队列_顺序队列 & 链式队列

队列 （Queue）
队头出，队尾入
操作集合：
(1)QueueInitiate(Q) 初始化队列Q
(2)QueueNotEmpty(Q) 队列Q非空否
(3)QueueAppend(Q,x) 入队列
(4)QueueDelete(Q,d) 出队列
(5)QueueGet(Q,d) 取队头数据元素

顺序队列：

队头是第一个元素的下标，队尾是最后一个元素下标+1（最后空位）
顺序队列假溢出问题：

顺序队列因多次入队和出队操作后出现的有存储空间但不能进行入队操作的溢出。

顺序循环队列的基本原理：
把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当 rear 和 front 达到MaxQueueSize-1 后，再前进一个位置就自动到0。

定义：

typedef struct
{
    ElemType queue[MaxQueueSize];
    int rear;   //队尾
    int front;  //对头
    int count;  //计数器：用于区分空队和满队 
}SequenceQueue;

(1)QueueInitiate(Q) 初始化队列Q

void QueueInitiate(SequenceQueue *Q)
{
    Q->rear = 0;
    Q->count = 0;
    Q->front = 0;
}

(3)QueueAppend(Q,x) 入队列

int QueueAppend(SequenceQueue *Q, ElemType x)
{
    if(Q->count>0 && Q->rear == Q->front)
    {
        printf("队列已满无法插入\n");
        return 0;
    }
    else
    {
        Q->queue[Q->rear] = x;
        //一个小的数跟一个大的数取余会得到自身，两数相等，取余为0 
        Q->rear = (Q->rear + 1) % MaxQueueSize;
        //这种好理解
        /*Q->rear++;
        if(Q->rear == MaxQueueSize) Q->rear = 0;*/
        Q->count++;
        return 1;
    }
} 

(4)QueueDelete(Q,d) 出队列

int QueueDelete(SequenceQueue *Q, ElemType *d)
{
    if(Q->count == 0)
    {
        printf("队列已空无法出队\n");
        return 0;
    }
    else
    {
        *d = Q->queue[Q->front];
        Q->front = (Q->front + 1) % MaxQueueSize;
        Q->count--;
        return 1;
    }
} 

测试代码：输入10个数，输出10个数。

#include<stdio.h>
#include<stdlib.h>
#define MaxQueueSize 50
#define ElemType int
#include "SequenceQueue.h"
void main(void)
{
    int i, x;
    SequenceQueue myQueue;
    QueueInitiate(&myQueue);
    
    for(i = 1; i<=10; i++)
    {
        QueueAppend(&myQueue, i);
    }
    while(myQueue.count != 0)
    {
        QueueDelete(&myQueue, &x);
        printf("%d\n", x);
    }
} 

---

链式队列：

SingleLinkList 定义队列节点

typedef struct LinkList 
{
    ElemType data;
    struct LinkList *next;
}SingleLinkList;

LinkQueue 定义队列：队头、队尾指针

typedef struct
{
    SingleLinkList *front;
    SingleLinkList *rear;
}LinkQueue;

LinkQueueInit 初始化

void LinkQueueInit(LinkQueue *LQ)
{
    LQ->front = NULL;
    LQ->rear = NULL;
}

LinkQueueNotEmpty 判空

int LinkQueueNotEmpty(LinkQueue LQ)
{
    if(LQ.front == NULL) return 0;
    else return 1;
} 

LinkQueueAppend 入队

int LinkQueueAppend(LinkQueue *LQ, ElemType x)
{
    SingleLinkList *p = (SingleLinkList *)malloc(sizeof(SingleLinkList));
    if(p == NULL)
    {
        printf("内存不足！入队失败");
        return 0;
    }
    p->data = x;
    p->next = NULL;
    if(LQ->rear != NULL)
    {
        LQ->rear->next = p;
        LQ->rear = p;
    }
    if(LQ->front == NULL)//第一次插入 
    {
        LQ->front = p;
        LQ->rear = p;       
    }
    return 1;       
}

LinkQueueOut 出队

int LinkQueueOut(LinkQueue *LQ, ElemType *x) 
{
    if(LQ->front == NULL)
    {
        printf("队空，出队出错！");
        return 0;
    }
    *x = LQ->front->data;
    
    SingleLinkList *p = LQ->front;
    LQ->front= LQ->front->next;//队头往前移 
    free(p);
    
    return 1;
}

GetLinkQueueFront 获取对头元素

int GetLinkQueueFront(LinkQueue LQ, ElemType *x) 
{
    if(LQ.front == NULL)
    {
        printf("队空！");
        return 0;
    }
    *x = LQ.front->data;
    return 1;
}

Destroy 销毁队列

void Destroy(LinkQueue Q) 
{
    SingleLinkList *p, *q;
    p = Q.front;
    while(p != NULL)
    {
        q = p;
        p = p->next;
        free(q);
    }
}

总结：
1、从原来的头指针（head）变成队头（front）队尾（rear）指针；
2、写入数据只能从队尾写入，读取数据只能从队头读取。

测试代码：

#include<stdio.h>
#include<stdlib.h>
#define ElemType int
#include "LinkQueue.h"
void main(void)
{
    LinkQueue Q;
    LinkQueueInit(&Q);//初始化 
    int i, x;
    for(i=0; i<10; i++)
    {
        LinkQueueAppend(&Q, i+1);//入队 
    }
    GetLinkQueueFront(Q, &x);//队头元素 
    printf("%d\n",x);
    while(LinkQueueNotEmpty(Q))//判空 
    {
        LinkQueueOut(&Q, &x);//出队 
        printf("%d ", x);
    }
    Destroy(Q);
}