当前位置:   article > 正文

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

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.出队时给出了两种方法,法二看上去,每次出队都会使得队容量减少,但是在某些情况下这也是很有用的特性。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/706949
推荐阅读
相关标签
  

闽ICP备14008679号