数据结构—队列

队列：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

读取特性：“先入先出”，”后入后出“(FIFO)。 类比 现实中的排队，放水入水的池子，充电的手机。

队列结构
队列状态
将队列设计成循环队列的形式，来演示入队出队过程。
循环队列入队出队

1、顺序存储—循环队列

顺序存储，内存中开辟一块连续的内存，预设空间大小，需要front，rear标记队头 队尾。
设计思路：
1：初始化队列为空，front = rear = 0;
2：入队，rear+1，指向队尾的下一个存储单元，为了实现循环利用取模运算：rear = (rear+1) % MaxSize;
3：出队，front+1，指向下一个队首，实现循环：front = (front+1) % MaxSize;
4：判断队满，(Q.rear+1) % MaxSize == Q.front;

预设置

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

循环队列的顺序存储结构

typedef struct {
    QElemType data[MAXSIZE];
    int front;        /* 队头标记 */
    int rear;        /* 队尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue;

函数实现，初始化，入队，出队...

//初始化一个空队列Q
Status InitQueue(SqQueue *Q){
    Q->front = Q->rear = 0;
    return OK;
}
//将队列清空
Status ClearQueue(SqQueue *Q){
    
    Q->front = Q->rear = 0;
    return OK;
}
//返回Q的元素个数,也就是队列的当前长度
int QueueLength(SqQueue Q){
    return (Q.rear -Q.front + MAXSIZE)%MAXSIZE;
}
//若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR;
Status GetHead(SqQueue Q,QElemType *e){
    
    if (Q.front == Q.rear) {//队列is空
        return ERROR;
    }
    *e = Q.data[Q.front];
    
    return OK;
}
// 入队：若队列未满,则插入元素e为新队尾元素
Status EnQueue(SqQueue *Q,QElemType e){
    
    if ((Q->rear + 1)%MAXSIZE == Q->front) {//队列已满
        return 0;
    }
   //将元素e赋值给队尾
    Q->data[Q->rear] = e;
    
    //rear 向后移动一位,若到最后则转到数组头部;
    Q->rear = (Q->rear+1)%MAXSIZE;
    
    return OK;
}
//  出队：若队列不空,则删除Q中队头的元素,用e返回值
Status DeQueue(SqQueue *Q,QElemType *e){
   
    if (Q->front == Q->rear) { //判断队列是否为空
        return ERROR;
    }
    
    *e = Q->data[Q->front];  //将队头元素赋值给e
    
    Q->front = (Q->front+1)%MAXSIZE; //front 指针向后移动一位,若到最后则转到数组头部
    
    return OK;
}
//从队头到队尾依次对队列的每个元素数组
Status QueueTraverse(SqQueue Q){
    int I;
    i = Q.front;
    while ((i+Q.front) != Q.rear) {
        printf("%d   ",Q.data[I]);
        i = (i+1)%MAXSIZE;
    }
    printf("\n");
    return OK;
}

2、链式存储实现

核心：

进入队列 ：Q.rear尾节点后追加新节点，将Q.rear指向新节点，新节点成队尾；
出队列：Q.front指向的首元节点出队列，Q.front指向首元节点的下一个节点

链式结构

结点结构

typedef struct QNode {   /* 结点结构 */
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct {            /* 队列的链表结构 */
    QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

函数实现

 //初始化队列
Status InitQueue(LinkQueue *Q){
    
     Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));//1. 头/尾指针都指向新生成的结点
   
    if (!Q->front) { //2.判断是否创建新结点成功与否
        return ERROR;
    }

    Q->front->next = NULL;  //3.头结点的指针域置空
    
    return OK;
}

//销毁队列Q*/
Status DestoryQueue(LinkQueue *Q){
  
    while (Q->front) {  //遍历整个队列,销毁队列的每个结点
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}

//将队列Q置空*/
Status ClearQueue(LinkQueue *Q){
    
    QueuePtr p = Q->front->next;
    Q->rear = Q->front;
    QueuePtr temp;
    while (p) {
        temp = p->next;
        free(p);
        p = temp;
    }
    
    Q->front->next = NULL;
    
    return OK;
}

//判断队列Q是否为空*/
Status QueueEmpty(LinkQueue Q) {
    
    if (Q.front == Q.rear) {
        return TRUE;
    }
    return FALSE;
}

//入队： 插入元素e为队列Q的新元素*/
Status EnQueue(LinkQueue *Q,QElemType e){
    
    QueuePtr temp = malloc(sizeof(QNode));
    if (!temp) {
        return ERROR;
    }

    temp->data = e;
    temp->next = NULL;

    Q->rear->next = temp;//将新结点插入到队尾
    
    Q->rear = temp;//修改队尾指针
    
    return OK;
}

//出队列
Status DeQueue(LinkQueue *Q,QElemType *e){
    
    if (Q->front == Q->rear) {
        return ERROR;
    }
    QueuePtr p = Q->front->next;
    *e = p->data;
    
    Q->front->next = p->next;//将原队列头结点的后继p->next 赋值给头结点后继
    
    if (Q->rear == p) {//若队头就是队尾,则删除后将rear指向头结点.
        Q->rear = Q->front;
    }
    free(p);

    return OK;
}
//获取队头元素
Status GetHead(LinkQueue Q,QElemType *e){
    
    if (Q.front != Q.rear) {
        *e = Q.front->next->data;//返回队头元素的值,队头指针不变
        return OK;
    }
    return ERROR;
}