队列

（1）队列的基本概念

队头：允许删除元素的一端；

队尾：允许插入元素的一端。

2）队列的顺序存储结构

#include <stdio.h>
#define MaxSize 10
typedef struct SeQueue
{
    int data[MaxSize];
    int front,rear;
};
//初始化队列，队头、队尾指针均指0
void InitQueue(SeQueue &Q){
    Q.front=0;
    Q.rear=0;
}
//队列判空:队头与队尾指向相同空间，即差值为0，队空
bool QueueEmpty(SeQueue Q)
{
    return (Q.front==Q.rear);
}
//入队操作：先将数据插入至队尾，再将尾指针后移
bool EnQueue(SeQueue &Q,int x)
{
    if((Q.rear+1)%MaxSize==Q.front) return false; //判断队列是否满，满则返回false,这里牺牲了一个存储空间用来区分队满和队空
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize; //这里要注意！由于这种方式实现的队列在逻辑上似乎是循环的，也称作循环队列
    return true;
}
//出队操作：先将数据取出，再将头指针后移
bool DeQueue(SeQueue &Q,int &x)
{
    if(Q.front==Q.rear) return false; //判断是否队空
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}
//查;获取队头元素
bool GetHead(SeQueue Q,int &data)
{
    if(Q.front==Q.rear) return false;
    data=Q.data[Q.front];
    return true;
}
int main(void)
{
    SeQueue Q;
    int x;
    int data;
    InitQueue(Q);
    printf("队列是否为空：%d\n",QueueEmpty(Q));
    EnQueue(Q,1);
    printf("队列是否为空：%d\n",QueueEmpty(Q));
    GetHead(Q,data);
    printf("队头元素为：%d\n",data);
    DeQueue(Q,x);
    printf("队列是否为空：%d\n",QueueEmpty(Q));
    return 0;
}

队列元素个数：(Q.rear-Q.front+MaxSize)%MaxSize;

如果想要不浪费一个存储空间用来区分队满与队空，我们可以使用一个在队列中定义一个size用来记录元素个数，初始设为0，增加元素size++，减少元素size--，队满条件size= =Maxsize，队空条件为：size= =0；

也可以设置tag，删除tag置为0，插入tag置为1，队满一定是因为插入，tag一定为1；

3）队列的链式存储结构

#include <stdio.h>
#include <stdlib.h>
//定义链式队列结点
typedef struct LinkNode
{
    int data;
    LinkNode * next;
}LinkNode;
//定义链式队列
typedef struct 
{
    LinkNode * front,* rear;
}LinkQueue;
//初始化(带头结点)
void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode)); 
    Q.front->next=NULL;
}
//队列判空:如果头、尾指针指向同一个结点或者头结点的next指向为NULL则为空
bool QueueEmpty(LinkQueue Q)
{
    return (Q.front->next==NULL);
    //return (Q.front=Q.rear);
}
//入队操作(带头结点)
void EnQueue(LinkQueue &Q,int x)
{
    //申请一个新的结点用于存储待插入的数据
    LinkNode * p=(LinkNode *)malloc(sizeof(LinkNode));
    p->data=x;
    //将新结点入队,即在队尾插入新结点
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
}
//出队操作(带头结点)
void DeQueue(LinkQueue &Q,int &x)
{
    LinkNode * p;
    p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    //！！如果删除的元素为表尾结点,要将尾指针指向头结点
    if(Q.rear==p)Q.rear=Q.front;
    free(p);
}
//带头结点版本
int main(void)
{
    int x;
    LinkQueue Q;
    InitQueue(Q);
    printf("队列是否为空：%d\n",QueueEmpty(Q));
    EnQueue(Q,2);
    printf("队列是否为空：%d\n",QueueEmpty(Q));
    DeQueue(Q,x);
    printf("删除的元素为：%d\n",x);
    printf("队列是否为空：%d\n",QueueEmpty(Q));
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
//定义链式队列结点
typedef struct LinkNode
{
    int data;
    LinkNode * next;
}LinkNode;
//定义链式队列
typedef struct 
{
    LinkNode * front,* rear;
}LinkQueue;
//初始化队列（不带头结点）:使front、rear都指向NULL
void InitQueue1(LinkQueue &Q)
{
    Q.front=NULL;
    Q.rear=NULL;
}
//判断队列是否为空（不带头结点）
bool QueueEmpty1(LinkQueue Q)
{
    return (Q.front==NULL);
}
//入队操作(不带头结点)
void EnQueue1(LinkQueue &Q,int x)
{
    //申请一个结点用来存储入队数据
    LinkNode * p=(LinkNode *)malloc(sizeof(LinkNode));
    p->data=x;
    //执行入队操作
    p->next=NULL;
    if(Q.rear==NULL)
    {
        Q.front=p;
        Q.rear=p;
    }
    else
    {
        Q.rear->next=p;
        Q.rear=p;
    }
}
//出队操作(不带头结点)
void DeQueue1(LinkQueue &Q,int &x)
{
    LinkNode * p=Q.front;
    x=p->data;
    Q.front=p->next;
    //如果出队恰好使最后一个结点，那么要把rear恢复为NULL
    if(Q.rear==p)
        Q.rear=NULL;
    free(p);
}

int main(void)
{
    int x;
    LinkQueue Q;
    InitQueue1(Q);
    printf("队列是否为空：%d\n",QueueEmpty1(Q));
    EnQueue1(Q,2);
    printf("队列是否为空：%d\n",QueueEmpty1(Q));
    DeQueue1(Q,x);
    printf("删除的元素为：%d\n",x);
    printf("队列是否为空：%d\n",QueueEmpty1(Q));
    return 0;
}