队列

队列：Queue FIFO

队首（front）允许删除的一端
队尾（rear）允许插入的一端

静态队列：使用数组存储，设立一个队首指针front，一个队尾指针rear，
front = rear = 0；
1、入队 rear + 1
2、出队 front + 1 ，返回出队元素
3、空队列 front = rear；
4、rear = MAX_QUEUE_SIZE - 1或front = rear；

循环队列：用来克服队列“假溢出”现象（front和rear只加不减，有可能超过指针上界）
1、当队首或队尾指针指向向量上界（MAX_QUEUE_SIZE - 1）, + 1操作变为指向向量下界0
2、只用front = rear，不能判断是空队列，还是满队列
3、循环队列满：（rear + 1）%MAX_QUEUE_SIZE = front

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #define  MAX_QUEUE_SIZE 5
 5 #define ERR -1 
 6 #define OK  0 
 7 
 8 typedef int ElemType;
 9 
10 typedef struct SqQueue
11 {
12     ElemType Queue_array[MAX_QUEUE_SIZE];
13     int front;
14     int rear;
15 };
16 
17 SqQueue Init_CirQueue()
18 {
19     SqQueue q;
20     q.front = q.rear = 0;
21     return q;
22  }
23 
24 int Push_CirQueue(SqQueue *s, ElemType e)
25 {
26     if ((s->rear + 1) % MAX_QUEUE_SIZE == s->front) //栈满
27     {
28         return ERR;
29     }
30     s->Queue_array[s->rear] = e;
31     s->rear = (s->rear + 1) % MAX_QUEUE_SIZE;
32     return OK;
33 }
34 
35 int Pop_CirQueue(SqQueue *q, ElemType *e)
36 {
37     if (q->front + 1 == q->rear)
38     {
39         return ERR;
40     }
41     *e = q->Queue_array[q->front];
42     q->front = (q->front + 1) % MAX_QUEUE_SIZE;
43     return OK;
44 }
45 
46 int main(void)
47 {
48     SqQueue cirQ = Init_CirQueue();
49 
50     for (int i = 0; i < 5; i++)
51     {
52         Push_CirQueue(&cirQ, i);
53     }
54     system("pause");
55     return 0;
56 }

队列的链式存储：单链表，需要两种结点，一种是数据结点，一种是队首队尾指针的结点

typedef struct QNode
{
    ElemType data;
    struct QNode *next;
};

typedef struct link_queue
{
    QNode *front;
    QNode *rear;
}Link_Queue;


Link_Queue* Init_Qnode()
{
    QNode *p;
    Link_Queue *q;
    p = (QNode*)malloc(sizeof(QNode));
    p->next = NULL;

    q = (Link_Queue *)malloc(sizeof(Link_Queue));
    q->front = q->rear = p;
    return q;
}

int Insert_Link_Queue(Link_Queue *q, ElemType e)
{
    QNode *p;
    if (q)
    {
        return ERR;
    }
    p = (QNode*)malloc(sizeof(QNode));
    p->data = e;
    p->next = NULL;
    //p->next = q->rear->next; 
    q->rear->next = p;
    q->rear = q->rear->next;
    return OK;
}

int Delete_Link_Queue(Link_Queue *q, ElemType *e)
{
    QNode *p;
    p = q->front->next;
    if (q->front == q->rear)
    {
        return ERR;
    }
    *e = p->data;
    q->front->next = p->next;

    if (p == q->rear)//如果只有一个结点因为出栈只能时Q->FRONT,既此时q->front和q->rear相等
    {
        q->rear == q->front;
    }
    free(p);

    return OK;
}

void Destroy_LinkQueue(Link_Queue *q)
{
    while (q->front != NULL)
    {
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }
}

队列

推荐阅读