队列的链式和顺序存储及其相关操作_c++采用链式存储(有头结点)实现队列的初始化、入队、出队、取队头元素操作。

一、链式存储

1.结构体的定义

typedef struct Queue_Node
{
	DataType data;
	Queue_Node* next;
}*QueueNodePtr;

typedef struct Link_Queue
{
	QueueNodePtr front;
	QueueNodePtr rear;
}*LinkQueuePtr;
1
2
3
4
5
6
7
8
9
10
11

DataType是操作者自己定义的数据类型。

2.初始化

LinkQueuePtr InitQueue()
{
	LinkQueuePtr resultPtr = new struct Link_Queue;

	QueueNodePtr headerPtr = new struct Queue_Node;

	headerPtr->next = NULL;

	resultPtr->front = resultPtr->rear = headerPtr;

	return resultPtr;
}
1
2
3
4
5
6
7
8
9
10
11
12

初始化构建队列数据结构

3.入队

void EnterQueue(LinkQueuePtr paraQueuePtr, int paraElement) {
	//Step 1. Create a new node
	QueueNodePtr tempNodePtr = new struct Queue_Node;

	tempNodePtr->data = paraElement;
	tempNodePtr->next = NULL;

	//Step 2. Link to the existing rear
	paraQueuePtr->rear->next = tempNodePtr;

	//Step 3. It is the new rear
	paraQueuePtr->rear = tempNodePtr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.出队

DataType DeleteQueue(LinkQueuePtr paraQueuePtr) {
	int resultValue;
	QueueNodePtr tempNodePtr = NULL;

	//Step 1. Is the queue empty?
	if (paraQueuePtr->front == paraQueuePtr->rear) 
	{
		cout << "The queue is empty." << endl;
		return -1;
	}

	//Step 2. Change the queue.
	tempNodePtr = paraQueuePtr->front->next;
	resultValue = tempNodePtr->data;
	paraQueuePtr->front->next = paraQueuePtr->front->next->next;

	//Step 2.1 Deal with the case of only one node
	if (paraQueuePtr->rear == tempNodePtr) 
		paraQueuePtr->rear = paraQueuePtr->front;

	//Step 3. Free space.
	 free(tempNodePtr);

	//Step 4. Return.
	return resultValue;
}
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

5.打印元素

void outputLinkQueue(LinkQueuePtr paraQueuePtr) {
	QueueNodePtr tempPtr = paraQueuePtr->front->next;

	while (tempPtr != NULL) 
	{
		printf("%d ", tempPtr->data);
		tempPtr = tempPtr->next;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10

6.完整代码

#include <stdio.h>
#include <iostream>

using namespace std;

typedef int DataType; //队列中元素类

typedef struct Queue_Node
{
	DataType data;
	Queue_Node* next;
}*QueueNodePtr;

typedef struct Link_Queue
{
	QueueNodePtr front;
	QueueNodePtr rear;
}*LinkQueuePtr;

LinkQueuePtr InitQueue()
{
	LinkQueuePtr resultPtr = new struct Link_Queue;

	QueueNodePtr headerPtr = new struct Queue_Node;

	headerPtr->next = NULL;

	resultPtr->front = resultPtr->rear = headerPtr;

	return resultPtr;
}

void EnterQueue(LinkQueuePtr paraQueuePtr, int paraElement) {
	//Step 1. Create a new node
	QueueNodePtr tempNodePtr = new struct Queue_Node;

	tempNodePtr->data = paraElement;
	tempNodePtr->next = NULL;

	//Step 2. Link to the existing rear
	paraQueuePtr->rear->next = tempNodePtr;

	//Step 3. It is the new rear
	paraQueuePtr->rear = tempNodePtr;
}

DataType DeleteQueue(LinkQueuePtr paraQueuePtr) {
	int resultValue;
	QueueNodePtr tempNodePtr = NULL;

	//Step 1. Is the queue empty?
	if (paraQueuePtr->front == paraQueuePtr->rear) 
	{
		cout << "The queue is empty." << endl;
		return -1;
	}

	//Step 2. Change the queue.
	tempNodePtr = paraQueuePtr->front->next;
	resultValue = tempNodePtr->data;
	paraQueuePtr->front->next = paraQueuePtr->front->next->next;

	//Step 2.1 Deal with the case of only one node
	if (paraQueuePtr->rear == tempNodePtr) 
		paraQueuePtr->rear = paraQueuePtr->front;

	//Step 3. Free space.
	 free(tempNodePtr);

	//Step 4. Return.
	return resultValue;
}

void outputLinkQueue(LinkQueuePtr paraQueuePtr) {
	QueueNodePtr tempPtr = paraQueuePtr->front->next;

	while (tempPtr != NULL) 
	{
		printf("%d ", tempPtr->data);
		tempPtr = tempPtr->next;
	}
	cout << endl;
}

void testLinkQueue() {
	LinkQueuePtr tempQueuePtr;
	tempQueuePtr = InitQueue();
	EnterQueue(tempQueuePtr, 10);
	EnterQueue(tempQueuePtr, 30);
	EnterQueue(tempQueuePtr, 50);

	outputLinkQueue(tempQueuePtr);

	cout << endl;

	printf("dequeue gets %d\r\n", DeleteQueue(tempQueuePtr));
	printf("dequeue gets %d\r\n", DeleteQueue(tempQueuePtr));
	printf("dequeue gets %d\r\n", DeleteQueue(tempQueuePtr));
	printf("dequeue gets %d\r\n", DeleteQueue(tempQueuePtr));

	outputLinkQueue(tempQueuePtr);
}

int main()
{
	testLinkQueue();

	system("pause");
	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

7.运行结果

二、顺序存储

1.结构体的定义

typedef struct Queue
{
	int queue[MaxSize];
	int front;  //队头指针  
	int rear;  //队尾指针 
}SeQueue;
1
2
3
4
5
6

这里没有采用地址指针，采用下标指针更好理解一点。

2.初始化

//初始化队列 
void InitQueue(SeQueue *SQ)
{
	if(!SQ)
		return ;
		
	SQ->front = SQ->rear = 0;//队头和队尾“指针 ”同时置为0 
}
1
2
3
4
5
6
7
8

3.判断队列是否已满

//判断队列是否已满
int IsFull(SeQueue *SQ)
{
	if(!SQ)
		return 0;
		
	if(SQ->rear == MaxSize)
		return 1;
	else
		return 0;
} 
1
2
3
4
5
6
7
8
9
10
11

4.判断队列是否为空

//判断队列是否为空
int IsEmpty(SeQueue *SQ)
{
	if(!SQ)
		return 0;
	
	if(SQ->front == SQ->rear)
		return 1;
	else 
		return 0;
} 
1
2
3
4
5
6
7
8
9
10
11

5.入队

//入队，插入元素
int EnterQueue(SeQueue *SQ,int data)
{
	if(!SQ)
		return 0;
		
	if(IsFull(SQ))
	{
		cout<<"无法插入:"<<data<<",队列已满!"<<endl;
		return 0; 
	}else
	{
		SQ->queue[SQ->rear] = data;//能且只能在队尾插入data
		SQ->rear++;//队尾指针向后移动一位 
	}
	return 1;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

6.1 出队：(法一）

//出队法一：将队列的队头元素data出队，后面元素向前移动
int OutOfQueue(SeQueue *SQ,int * data,int num)
{
	if(!SQ||IsEmpty(SQ))
	{
		cout<<"队列为空!"<<endl;
		return 0; 
	}
	
	if(!data)
	{
		return 0;
	}
	
	*data = SQ->queue[SQ->front];
	
	int i=SQ->front+1;
	
	//后面元素向前覆盖
	for(i=SQ->front;i<SQ->rear-1;i++)
	{
		SQ->queue[i] = SQ->queue[i+1];
	} 
	//出队一个，队尾指针向前移一个 
	SQ->rear--;
	
	return 1;
} 
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

法一是先整体移动元素，然后尾指针-1.

6.2 出队：(法二)

//出队法二: 元素不移动，头指针移动。但是队列长度会随之变小
int OutOfQueue2(SeQueue *SQ,int *data,)
{
	if(!SQ||IsEmpty(SQ))
	{
		cout<<"队列为空!"<<endl;
		return 0; 
	}
	
	if(SQ->front>=MaxSize)
	{
		cout<<"队列已到尽头!"<<endl;
		return 0;
	} 
	
	*data = SQ->queue[SQ->front];//出队元素的值 
	SQ->front = (SQ->front)+1;//队首指针后移一位 
	
	return 1;
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.参数采用 int *data,其实和 int &data是一个意思，都是为了把删除的元素带出去。
2.采用头指针后移的方式，可能会造成“假溢出”。

7.获取队首元素

//获取队首元素，但不出队
int GetHead(SeQueue *SQ,int *data)
{
	if(!SQ||IsEmpty(SQ))
	{
		cout<<"队列为空!"<<endl;
		return 0; 
	}
	return *data = SQ->queue[SQ->front]; 
} 

1
2
3
4
5
6
7
8
9
10
11

8.获取队长

//获取队列中元素的个数 
int GetLength(SeQueue *SQ) 
{
	if(!SQ)
		return 0;
		
	return SQ->rear - SQ->front;
}
1
2
3
4
5
6
7
8

9.打印

//打印队列中的各元素
void PrintQueue(SeQueue *SQ)
{
	if(!SQ)
		return ;
	
	int i = SQ->front;
	while(i<SQ->rear)
	{
		cout<<setw(4)<<SQ->queue[i++];
	}
	
} 
1
2
3
4
5
6
7
8
9
10
11
12
13

setw(n) n 表示宽度

10.清空队列

//清空队列
int CleanQueue(SeQueue *SQ) 
{
	if(!SQ)
		return 0;
	
	SQ->front = SQ->rear = 0;//头指针，尾指针 同时指向队首 
	return 1;
}
1
2
3
4
5
6
7
8
9

11.完整代码

#include <iostream>
#include <stdio.h>
//#include <assert.h>

#include <iomanip>

using namespace std;

#define MaxSize 5//队列的最大容量 


typedef struct Queue
{
	int queue[MaxSize];
	int front;  //队头指针  （不是真正意义上的指针 ） 
	int rear;  //队尾指针 
}SeQueue;

//初始化队列 
void InitQueue(SeQueue *SQ)
{
	if(!SQ)
		return ;
		
	SQ->front = SQ->rear = 0;//队头和队尾“指针 ”同时置为0 
}

//判断队列是否已满
int IsFull(SeQueue *SQ)
{
	if(!SQ)
		return 0;
		
	if(SQ->rear == MaxSize)
		return 1;
	else
		return 0;
} 

//判断队列是否为空
int IsEmpty(SeQueue *SQ)
{
	if(!SQ)
		return 0;
	
	if(SQ->front == SQ->rear)
		return 1;
	else 
		return 0;
} 

//入队，插入元素
int EnterQueue(SeQueue *SQ,int data)
{
	if(!SQ)
		return 0;
		
	if(IsFull(SQ))
	{
		cout<<"无法插入:"<<data<<",队列已满!"<<endl;
		return 0; 
	}else
	{
		SQ->queue[SQ->rear] = data;//能且只能在队尾插入data
		SQ->rear++;//队尾指针向后移动一位 
	}
	return 1;
} 

//出队法一：将队列的队头元素data出队，后面元素向前移动
int OutOfQueue(SeQueue *SQ,int * data,int num)
{
	if(!SQ||IsEmpty(SQ))
	{
		cout<<"队列为空!"<<endl;
		return 0; 
	}
	
	if(!data)
	{
		return 0;
	}
	
	*data = SQ->queue[SQ->front];
	
	int i=SQ->front+1;
	
	//后面元素向前移动
	 
	/*法一*/ 
//	for(i=SQ->front+1;i<SQ->rear;i++)
//	{
//		SQ->queue[i-1] = SQ->queue[i];
//	}
	
	/*法二*/ 
	for(i=SQ->front;i<SQ->rear-1;i++)
	{
		SQ->queue[i] = SQ->queue[i+1];
	} 
	//出队一个，队尾指针向前移一个 
	SQ->rear--;
	
	return 1;
} 

//出队法二: 元素不移动，头指针移动。但是队列长度会随之变小
int OutOfQueue2(SeQueue *SQ,int * data,int num)
{
	if(!SQ||IsEmpty(SQ))
	{
		cout<<"队列为空!"<<endl;
		return 0; 
	}
	
	if(SQ->front>=MaxSize)
	{
		cout<<"队列已到尽头!"<<endl;
		return 0;
	} 
	
	*data = SQ->queue[SQ->front];//出队元素的值 
	SQ->front = (SQ->front)+1;//队首指针后移一位 
	
	return 1;
}  

//获取队首元素，但不出队
int GetHead(SeQueue *SQ,int *data)
{
	if(!SQ||IsEmpty(SQ))
	{
		cout<<"队列为空!"<<endl;
		return 0; 
	}
	return *data = SQ->queue[SQ->front]; 
} 

//打印队列中的各元素
void PrintQueue(SeQueue *SQ)
{
	if(!SQ)
		return ;
	
	int i = SQ->front;
	while(i<SQ->rear)
	{
		cout<<setw(4)<<SQ->queue[i++];
	}
	
} 

//清空队列
int CleanQueue(SeQueue *SQ) 
{
	if(!SQ)
		return 0;
	
	SQ->front = SQ->rear = 0;//头指针，尾指针 同时指向队首 
	return 1;
}

//获取队列中元素的个数 
int GetLength(SeQueue *SQ) 
{
	if(!SQ)
		return 0;
		
	return SQ->rear - SQ->front;
}

int main()
{
	SeQueue *SQ = new SeQueue;
	
	int /*DataType*/data,i;
	
	
	//初始化队列
	 InitQueue(SQ);
	 
	//入队
	int num;
	cout<<"请输入元素的个数:";
	cin>>num;
	for(i=0;i<num;i++)
	{
		EnterQueue(SQ,i);
	} 
	
	//打印队列中的元素
	cout<<endl<<"队列的元素:";
	PrintQueue(SQ);
	printf("\n队列中的元素个数为:%d\n",GetLength(SQ));
	cout<<endl;
	
	//出队 
	cout<<"请输入出队的次数:";
	cin>>num;
	 
	if(num>MaxSize)
		cout<<endl<<"出队次数过多!"<<endl<<endl;
	 for(i=0;i<num;i++)
	 {
	 	if(OutOfQueue2(SQ,&data,num))
	 	{
	 		cout<<"出队的元素是:"<<data<<endl;
	 		printf("队列中的元素个数为:%d\n",GetLength(SQ));
	 		cout<<"队列:"; 
	 		PrintQueue(SQ);
	 		cout<<endl<<endl;
	 	}else
	 		cout<<"出队失败!!!"<<endl;
	 }
	 
	 //清空队列
	 if(CleanQueue(SQ))
	 	cout<<"销毁成功!";
	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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220

12.测试结果

三、总结

1.队列也是一个经典的数据结构，关键是抓住先进先出，后进后出的方式。
2.出队时给出了两种方法，法二看上去，每次出队都会使得队容量减少，但是在某些情况下这也是很有用的特性。