数据结构--双端队列

数据结构–双端队列

双端队列（Double-ended Queue，简称Deque）是一种具有队列和栈特性的数据结构，可以在队列的两端进行插入和删除操作。双端队列允许从前端和后端同时进行插入和删除操作，因此可以称为“两端都可以进出的队列”。

双端队列的特点包括：

1. 可以在队列的头部和尾部进行插入和删除操作。
2. 元素的插入和删除操作可以分别称为入队和出队操作。
3. 可以实现先进先出（FIFO）和后进先出（LIFO）两种操作方式。
4. 可以用于实现栈、队列以及其他需要在两端进行插入和删除操作的场景。

双端队列的常见操作包括：

1. 在队列头部插入元素（头部入队）：将元素插入到队列头部。
2. 在队列尾部插入元素（尾部入队）：将元素插入到队列尾部。
3. 从队列头部删除元素（头部出队）：删除队列头部的元素并返回。
4. 从队列尾部删除元素（尾部出队）：删除队列尾部的元素并返回。
5. 获取队列头部的元素：返回队列头部的元素，但不删除。
6. 获取队列尾部的元素：返回队列尾部的元素，但不删除。
7. 判断队列是否为空：判断队列中是否有元素。
8. 获取队列中的元素个数：返回队列中元素的个数。

双端队列的实现方式有多种，包括使用数组、链表等数据结构。具体的实现方式可以根据不同的需求和场景选择合适的方式。

常用操作代码实现

#include <stdio.h>
#include <stdlib.h>

// 定义双端队列节点结构体
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域，指向下一个节点
} Node;

// 定义双端队列结构体
typedef struct Deque {
    Node* front;  // 队头指针
    Node* rear;   // 队尾指针
} Deque;

// 初始化双端队列
Deque* initializeDeque() {
    Deque* deque = (Deque*)malloc(sizeof(Deque));
    deque->front = NULL;
    deque->rear = NULL;
    return deque;
}

// 判断双端队列是否为空
int isEmpty(Deque* deque) {
    return (deque->front == NULL);
}

// 在队头插入元素
void insertFront(Deque* deque, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(deque)) {
        deque->front = newNode;
        deque->rear = newNode;
    } else {
        newNode->next = deque->front;
        deque->front = newNode;
    }
}

// 在队尾插入元素
void insertRear(Deque* deque, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(deque)) {
        deque->front = newNode;
        deque->rear = newNode;
    } else {
        deque->rear->next = newNode;
        deque->rear = newNode;
    }
}

// 从队头删除元素
int deleteFront(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    int value = deque->front->data;
    Node* temp = deque->front;
    deque->front = deque->front->next;

    if (deque->front == NULL) {
        deque->rear = NULL;
    }

    free(temp);
    return value;
}

// 从队尾删除元素
int deleteRear(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    int value = deque->rear->data;
    Node* temp = deque->rear;
    Node* current = deque->front;

    while (current->next != deque->rear) {
        current = current->next;
    }

    deque->rear = current;
    deque->rear->next = NULL;
    free(temp);
    return value;
}

// 获取队头元素
int getFront(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    return deque->front->data;
}

// 获取队尾元素
int getRear(Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty.\n");
        return -1;
    }

    return deque->rear->data;
}

// 打印双端队列元素
void printDeque(Deque* deque) {
    Node* current = deque->front;

    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");
}

int main() {
    Deque* deque = initializeDeque();

    insertFront(deque, 1);  // 队头插入元素1
    insertFront(deque, 2);  // 队头插入元素2
    insertRear(deque, 3);   // 队尾插入元素3

    printDeque(deque);      // 输出：2 1 3

    deleteFront(deque);     // 从队头删除元素
    printDeque(deque);      // 输出：1 3

    deleteRear(deque);      // 从队尾删除元素
    printDeque(deque);      // 输出：1

    printf("Front element: %d\n", getFront(deque));  // 输出队头元素：1
    printf("Rear element: %d\n", getRear(deque));    // 输出队尾元素：1

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

知识点回顾与重要考点