数据结构-5-队列

//队列
//往头结点前面入队 ，从头结点后面出队

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


typedef struct Node                 //定义队列的结点结构体
{
    int data;
    struct Node* next;
    struct Node* pre;
} Node;


Node* initQueue()                               //初始化队列
{
    Node* Q = (Node*)malloc(sizeof(Node));      //为头结点分配动态内春空间
    Q->data = 0;                
    Q->pre = Q;                                 //初始化pre
    Q->next = Q;                                //初始化next
    return Q;
}


void enQueue(Node* Q, int data)                         //入队       
{
    Node* node = (Node*)malloc(sizeof(Node));           //为新结点分配动态内存空间
    node->data = data;                                  //为新结点赋值
    node->next = Q;                                     //将头结点的地址 赋值给 新结点的next
    node->pre = Q->pre;                                 //将头结点的pre的值 赋值给 新结点的pre
    Q->pre->next = node;                                //将新结点的地址 赋值给 头结点的pre指向的结点的next
    Q->pre = node;                                      //将新结点的地址 赋值给 头结点的pre
    Q->data++;                                          //头结点的data++
}


int isEmpty(Node* Q)                                    //判队列是否为空
{
    if (Q->data == 0 || Q->next == Q)                   //如果头结点的data == 0，或者头结点的next == 自己
    {
        return 1;                                       //返回 1，代表队列为空
    } 
    else 
    {
        return 0;                                       //返回 0，代表队列不为空
    }
}


int deQueue(Node* Q)                                    //出队
{
    if (isEmpty(Q))                                     //判断队列是否为空
    {
        return 0;                                       //为空则返回 0
    } 
    else 
    {                                          
        Node* node = Q->next;                           //将头结点的next的值 赋值给 node
        Q->next = Q->next->next;                        //将头结点的next指向的结点的next的值 赋值给 头结点的next
        Q->next->pre = Q;                               //将头结点的地址 赋值给 头结点的next指向的结点的pre
        return node->data;                              //返回出队结点的值
    }
}


void printQueue(Node* Q)                                //打印队列
{
    Node* node = Q -> next;                             //将头结点的next的值 赋值给 node
    while (node != Q)                                   //判断node 是否是头结点的地址       
    {
        printf("%d -> ", node -> data);                 //打印node的data
        node = node -> next;                            //更新node
    }
    printf("NULL\n");
}


int main() {
    Node* Q = initQueue();                      //初始化队列
    enQueue(Q, 1);                              //1 入队
    enQueue(Q, 2);                              //2 入队
    enQueue(Q, 3);                              //3 入队
    enQueue(Q, 4);                              //4 入队
    printQueue(Q);                              //打印队列
    printf("dequeue = %d\n", deQueue(Q));       //出队
    printf("dequeue = %d\n", deQueue(Q));       //出队
    printQueue(Q);                              //打印队列
    return 0;
}