队列概述及存储结构（顺序存储，链式存储，循环队列）代码实现_队列的存储结构

一、队列的基本概念

1.1 队列的定义

  队列(Queue) 简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队。删除元素称为出队或离队。这和我们日常生活中的排队是一致的，最早排队的也是最早离队的，其操
作的特性是先进先出(First In First Out, FIFO)，如：

队头(Front)： 允许删除的一-端，又称队首。
队尾(Rear)。： 允许插入的一-端。
空队列： 不含任何元素的空表。

1.2 队列常见的基本操作

InitQueue(&Q)： 初始化队列，构造-一个空队列 Q.
QueueEmpty(Q)： 判队列空，若队列Q为空返回true,否则返回false.
EnQueue(&Q,x)： 入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue (&Q, &x)： 出队，若队列e非空，删除队头元素，并用x返回。
GetHead(Q,&x)： 读队头元素，若队列Q非空，则将队头元素赋值给x。

注意： 栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈 和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

二、队列的顺序存储结构

  队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针:队头指针front 指向队头元素,队尾指针rear 指向队尾元素的下一个位置 (也可以让rear指向队尾元素、front 指向队头元素) 。
  顺序结构可描述为：

typedef struct SqQueue
{
	ElemType data[MaxSize];	//存放队列元素
	int front;	//队头指针
	int rear;	//队尾指针
}SqQueue;
1
2
3
4
5
6

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

队列的操作：

顺序存储结构存在的问题：

  出队a1、a2，则front指针指向下标为2的位置，rear 不变，如左图所示，再入队a5,此时front 指针不变，rear 指针移动到数组之外。嗯?数组之外，那么就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做 “假溢出”。如右图所示。

三、循环队列

  为了解决假溢出的问题，引入了循环队列，使其头尾相连。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

3.1 实现思路

  当队首指针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 (如图所示)

3.2 循环队列队空和队满的判断条件

  循环队列队空和队满的判断条件是什么呢?显然,队空的条件是Q.front==Q.rear
若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，如图(d1)所示，此时可以看出队满时也有Q.front==Q.rear。
  为了区分队空还是队满的情况，有三种处理方式:

1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，
   约定以 “队头指针在队尾指针的下一位置作为队满的标志”，如图(d2)所示。
   队满条件: (Q.rear+1) % MaxSize==Q.front
   队空条件仍为: Q.front==Q.rear。
   队列中元素的个数: (Q. rear-Q. front+MaxSize)各MaxSize.
2. 类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size==0;队满的条件为
   Q.size==MaxSize。这两种情况都有Q. front==Q. rear.
3. 类型中设置一个标志变量 flag，以区分是队满还是队空。flag 等于 0 时，若因删除导致
   Q.frontQ.rear ,则为队空; flag 等于 1 时，若因插入导致Q. frontQ. rear,则为队满。（常用）
   

3.3 循环队列的操作

#include<stdio.h>
#include<malloc.h>


#define MaxSize 20
typedef int ElemType;

typedef struct SqQueue
{
	ElemType *data;	//存放队列元素
	int front;	//队头指针
	int rear;	//队尾指针
}SqQueue;

void InitQueue(SqQueue *Q);	//初始化队列
bool isEmpty(SqQueue Q);	//判断队列是否为空
bool isFull(SqQueue Q);	//判断队列是否已满
bool EnQueue(SqQueue *Q,ElemType e);	//入队
bool DeQueue(SqQueue *Q,ElemType *e);	//出队
void PrintQueue(SqQueue pQ);

int main()
{
	SqQueue Q;
	ElemType e;
	InitQueue(&Q);

	EnQueue(&Q,1);
	EnQueue(&Q,2);
	EnQueue(&Q,3);
	EnQueue(&Q,4);
	EnQueue(&Q,5);
	EnQueue(&Q,6);
	EnQueue(&Q,7);
	
	PrintQueue(Q);

	if(DeQueue(&Q,&e))
		printf("出队成功，出队元素为：%d\n",e);
	else
		printf("出队失败\n");

	PrintQueue(Q);

	return 0;
}


void InitQueue(SqQueue *Q)
{
	Q->data = (ElemType *)malloc(sizeof(ElemType)* MaxSize);
	Q->front = Q->rear = 0;
}


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

bool isFull(SqQueue Q)
{
	if((Q.rear + 1) % MaxSize == Q.front)
		return true;
	else
		return false;
}

bool EnQueue(SqQueue *Q,ElemType e)
{
	if((Q->rear + 1) % MaxSize == Q->front)
		return false;	//队满报错
	Q->data[Q->rear] = e;
	Q->rear = (Q->rear +1) % MaxSize;	//队尾指针加1取模
	return true;
}

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

void PrintQueue(SqQueue pQ)
{
	int i = pQ.front;

	while(i != pQ.rear)
	{
		printf("%d ",pQ.data[i]);
		i = (i+1) % MaxSize;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

四、队列的链式存储结构

4.1 队列链式存储

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

可描述为：

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

typedef struct			/* 队列的链表结构 */
{
   QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
1
2
3
4
5
6
7
8
9
10

  当Q. front==NULL且Q.rear==NULL时，链式队列为空。
  出队时，首先判断队是否为空,若不空,则取出队头元素,将其从链表中摘除，并让Q. front
指向下一个结点(若该结点为最后一个结点，则置Q. front和Q. rear都为NULL)。入队时,
建立一个新结点，将新结点插入到链表的尾部，并改让Q. rear指向这个新插入的结点(若原队列为空队，则令Q. front也指向该结点)。
  不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了。

使用场景： 用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式
队列，这样就不会出现存储分配不合理和“溢出”的问题。

4.2 链式队列的基本操作

4.2.1 初始化

void InitQueue(LinkQueue *Q)
{ 
	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
	Q->front->next=NULL;
}
1
2
3
4
5

4.2.2 判队空

bool IsEmpty(LinkQueue Q)
{ 
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7

4.2.3 入队

  入队操作时，其实就是在链表尾部插入结点，如图所示：

其代码如下：

bool EnQueue(LinkQueue *Q,ElemType e)
{ 
	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
	s->data=e;
	s->next=NULL;
	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
	Q->rear=s;		/* 把当前的s设置为队尾结点，rear指向s，见图中② */
	return true;
}
1
2
3
4
5
6
7
8
9

4.2.4 出队

  出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear 指向头结点，如图所示：

其代码如下：

bool DeQueue(LinkQueue *Q,ElemType *e)
{
	QueuePtr p;
	if(Q->front==Q->rear)
		return false;
	p=Q->front->next;		/* 将欲删除的队头结点暂存给p，见图中① */
	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
	if(Q->rear==p)		/* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
		Q->rear=Q->front;
	free(p);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.3 队列链式结构完整代码

#include<stdio.h>
#include<malloc.h>

#define MaxSize 10;
typedef int ElemType;

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

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


/* 构造一个空队列Q */
void InitQueue(LinkQueue *Q)
{ 
	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
	Q->front->next=NULL;
}

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

/* 插入元素e为Q的新的队尾元素 */
bool EnQueue(LinkQueue *Q,ElemType e)
{ 
	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
	s->data=e;
	s->next=NULL;
	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
	Q->rear=s;		/* 把当前的s设置为队尾结点，rear指向s，见图中② */
	return true;
}



/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
bool DeQueue(LinkQueue *Q,ElemType *e)
{
	QueuePtr p;
	if(Q->front==Q->rear)
		return false;
	p=Q->front->next;		/* 将欲删除的队头结点暂存给p，见图中① */
	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
	if(Q->rear==p)		/* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
		Q->rear=Q->front;
	free(p);
	return true;
}


void PrintQueue(LinkQueue Q)
{
	QueuePtr p;
	p=Q.front->next;
	while(p)
	{
		 printf("%d ",p->data);
		 p=p->next;
	}
	printf("\n");
}

int main()
{
	LinkQueue Q;
	ElemType e;

	InitQueue(&Q);

	EnQueue(&Q,1);
	EnQueue(&Q,2);
	EnQueue(&Q,3);
	EnQueue(&Q,4);
	EnQueue(&Q,5);
	EnQueue(&Q,6);
	EnQueue(&Q,7);
	
	PrintQueue(Q);

	if(DeQueue(&Q,&e))
		printf("出队成功，出队元素为：%d\n",e);
	else
		printf("出队失败\n");

	PrintQueue(Q);


	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101