1.3 队列的顺序存储实现和链式存储实现（C语言）_队列的顺序存储和链式存储的实现详细

顺序存储实现源码

• 数组的方式实现队列的顺序存储。用一个一维数组来存储队列的数据，对队列执行操作时，插入和删除分别是对数组头和数组尾进行操作，所以还要有两个指针变量来指示数组的头和尾

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define MaxSize 5       /* 存储空间初始分配量 */

typedef int ElementType;  //给int取别名
typedef int Position;
struct QNode {
	ElementType *Data;     /* 存储元素的数组 */
	Position Front, Rear;  /* 队列的头、尾指针 */
};
typedef struct QNode *Queue;

/*生成长度为MaxSize的空队列*/
Queue CreateQueue()
{
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
	Q->Front = Q->Rear = 0;

	return Q;
}

/*判断队列Q是否已满*/
bool IsFull(Queue Q)
{
	return ((Q->Rear + 1) % MaxSize == Q->Front);
}

/*若队列未满，将数据元素X插入队列Q中*/
bool AddQ(Queue Q, ElementType X)
{
	if (IsFull(Q)) {
		printf("队列满");
		return false;
	}
	else {	
		/* Rear指针向后移一位置，若到最后则转到数组头部 */
		Q->Rear = (Q->Rear + 1) % MaxSize;//循环队列：求余函数
		/* 将元素X赋值给队尾 */
		Q->Data[Q->Rear] = X;//注意这里Q->Rear=1，也就是说队尾是1，从第一位开始赋值
		return true;
	}
}

/*判断队列Q是否为空*/
bool IsEmpty(Queue Q)
{
	return (Q->Front == Q->Rear);
}

/*若队列不空，将队头数据从队列中删除并返回*/
ElementType DeleteQ(Queue Q)
{
	if (IsEmpty(Q)) {
		printf("队列空");
		return ERROR;
	}
	else {
		Q->Front = (Q->Front +1) % MaxSize;
		return  Q->Data[Q->Front];
	}
}

/* 从队头到队尾依次对队列Q中每个元素输出 */
ElementType Queueshow(Queue Q)
{
	int i;
	i = Q->Front;
	if (IsEmpty(Q)) {
		printf("栈是空的");
	}else
	while ((i + Q->Front) != Q->Rear)
	{
		i = (i +1) % MaxSize; //初次时，i=1，从第一位开始输出
		printf("%d\t",Q->Data[i]);	
	}
	printf("\n");
	return 0;
}

/* 返回Q的元素个数，也就是队列的当前长度 */
int QueueLength(Queue Q)
{
	return  (Q->Rear - Q->Front + MaxSize) % MaxSize;
}

int  show(Queue Q) {
	printf("此时队列的长度为%d,此时队头Front指向的元素为%d,此时队尾Rear指向的元素为%d\n", QueueLength(Q),Q->Front, Q->Rear);

	return 0;
}


int main() {
	Queue q;//结构体指针 
	int i = 0;
	q = CreateQueue();
	printf("此时队列的MaxSize大小为%d\n", MaxSize);
	
	printf("此时队列q的元素有\n");
	Queueshow(q);
	show(q);

	printf("若队列未满，将元素X插入队列\n");
    for (i = 1; i < MaxSize; i++) {
		printf("将%d插入队列q为新的队尾元素\n", i);
		AddQ(q, i);
	}
	show(q);

	printf("此时堆栈q的元素有\n");
	Queueshow(q);
	printf("若队列不空，删除并返回队头元素\n");
	for (i = 1; i < MaxSize; i++) {
		printf("将队头元素%d从队列q中删除并返回\n", DeleteQ(q));
	}
	show(q);

	printf("此时堆栈q的元素有\n");
	Queueshow(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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

运行

此时队列的MaxSize大小为5
此时队列q的元素有
栈是空的
此时队列的长度为0,此时队头Front指向的元素为0,此时队尾Rear指向的元素为0
若队列未满，将元素X插入队列
将1插入队列q为新的队尾元素
将2插入队列q为新的队尾元素
将3插入队列q为新的队尾元素
将4插入队列q为新的队尾元素
此时队列的长度为4,此时队头Front指向的元素为0,此时队尾Rear指向的元素为4
此时堆栈q的元素有
1       2       3       4
若队列不空，删除并返回队头元素
将队头元素1从队列q中删除并返回
将队头元素2从队列q中删除并返回
将队头元素3从队列q中删除并返回
将队头元素4从队列q中删除并返回
此时队列的长度为0,此时队头Front指向的元素为4,此时队尾Rear指向的元素为4
此时堆栈q的元素有
栈是空的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

顺环队列

1. 使用额外标记：Size或者tag域

• 增加一个额外的标记，Size来记录当前队列元素的个数，删除元素-1，加入元素+1，由Size为0或n得知队列空满
• 插入元素的时候，Tag设为1，删除一个元素的时候tag等于0，tag代表最后一次操作是插入还是删除，此时就知道队列到底是空或满

2. 仅使用n-1个数组空间

• 另外一种方法是，数组大小虽然是n，但是不放满，最多只放n-1个元素，就像上面的例子，数组有6，但是我最多放5个

链式存储实现源码

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define NULL 0
#define MaxSize 5       /* 存储空间初始分配量 */

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

typedef struct Node *PtrToNode;
struct Node {     /* 队列中的结点结构 */ 
	ElementType Data;
	PtrToNode Next;
};
typedef PtrToNode Position;

struct QNode {      /* 队列的链表结构 */
	Position Front, Rear;  /* 队列的头、尾指针 */
};
typedef struct QNode *Queue;

/* 构造一个空队列Q */
Queue InitQueue()
{
	Queue Q=(Queue)malloc(sizeof(struct QNode));
	Q->Front = Q->Rear = (Position)malloc(sizeof(Node));
	if (!Q->Front)
		exit(false);//正常退出
	Q->Front->Next = NULL;
	return Q;
}
/* 销毁队列Q */
void DestroyQueue(Queue Q)
{
	while (Q->Front)
	{
		Q->Rear = Q->Front->Next;
		free(Q->Front);
		Q->Front = Q->Rear;
	}

}

/* 将Q清为空队列 */
Queue ClearQueue(Queue Q)
{
	Position p, q;
	Q->Rear = Q->Front;
	p = Q->Front->Next;
	Q->Front->Next = NULL;
	while (p)
	{
		q = p;
		p = p->Next;
		free(q);
	}
	return Q;
}

/*判断队列Q是否为空*/
bool IsEmpty(Queue Q)
{
	return (Q->Front == NULL);
}

/* 插入元素e为Q的新的队尾元素 */
ElementType EnQueue(Queue Q, ElementType e)
{
	Position s = (Position)malloc(sizeof(Node));
	if (!s) /* 存储分配失败 */
		exit(false);
	s->Data = e;
	s->Next = NULL;
	Q->Rear->Next = s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继 */
	Q->Rear = s;		/* 把当前的s设置为队尾结点，rear指向s */
	return 0;
}

/*若队列不空，将队头数据从队列中删除并返回*/
ElementType DeleteQ(Queue Q)
{
	Position FrontCell;
	ElementType FrontElem;

	if (IsEmpty(Q)) {
		printf("队列空");
		return ERROR;
	}
	else {
		FrontCell = Q->Front->Next; /*将欲删除的队头结点暂存给新建结点*/
		FrontElem = FrontCell->Data;/* 将欲删除的队头结点的值赋值给新建变量*/
		Q->Front->Next = FrontCell->Next;/* 将原队头结点的后继FrontCell->next赋值给头结点后继*/
		if (Q->Front == Q->Rear) /* 若队列只有一个元素 */
			Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */

		free(FrontCell);  /* 释放被删除结点空间  */
		return  FrontElem;
	}
}

/* 从队头到队尾依次对队列Q中每个元素输出 */
ElementType Queueshow(Queue Q)
{
	Position p;
	p = Q->Front->Next;
	if (Q->Front->Next==NULL) {
		printf("队列是空的");
		return false;
	}else
	while (p)
	{
		printf("%d\t",p->Data);
		p = p->Next;
	}
	printf("\n");
	return 0;
}

/* 返回Q的元素个数，也就是队列的当前长度 */
int QueueLength(Queue Q)
{
	int i = 0;
	Position p ;
	p = Q->Front;
	if (p->Next == NULL) {
		//printf("队列是空的\n");
		return false;
	}
	else
	while (Q->Rear != p)
	{
		i++;
		p = p->Next;
	}
	return i;
}

void  show(Queue Q) {
	Position p,p2;
	if (Q->Front == Q->Rear|| Q->Front->Next==NULL)
	{
		printf("链队列为空，无法返回队头数据\n"); 
	}else
	{
		p = Q->Front->Next;//队头
		printf( "此时队头Front指向的元素为%d,\n" ,p->Data );
		p2 = Q->Rear;
		printf("此时队尾Rear指向的元素为%d\n", p2->Data);
	}
	printf("此时队列的长度为%d,\n", QueueLength(Q));
}


int main() {
	Queue q;//结构体指针 
	int i = 0;
	q = InitQueue();
	ClearQueue(q);
	printf("此时队列的MaxSize大小为%d\n", MaxSize);
	printf("此时队列q的元素有\n");
	Queueshow(q);
	show(q);

	printf("若队列未满，将元素X插入队列\n");
    for (i = 1; i < MaxSize; i++) {
		printf("将%d插入队列q为新的队尾元素\n", i);
		EnQueue(q, i);
	}
	printf("此时队列q的元素有\n");
	Queueshow(q);
	show(q);

	printf("若队列不空，删除并返回队头元素\n");
	for (i = 1; i < MaxSize; i++) {
		printf("将队头元素%d从队列q中删除并返回\n", DeleteQ(q));
	}
	printf("此时队列q的元素有\n");	
	Queueshow(q);
	show(q);
	DestroyQueue(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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

运行

此时队列的MaxSize大小为5
此时队列q的元素有
队列是空的链队列为空，无法返回队头数据
此时队列的长度为0,
若队列未满，将元素X插入队列
将1插入队列q为新的队尾元素
将2插入队列q为新的队尾元素
将3插入队列q为新的队尾元素
将4插入队列q为新的队尾元素
此时队列q的元素有
1       2       3       4
此时队头Front指向的元素为1,
此时队尾Rear指向的元素为4
此时队列的长度为4,
若队列不空，删除并返回队头元素
将队头元素1从队列q中删除并返回
将队头元素2从队列q中删除并返回
将队头元素3从队列q中删除并返回
将队头元素4从队列q中删除并返回
此时队列q的元素有
队列是空的链队列为空，无法返回队头数据
此时队列的长度为0,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

链队列示意图

int data[]与int *data区别(c中数组名可以看成指针)

做形参的时候，int data[]与int *data无任何区别。

int data[]申请的是一个静态数组，在设计时就需要考虑其大小，这样带来的缺点是空间大小固定，导致空间不够用或者浪费
int *data申请的是一个指针变量(申请一个路标)，然后通过malloc函数申请一片空间(在建设工程中申请一片空地，这样可以按照需求确定大小，然后让路标指向这片空地)，得到动态数组(即申请的空间可以由变量大小确定)。

data[i]本来就是*(data+i)
如果要访问int data[5]实际上是先获得这个数组的头指针int *data，然后在内存中偏移5个int的数据长度int *(data+5)，也就是从代码的理解上，可以认为int data[5]与 int *(data+5)等价

int *data为动态数组（动态内存分配方式）

• 区别于数组的静态内存分配
• 数组每一个元素类型都是统一的，且连续不间断的

动态内存分配是指重新分配一个更大的空间，把原来分配的空间释放掉。
举个例子，就是你和朋友两人去住旅馆，开了一个双人间，但是后来你还有一个朋友要来，就去开了个三人间，并把原来的双人间退掉。

数组与链表

• 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

数组优点
通过下标随机访问的时间复杂度是O(1)，查找快，支持动态扩容，即动态数组

数组缺点
插入、删除数据慢，因为数组连续的内存空间，所以在插入一个数据的时候会使插入位置后面的每个数据都向后位移一个位置，所以比较低效，删除同理，会使删除位置之后的每个数据向前位移一个
查询某个元素是否存在或者删除、插入某个元素时需要遍历整个数组，耗费 O(n) 的时间
操作不当会越界

• 链表是有一系列不必在内存中连续的结构组成，通过指针将一组零散的内存块串联起来使用

链表优点
在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素

链表缺点
不能像按索引在数组中那样随机访问任何元素。 例如，如果我们要访问位置n处的节点，则必须遍历它之前的所有节点。 因此，访问节点所需的时间很大。
在链表中，反向遍历确实很困难。 在双链表的情况下，它比较容易，但是向后指针需要额外的内存，因此浪费了内存。

数组与链表的比较

• (静态)数组从栈中分配空间，方便，可操作性小
• (动态)数组从堆中分配空间，管理麻烦
• 链表从堆中分配空间

动态数组是重新分配一块更大的空间（所以动态数组是连续的）
Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
链表是一块一块的分配（所以不连续）
Position s = (Position)malloc(sizeof(Node));

数组（顺序存储）与链表（链式存储）的使用

（1）若线性表的总长度基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素。

采用顺序存储结构，其插入和删除操作需要移动大量元素，但可按数组下标直接查找元素。

（2）如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。

采用链式存储结构，链表的长度不需要限制，可动态发生变化。