【算法与数据结构】双端队列示例
程序员文章站
2022-07-14 14:16:27
...
双端队列可以从两侧入队和出队:
#include <stdio.h>
#include <stdlib.h>
struct dequeNode {
int data;
struct dequeNode *next;
struct dequeNode *prev;
};
typedef struct dequeNode Node;
typedef Node * Position;
typedef Node * Queue;
void deque_init(Queue *Q) {
*Q = malloc(sizeof(Node));
(*Q)->next = *Q;
(*Q)->prev = *Q;
}
int head(Queue Q, int* v) {
if (Q->next == Q) {
return -1;
}
*v = Q->next->data;
return 0;
}
int tail(Queue Q, int* v) {
if (Q->prev == Q) {
return -1;
}
*v = Q->prev->data;
return 0;
}
void enqueue_head(Queue Q, int v) {
Position tmp;
tmp = (Position)malloc(sizeof(Node));
tmp->data = v;
tmp->next = Q->next;
Q->next = tmp;
tmp->next->prev = tmp;
tmp->prev = Q;
}
void enqueue_tail(Queue Q, int v) {
Position tmp;
tmp = (Position)malloc(sizeof(Node));
tmp->data = v;
tmp->next = Q;
tmp->prev = Q->prev;
Q->prev = tmp;
tmp->prev->next = tmp;
}
int dequeue_head(Queue Q, int *v) {
Position tmp;
tmp = Q->next;
if (tmp == Q) {
return -1;
}
Q->next = Q->next->next;
Q->next->prev = Q;
*v = tmp->data;
free(tmp);
}
int dequeue_tail(Queue Q, int *v) {
Position tmp;
tmp = Q->prev;
if (tmp == Q) {
return -1;
}
Q->prev = Q->prev->prev;
Q->prev->next = Q;
*v = tmp->data;
free(tmp);
}
void printQueue(Queue Q) {
Position tmp = Q->next;
while (tmp != Q) {
printf("%4d", tmp->data);
tmp = tmp->next;
}
printf("\n");
}
int main(void) {
int i;
Queue q;
deque_init(&q);
enqueue_head(q, 5);
enqueue_head(q, 3);
enqueue_head(q, 2);
enqueue_tail(q, 8);
enqueue_tail(q, 1);
printQueue(q);
ret = head(q, &i);
printf("ret = %d, i = %d\n", ret, i);
ret = tail(q, &i);
printf("ret = %d, i = %d\n", ret, i);
dequeue_head(q, &i);
printf("i is: %d\n", i);
printQueue(q);
dequeue_head(q, &i);
printf("i is: %d\n", i);
printQueue(q);
dequeue_tail(q, &i);
printf("i is: %d\n", i);
printQueue(q);
dequeue_tail(q, &i);
printf("i is: %d\n", i);
printQueue(q);
printf("c test");
return 0;
}
推荐阅读
-
Python常见数据结构之栈与队列用法示例
-
Python实现的数据结构与算法之双端队列详解
-
数据结构--队列、双端队列实际举例详解(Python代码)
-
Python cookbook(数据结构与算法)通过公共键对字典列表排序算法示例
-
Python cookbook(数据结构与算法)找出序列中出现次数最多的元素算法示例
-
Python cookbook(数据结构与算法)实现对不原生支持比较操作的对象排序算法示例
-
JavaScript数据结构与算法之栈与队列
-
Python cookbook(数据结构与算法)找到最大或最小的N个元素实现方法示例
-
Python cookbook(数据结构与算法)实现优先级队列的方法示例
-
Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】