2、队列

2.1 队列的基本概念

队列：队列简称队，是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列种插入元素称为入队或进队；删除元素称为出队或离队。队列的示意图如下所示：

对头（front）：允许删除的一端，又称队首。
队尾（rear）：允许插入的一端。
空队列：不含任何元素的空表。
队列的特性：先进先出。
队列的应用：速度不匹配问题、多用户资源竞争问题。

注意：栈和队列都是操作受限的线性表，不是任何对线性表的操作都适合栈和队列的操作，不可以随便读取栈或队列中间的某个元素。

2.2 队列的顺序存储结构

1.队列的顺序存储

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：对头指针 front 指向对头元素，队尾指针 rear 指向队尾元素的下一个位置。

队列的顺序存储类型描述如下：

#define MaxSize 50  //定义队列中元素的最大个数
typedef struct{
   ElemType data[MaxSize];  //存放队列元素
   int front,rear;  //队头指针和队尾指针
   } SqQueue;

初始状态（队空条件）：Q.front == Q.rear == 0
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1
出队操作：队不空时，先取队头元素值，再将队头指针加1

队列的操作示意图如下图所示：

在这里插入图片描述

队列操作示意图中 d 图所示，队列中仅有一个元素，再进行入队操作时，会出现“上溢出”，但这种溢出不是真正的溢出，在队列数组中仍然存在可以存放元素的空位置，这是一种“假溢出”。

2.循环队列

循环队列：将顺序队列臆造成一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。

当队首指针 Q.front = MaxSize-1 后，再前进一个位置就会自动到 0，可利用除法取余（%）来实现。

初始时：Q.front = Q.rear = 0
队首指针进1：Q.front = (Q.front + 1)%MaxSize
队尾指针进1：Q.rear = (Q.rear + 1)%MaxSize
队列长度：(Q.rear + MaxSize - Q.front)%MaxSize
出队入队时：指针都按照顺时针方向进1
注意：不能用动态分配的一维数组来实现循环队列，初始化时必须设定一个最大队列长度。

为了区分循环队列队空还是队满情况，有三种处理方式，其中第一种为常用的区分方式，重点掌握：

（1）牺牲一个单元来区分队空还是队满，入队时少用一个队列单元，约定以“队头指针在队尾的下一个指针作为堆满标志”。如下图 (d2) 所示。

队满条件： (Q.rear + 1)%MaxSize == Q.front
队空条件：Q.front == Q.rear
队列中元素的个数：(Q.rear + MaxSize - Q.front)%MaxSize
（2）类型中增设表示元素个数的数据成员。对空的条件为 Q.size = 0，队满的条件为 Q.size == MaxSize，有Q.front == Q.rear。
（3）类型中增设 tag 数据成员，以区分是队空还是队满。tag = 0 时，若因删除导致 Q.front == Q.rear，则为队空；tag = 1 时，若因插入导致 Q.front == Q.rear，则为队满。

循环队列出入队示意图如下所示：

在这里插入图片描述

3 . 循环队列的操作

（1）初始化

1
2
3

void InitQueue(SqQueue &Q){
   Q.front == Q.rear=0;  //初始化队首、队尾指针
}

（2）判队空

 bool isEmpty(SqQueue Q){
    if(Q.front == Q.rear) //队空条件
       return true;
    else
       return false;
 }

（3）入队

 bool EnQueue(SqQueue &Q,ElemType x){
    if( (Q.rear + 1)%MaxSize == Q.front) //队满则报错
       return false; 
    Q.data[Q.rear]=x;
    Q.rear= (Q.rear + 1)%MaxSize;  //队尾指针加1模
    return true;
 }

（4）出队

 bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.front == Q.rear)  //队空则报错
       return false;
    x=Q.data[Q.front]; 
    Q.front = (Q.front + 1)%MaxSize;  //队头指针加1取模
    return true;
 }

顺序队列示例代码
顺序队列基本操作：顺序队列的初始化、入队列、出队列以及显示队列中的数据元素的示例代码如下所示：

#include <stdio.h>
#include <stdlib.h>

#define QINITSIZE 100
#define QINCRECEMENT 10
#define OK 1
#define ERROR 0
#define null 0

typedef int Status;
typedef int QElemType;

typedef struct QueueType
{
    QElemType *front;
    QElemType *rear;
    int qsize;
}queue;

Status q_init(queue *q)
{
	q->front = (QElemType *)malloc(QINITSIZE*sizeof(QElemType));
	if(q->front == null)
		return ERROR;
	q->rear = q->front;
	q->qsize = QINITSIZE;
	return OK;
}

Status Enqueue(queue *q,int e)
{
	if(q->rear - q->front >= QINITSIZE)
	{
		q->front = (QElemType *)realloc(q,(q->qsize + QINCRECEMENT)*sizeof(QElemType));
		q->rear = q->front;
		q->qsize += QINCRECEMENT; 
	}
	*q->rear++ = e;
	return OK;
}
Status Dequeue(queue *q,int *e)
{
	if(q->rear == q->front)
		return ERROR;
	*e = *q->front++;
	q->qsize--;
	return OK;
}
int main()
{
	queue q;
	QElemType e,*p;
	if(q_init(&q))
	{
		printf("顺序队列创建成功!\n");
	}
	Enqueue(&q,1);
	Enqueue(&q,2);
	Enqueue(&q,3);
	Enqueue(&q,4);
	Enqueue(&q,5);
	p = q.front;
	printf("顺序队列里面的数据为:\n");
	while(p < q.rear)
	    printf("%d ",*p++);
	Dequeue(&q,&e);
	printf("\n被删除的元素:\n");
	printf("%d\n",e);
	p=q.front;
	printf("删除队头后的数据为:\n");
	while(p<q.rear)
	     printf("%d ",*p++);
	printf("\n");
	return 0;
}

运行结果如下图所示：在这里插入图片描述

2.3 队列的链式存储结构

1.队列的链式存储

队列的链式表示称为链队列，实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。

队列的不带头结点的链式存储示意图如下图所示：在这里插入图片描述

队列的链式存储类型代码描述如下所示：

typedef struct{  //链式队列结点
   ElemType data;
   struct LinkNode *next;
}LinkNode;
typedef struct{  //链式队列
   LinkNode *front,*rear;  //队列的队头和队尾指针
}LinkQueue;

当 Q.front == NULL 且 Q.rear == NULL 时，链式队列为空。

出队时，首先判断队是否为空，若不空，则取出队头元素，将其从链表中移除，并让 Q.front 指向下一个结点（若该结点为最后一个结点，则令 Q.front 和 Q.rear 都为 NULL）。入队时，建立一个新结点，将新结点插入到链表的尾部，并改让 Q.rear 指向这个新插入的结点（若原队列为空队，则另 Q.front 也指向该结点）。

由于不带头结点的链式队列在操作上比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，实现插入和删除相统一。带头结点和不带头结点的链式队列如下图所示：

优点：用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。

2.链式队列的基本操作

（1）初始化

 void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));//建立头结点
    Q.front->next =NULL; //初始为空

（2）判队空

 bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear) 
       return true;
    else
       return false;
 }

（3）入队

 void EnQueue(LinkQueue &Q，ElemTyepe x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x; //创建新结点，插入到链尾
    s->next=null;
    Q.rear->next=s;
    Q.rear=s;
 }

（4）出队

 bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear) //空队
       return false;
    LinkNode *p =Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
       Q.rear=Q.front;//若原队列中只有一个结点，删除后变空
    free(p);
    return true;
 }

3.链队列示例代码

链队列的操作：链队列的初始化、入链队列、链队列队头元素出链队列以及显示链队列所有数据元素的示例代码如下所示：

#include<stdio.h>
#include<stdlib.h>
#define OK 1;
#define ERROR 0;

typedef int QElemType;
typedef int Status;

typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct 
{
	QueuePtr rear;
	QueuePtr front;
}LinkQueue;

Status InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)
		exit(0);
	Q.front->next=NULL;
	return OK;
}

Status EnQueue(LinkQueue &Q,QElemType e)
{
	QueuePtr p;
	p=(QueuePtr)malloc(sizeof(QNode));
	if(!p)
		exit(0);
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}

Status displayQueue(LinkQueue &Q)
{
	QueuePtr rear,front;
	front=Q.front->next;
	rear=Q.rear;
	if(front==rear)
	{
		printf("链队列为空!");
		return OK;
	}
	while(front!=NULL)
	{
		printf("%d\t",front->data);
		front=front->next;
	}
	printf("\n");
	return OK;
}

Status distoryQueue(LinkQueue &Q)
{
	while(Q.front!=NULL)
	{
		Q.rear=Q.front->next;
		free(Q.front);
		Q.front=Q.rear;
	}
	return OK;
}

Status DeQueue(LinkQueue &Q,QElemType &e)
{
	QueuePtr p;
	if(Q.front==Q.rear)
		return ERROR;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;
	free(p);
	return OK;
}

int main()
{
	LinkQueue Q;
	InitQueue(Q);
	printf("链队列中输入三个数据:\n");
	printf("10\t20\t30");
	EnQueue(Q,10);
	EnQueue(Q,20);
	EnQueue(Q,30);
	printf("\n输出链队列中的三个数据:\n");
	displayQueue(Q);
	int e;
	printf("链队列对头元素出队:");
	DeQueue(Q,e);
	printf("出队的元素为:e=%d\n\n",e);
	printf("初始化链队列:\n\n");
	distoryQueue(Q);
	return 0;
}

运行结果：

在这里插入图片描述

栈和队列

2、队列

2.1 队列的基本概念

2.2 队列的顺序存储结构

1.队列的顺序存储

2.循环队列

为了区分循环队列队空还是队满情况，有三种处理方式，其中第一种为常用的区分方式，重点掌握：

2.3 队列的链式存储结构

1.队列的链式存储

2.链式队列的基本操作

3.链队列示例代码

栈

数据结构与算法知识点汇总