数据结构 队列

一、队列
1.队列是一种操作受限制的线性表，具有两个特殊的属性。第一，新项只能添加到表的末尾（称为入队）。第二，只能从表的开头移除项（称为出队）。因此队列是一种“先进先出”的数据形式。

二、链队列
1.因为入队和出队操作分别在链表的两端进行，所以使用两个指针分别指向链表的首元结点（若有头结点，则指向头结点）和链表的尾结点。指向链表的首元结点（或头结点）的指针为front，指向链表的尾结点的指针为rear。

带头结点的链队列
不带头结点的链队列

2.链队列的存储结构定义：

#define SIZE 20
typedef struct people{int num;          //序号char name[SIZE];  //姓名
}Item;
typedef struct node{Item item;           //数据域struct node * next;  //指针域，指向链表中的下一个结构
}Node;    //队列的结点类型名为Node
typedef struct queue{Node * front;   //指向队头结点的指针Node * rear;    //指向队尾结点的指针
}Queue;  //链队列类型名为Queue

该定义中通过typedef为某一类型自定义名称。用Item作为struct people的别名（这样做更加通用），如果以后需要其他数据形式的队列，可以重新定义Item类型。用Node作为struct node的别名，队列的结点类型名是Node。用Queue作为struct queue的别名，链队列类型名为Queue。若有Queue Q;则表示创建了一个队列。从逻辑上说，链队列是元素结点构成的，而从数据类型的角度，链队列实际上是两个指针的组合。

3.链队列的初始化：
链队列初始化为空，队头指针与队尾指针指向头结点。

void InitQueue(Queue * Q)  //形参：指向Queue类型的指针
{Q->front=Q->rear=(Node *)malloc(sizeof(Node));  //建立头结点，并将其地址赋给队头指针、队尾指针Q->front->next=NULL;                            //头结点的指针域设置为NULL
}

带头结点的链队列初始化

void InitQueue(Queue * Q)  //形参：指向Queue类型的指针
{Q->front=NULL;        //队头指针指向NULLQ->rear=NULL;         //队尾指针指向NULL
}

不带头结点的链队列初始化

带头结点的链队列初始化前/后：（初始化后队列为空）

4.链队列的入队操作：

bool EnQueue(Queue * Q,Item item)  //形参：1.指向Queue类型的指针  2.Item类型的变量item，用于为新结点的数据域赋值
{Node * temp;  //指向Node类型的指针temptemp=(Node *)malloc(sizeof(Node));  //申请一个结点的空间，并将其地址赋给结构指针tempif(temp==NULL)  //若申请结点不成功，则返回falsereturn false;Copy(item,temp);     //Copy()用于处理数据域，可以根据程序自定义处理数据域的方式temp->next=NULL;     //新结点的next指针指向NULLQ->rear->next=temp;  //队尾结点的指针域指向新结点Q->rear=temp;        //队列的尾指针指向新结点return true;      
}

5.链队列的出队操作：

bool DeQueue(Queue * Q,Item * item)  //形参:1.指向Queue类型的指针 2.指向Item类型的指针，带出出队结点的数据域
{Node * temp;  //指向Node类型的指针tempif(Q->front==Q->rear)  //若队列为空，则返回falsereturn false;       temp=Q->front->next;   //指针temp指向首元结点Q->front->next=temp->next;  //将首元结点的指针域赋给头结点if(Q->rear==temp)    //若队中只有一个结点，则出队后队列为空Q->rear=Q->front; //修改队尾指针，指向头结点*item=temp->item;    //将出队结点的数据域通过Item类型的指针带出free(temp);          //释放出队结点的空间return true;         
}

6.链队列的队长：

int QueueItemCount(const Queue * Q)  //形参:指向Queue类型的指针，由于该函数不修改队列，使用const修饰符对指针所指向的内容进行保护
{int count=0;  //定义计数器countNode * temp;  //指向Node类型的指针temptemp=Q->front->next;  //指针temp指向首元结点while(temp!=NULL)     //遍历队列，每经过一个结点计数器递增{count++;temp=temp->next;}return count;  //返回队列长度
}

7.清空链队列：

void EmptyTheQueue(Queue * Q)  //形参:指向Queue类型的指针
{Item item;    //Item类型的变量itemNode * temp;  //指向Node类型的指针temptemp=Q->front->next;  //指针temp指向首元结点while(temp!=NULL)  //遍历队列，每经过一个结点调用一次出队算法{temp=temp->next;   //先将指针temp指向下一结点DeQueue(Q,&item);  //调用出队算法}
}

注意：在调用出队算法前，需要将指针temp指向下一结点。若调用出队算法后，再修改指针temp则会导致程序出错。例如第一次循环，指针temp指向首元结点，若先调用出队算法，首元结点删除，指针temp的指向无法确定。

8.输出链队列：

void output(const Queue * Q)  //形参:指向Queue类型的指针，由于该函数不修改队列，使用const修饰符对指针所指向的内容进行保护
{Node * temp;  //指向Node类型的指针temptemp=Q->front->next;  //指针temp指向首元结点while(temp!=NULL)     //遍历队列{printf("序号: %d,姓名: %s\n",temp->item.num,temp->item.name);  //输出形式由数据域的类型决定temp=temp->next;}
}

9.链队列样例：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>#define SIZE 20typedef struct people{int num;          //序号char name[SIZE];  //姓名
}Item;
typedef struct node{Item item;           //数据域struct node * next;  //指针域，指向链表中的下一个结构
}Node;
typedef struct queue{Node * front;Node * rear;
}Queue;void InitQueue(Queue * Q);
void output(const Queue * Q);
void Copy(Item item,Node * pnode);
bool EnQueue(Queue * Q,Item item);
bool DeQueue(Queue * Q,Item * item);
void EmptyTheQueue(Queue * Q);
int QueueItemCount(const Queue * Q);int main()
{Queue Q;Item temp;Item item;int i;int count=1;int number;InitQueue(&Q);printf("请输入入队人姓名:");while(scanf("%s",temp.name)&&temp.name[0]!='#'){temp.num=count++;EnQueue(&Q,temp);printf("请输入入队人姓名:");}printf("队列为:\n");output(&Q);number=QueueItemCount(&Q);printf("队列的大小为:%d",number);printf("\n连续出队3人:\n");for(i=0;i<3;i++){DeQueue(&Q,&item);printf("序号: %d,姓名: %s\n",item.num,item.name);}printf("现队列为:\n");output(&Q);printf("现队列的大小为:%d",QueueItemCount(&Q));printf("\n清空队列\n");EmptyTheQueue(&Q);printf("\nBye!");return 0;
}void InitQueue(Queue * Q)
{Q->front=Q->rear=(Node *)malloc(sizeof(Node));Q->front->next=NULL;
}bool EnQueue(Queue * Q,Item item)
{Node * temp;temp=(Node *)malloc(sizeof(Node));if(temp==NULL)return false;Copy(item,temp);temp->next=NULL;Q->rear->next=temp;Q->rear=temp;return true;
}bool DeQueue(Queue * Q,Item * item)
{Node * temp;if(Q->front==Q->rear)return false;temp=Q->front->next;Q->front->next=temp->next;if(Q->rear==temp)Q->rear=Q->front;*item=temp->item;free(temp);return true;
}void Copy(Item item,Node * pnode)
{pnode->item=item;
}void output(const Queue * Q)
{Node * temp;temp=Q->front->next;while(temp!=NULL){printf("序号: %d,姓名: %s\n",temp->item.num,temp->item.name);temp=temp->next;}
}int QueueItemCount(const Queue * Q)
{int count_=0;Node * temp;temp=Q->front->next;while(temp!=NULL){count_++;temp=temp->next;}return count_;
}void EmptyTheQueue(Queue * Q)
{Item item;Node * temp;temp=Q->front->next;while(temp!=NULL){temp=temp->next;DeQueue(Q,&item);}
}

输出结果：

三、循环队列
1.顺序队列：

由于队列的项只能添加到表的末尾，并且只能从表的开头移除项。所以得到了以上顺序队列队头指针front和队尾指针rear的移动情况。空队列时两者都指向下标为0的位置。当a、b、c入队时，指针front仍指向队头下标为0的位置，而指针rear则指向下标为3的位置。当a、b出队时，指针front指向下标为2的位置，而指针rear仍指向下标为3的位置。当d、e入队时，指针front仍指向下标为2的位置，但是指针rear的指向却出现了问题，越出了数组的边界，其指向无法确知。但是在下标0和1的位置上，有着闲置的空间，指针rear却无法指向他们，这种现象被称为假溢出。因此为了解决这个问题，引入了循环队列。（队头指针与队尾指针实际上是一种标记，标记队首元素与队尾元素，并非语言指针。）

2.循环队列：
为了解决假溢出，我们使队列形成环形，即在逻辑上将数组的首尾相连形成环。这样，当到达数组末尾时，若首元素空出，就可以把新添加的项储存到这些空出的元素中。

图中空队列时队头指针和队尾指针都指向下标为0的位置，因此这种情况下也出现了一个问题，当队列满时，队头指针和队尾指针也都指向下标为0的位置。也就是说，当队头指针和队尾指针都指向下标为0的位置时，我们无法区分该队列是满状态还是空状态。为了能正确判断循环队列的空和满，可以用以下两种方法解决：①：仅使用n-1个数组空间。②：使用额外标记，如SIZE来记录使用元素的个数。当SIZE为0时表示队空。当SIZE为数组大小时表示队满。

3.循环队列的存储结构定义：

#define SIZE 20
#define MAXSIZE 7  //仅使用n-1个数组空间，即队列大小最大为6typedef struct people{int num;          //序号char name[SIZE];  //姓名
}Item;
typedef struct node{Item item[MAXSIZE];  //数据域占用的数组空间int front;           //头指针指示器,指向队首元素int rear;            //尾指针指示器,指向队尾元素
}Queue;

4.循环队列初始化：
循环队列初始化为空，将队头指针与队尾指针都指向下标为0的位置。

void InitQueue(Queue * Q)  //形参：指向Queue类型的指针
{Q->front=0;  //队头指针指向下标为0的位置Q->rear=0;   //队尾指针指向下标为0的位置
}

5.循环队列判空与判满：
对于仅使用n-1个数组空间的情况，循环队列判断空与满，主要看front指针与rear指针的相对位置。当front指针与rear指针的相对位置为0时（即两者指向同一位置），循环队列就为空。那么如何来判断满呢？我们使用取余的方法。对n取余其结果只能在【0,n-1】的范围里。当队尾指针指向的下标+1对数组大小取余与队头指针指向的下标相同，循环队列就为满。例如，数组大小为7，仅使用n-1个数组空间(有效空间为6,下标0~5)，此时front指针指向下标为0的位置，rear指针指向下标为6的位置。（6+1）%7=0，与front指针指向的位置相同，队列为满。
①判断循环队列为空：

bool QueueIsEmpty(const Queue * Q)  //形参:指向Queue类型的指针，由于该函数不修改队列，使用const修饰符对指针所指向的内容进行保护
{if(Q->front==Q->rear)//若队头指针与队尾指针都指向相同的位置，则队列为空返回true，否则返回falsereturn true;elsereturn false;
}

②判断循环队列为满：

bool QueueIsFull(const Queue * Q)  //形参:指向Queue类型的指针，由于该函数不修改队列，使用const修饰符对指针所指向的内容进行保护
{if((Q->rear+1)%MAXSIZE==Q->front)  //若队尾指针指向的下标+1对数组大小取余与队头指针指向的下标相同，则队列为满返回true，否则返回falsereturn true;elsereturn false;}

循环队列满时数组情况(仅使用n-1个数组空间)

6.循环队列的入队操作：

bool EnQueue(Queue * Q,Item item)  //形参：1.指向Queue类型的指针  2.Item类型的变量item，用于为结点的数据域赋值
{if(QueueIsFull(Q)==true)  //判满，若队列为满，则返回falsereturn false;Q->item[Q->rear]=item;        //为结点的数据域赋值Q->rear=(Q->rear+1)%MAXSIZE;  //队尾指针后移return true;
}

7.循环队列的出队操作：

bool DeQueue(Queue * Q,Item * item)  //形参:1.指向Queue类型的指针 2.指向Item类型的指针，带出出队结点的数据域
{if(QueueIsEmpty(Q)==true)  //判空，若队列为空，则返回falsereturn false;*item=Q->item[Q->front];       //带出出队结点的数据域Q->front=(Q->front+1)%MAXSIZE; //队头指针后移return true;
}

8.输出循环队列：
注意：输出时需要用额外的变量将循环队列的front指针与rear指针记录下来，若直接使用，则可能造成front指针与rear指针的指向改变，若再使用错误的指向去做其他事情就会发生错误。

void output(const Queue * Q)  //形参:指向Queue类型的指针，由于该函数不修改队列，使用const修饰符对指针所指向的内容进行保护
{int front,rear;  //定义两个整形变量，用于记录front指针与rear指针的指向front=Q->front;rear=Q->rear;while(front<rear){printf("序号: %d,姓名: %s\n",Q->item[front].num,Q->item[front].name);  //输出形式由数据域的类型决定front++;}
}

9.循环队列样例：

#include<stdio.h>
#include<stdbool.h>#define SIZE 20
#define MAXSIZE 7typedef struct people{int num;          //序号char name[SIZE];  //姓名
}Item;
typedef struct node{Item item[MAXSIZE];  //数据域int front;        //头指针指示器,指向队首元素int rear;         //尾指针指示器,指向队尾元素
}Queue;void InitQueue(Queue * Q);
void output(const Queue * Q);
bool EnQueue(Queue * Q,Item item);
bool QueueIsFull(const Queue * Q);
bool QueueIsEmpty(const Queue * Q);
bool DeQueue(Queue * Q,Item * item);int main()
{Queue Q;Item item;Item item_;int i;int number=1;InitQueue(&Q);if(QueueIsEmpty(&Q)==true)printf("现在队列为空!\n");while(1){printf("请输入入队人姓名:");scanf("%s",item.name);item.num=number++;EnQueue(&Q,item);if(QueueIsFull(&Q)==true){printf("队列大小为: %d,队列已满!\n",MAXSIZE-1);break;}}printf("队列为:\n");output(&Q);printf("连续出队3人:\n");for(i=1;i<=3;i++){DeQueue(&Q,&item_);printf("序号: %d,姓名: %s\n",item_.num,item_.name);}printf("现队列为:\n");output(&Q);printf("\nBye!");return 0;
}void InitQueue(Queue * Q)
{Q->front=0;Q->rear=0;
}bool QueueIsEmpty(const Queue * Q)
{if(Q->front==Q->rear)return true;elsereturn false;
}bool QueueIsFull(const Queue * Q)
{if((Q->rear+1)%MAXSIZE==Q->front)return true;elsereturn false;}bool EnQueue(Queue * Q,Item item)
{if(QueueIsFull(Q)==true)return false;Q->item[Q->rear]=item;Q->rear=(Q->rear+1)%MAXSIZE;return true;
}bool DeQueue(Queue * Q,Item * item)
{if(QueueIsEmpty(Q)==true)return false;*item=Q->item[Q->front];Q->front=(Q->front+1)%MAXSIZE;return true;
}void output(const Queue * Q)
{int front,rear;front=Q->front;rear=Q->rear;while(front<rear){printf("序号: %d,姓名: %s\n",Q->item[front].num,Q->item[front].name);front++;}
}

输出结果：