欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【算法与数据结构】双端队列示例

程序员文章站 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;
}
相关标签: deque 双端队列