数据结构与算法 队列(顺序表实现)

简单描述：队列是一种受限制的线性结构(先进先出)，它只能在表的前端进行删除，在表的后端进行插入。

一、用顺序表实现

1.初始化队列，判断队列是否为空，是否为满

宏定义设置这个队列的最大容量，重新定义类据类型作为队列的数据类型，这样可方便修改，结构体队列中除数据区外，还定义了两个整型变量front、rear，分别用来表示该队列的首部位置和尾部位置（当前队列最后已有元素位置的下一个位置），队列的各种方法实现可由这两个变量控制实现。

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

typedef int DataType;  //队列中元素类型(方便修改)

//队列结构体
typedef struct Queue {
	DataType queue[MaxSize]; //队列数据存储区
	int front;    //队头(指向队列中的第一个元素的位置)
	int rear;     //队尾(指向队列中的最后一个元素的位置)
}SeqQueue;

//队列初始化，将队列初始化为空队列
void InitQueue(SeqQueue *SQ) {
	if (!SQ) return;//判断队列是否为空
	
	SQ->front = 0;  //将队头设置为0
	SQ->rear = 0;   //将队尾设置为0
}

//判断队列是否满了
bool IsFull(SeqQueue *SQ) {
	if (!SQ) return false;

	if (SQ->rear == MaxSize) { //尾部位置与队列容量相等，队列已满
		return true;
	}
	return false;
}

//判断队列是否为空
bool IsEmpty(SeqQueue* SQ) {
	if (!SQ) return false;

	if (SQ->front == SQ->rear) {//队列首部位置与队列尾部位置相等，则为空
		return true;
	}
	return false;
}

2.入队（添加元素）

//入队，将元素data插入到队列中
bool EnterQueue(SeqQueue* SQ, DataType data) {//data为要插入的数据
	if (IsFull(SQ)) {//判断队列是否已满
		cout << "队列已满，无法插入！" << endl;
		return false;
	}

	SQ->queue[SQ->rear] = data; //在队尾插入元素data
	SQ->rear++;  //插入元素后，队尾位置加1

	return true;
}

3.出队

方法一：

将首元素出队，后面的元素依次向前移一位。

//出队，将队列中队首的元素data出队，后面的元素依次向前移动
bool DeleteQueue(SeqQueue* SQ, DataType* data) {//data用来保存出队元素
	if (!SQ || IsEmpty(SQ)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!data) return false;

	*data = SQ->queue[SQ->front];//将出队元素保存到data中

	for (int i = SQ->front + 1; i < SQ->rear; i++) {//元素出队后，其他元素依次向前移一位
		SQ->queue[i - 1] = SQ->queue[i];
	}

	SQ->rear--;//出队一个，尾部减1
	return true;
}

方法二：

方法二的最大不同就在于，不需要大规模的移动，只需将队首后移一位即可，使队首下一个位置的元素成为新的队首。第二种方法看似比第一种方法要好，但是却有一个缺陷，就是当队首位置移动到队尾的时候，就不能再插入元素了，即当前队列为空队列。

//出队方法2：
//出队，将队列中队头的元素data出队，后将队首位置向后移一位(表示首位)
bool DeleteQueue2(SeqQueue* SQ, DataType* data) {
	if (!SQ || IsEmpty(SQ)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!data) return false;

	if (SQ->front >= MaxSize) { //判断首部元素位置是否大于或等于队列容量
		cout << "队列已到尽头" << endl;
		return false;
	}

	*data = SQ->queue[SQ->front];//出队元素保存到data中
	SQ->front = (SQ->front) + 1; //将队列首部向后移一位

	return true;
}

4.获取队列首元素，和队列长度

//获取队首元素
int GetHead(SeqQueue* SQ, DataType* data) {
	if (!SQ || IsEmpty(SQ)) {
		cout << "队列为空" << endl;
		return -1;
	}
	return *data = SQ->queue[SQ->front];//将首元素存储到data中
}

//获取队列长度
int GetLength(SeqQueue* SQ) {
	if (!SQ) return 0;

	return SQ->rear - SQ->front;//队列尾部位置减去首部位置即为队列长度
}

5.清空队列，遍历队列

//清空队列
void ClearQueue(SeqQueue* SQ) {
	if (!SQ) return;
	SQ->front = SQ->rear = 0;
}

//遍历队列中的所有元素
void PrintQueue(SeqQueue* SQ) {
	if (!SQ) return;

	int i = SQ->front;
	while (i < SQ->rear) {//循环遍历队列
		cout << setw(4) << SQ->queue[i];
		i++;
	}
	cout << endl;
}

完整代码

#include <iostream>
#include <Windows.h>
#include <iomanip>  //setw()函数头文件,setw()函数是设置字段宽(间距)的，默认右对齐

using namespace std;

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

typedef int DataType;  //队列中元素类型(方便修改)

//队列结构体
typedef struct Queue {
	DataType queue[MaxSize]; //队列数据存储区
	int front;    //队头(指向队列中的第一个元素的位置)
	int rear;     //队尾(指向队列中的最后一个元素的位置)
}SeqQueue;

//队列初始化，将队列初始化为空队列
void InitQueue(SeqQueue *SQ) {
	if (!SQ) return;//判断队列是否为空
	
	SQ->front = 0;  //将队头设置为0
	SQ->rear = 0;   //将队尾设置为0
}

//判断队列是否满了
bool IsFull(SeqQueue *SQ) {
	if (!SQ) return false;

	if (SQ->rear == MaxSize) { //尾部位置与队列容量相等，队列已满
		return true;
	}
	return false;
}

//判断队列是否为空
bool IsEmpty(SeqQueue* SQ) {
	if (!SQ) return false;

	if (SQ->front == SQ->rear) {//队列首部位置与队列尾部位置相等，则为空
		return true;
	}
	return false;
}

//入队，将元素data插入到队列中
bool EnterQueue(SeqQueue* SQ, DataType data) {//data为要插入的数据
	if (IsFull(SQ)) {//判断队列是否已满
		cout << "队列已满，无法插入！" << endl;
		return false;
	}

	SQ->queue[SQ->rear] = data; //在队尾插入元素data
	SQ->rear++;  //插入元素后，队尾位置加1

	return true;
}

//出队，将队列中队头的元素data出队，后面的元素依次向前移动
bool DeleteQueue(SeqQueue* SQ, DataType &data) {//data用来保存出队元素
	if (!SQ || IsEmpty(SQ)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!data) return false;

	data = SQ->queue[SQ->front];//将出队元素保存到data中

	for (int i = SQ->front + 1; i < SQ->rear; i++) {//元素出队后，其他元素依次向前移一位
		SQ->queue[i - 1] = SQ->queue[i];
	}

	SQ->rear--;//出队一个，尾部减1
	return true;
}

//出队方法2：
//出队，将队列中队头的元素data出队，后将队首位置向后移一位(表示首位)
bool DeleteQueue2(SeqQueue* SQ, DataType &data) {
	if (!SQ || IsEmpty(SQ)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!data) return false;

	if (SQ->front >= MaxSize) { //判断首部元素位置是否大于或等于队列容量
		cout << "队列已到尽头" << endl;
		return false;
	}

	data = SQ->queue[SQ->front];//出队元素保存到data中
	SQ->front = (SQ->front) + 1; //将队列首部向后移一位

	return true;
}

//获取队首元素
int GetHead(SeqQueue* SQ, DataType &data) {
	if (!SQ || IsEmpty(SQ)) {
		cout << "队列为空" << endl;
		return -1;
	}
	return data = SQ->queue[SQ->front];//将首元素存储到data中
}

//清空队列
void ClearQueue(SeqQueue* SQ) {
	if (!SQ) return;
	SQ->front = SQ->rear = 0;
}

//获取队列长度
int GetLength(SeqQueue* SQ) {
	if (!SQ) return 0;

	return SQ->rear - SQ->front;//队列尾部位置减去首部位置即为队列长度
}

//遍历队列中的所有元素
void PrintQueue(SeqQueue* SQ) {
	if (!SQ) return;

	cout << "------打印队列------" << endl;
	int i = SQ->front;
	while (i < SQ->rear) {//循环遍历队列
		cout << setw(4) << SQ->queue[i];
		i++;
	}
	cout << endl;
	cout << "------打印队列------" << endl;
}

int main(void) {
	SeqQueue* SQ = new SeqQueue; //分配存储空间,创建队列
	DataType data = -1;

	//初始化队列
	InitQueue(SQ);

	//入队
	int num,n,i=0;
	cout << "请输入要插入元素的个数：";
	cin >> n;
	while (i<n) {
		cout << "请输入队列元素:";
		cin >> num;
		if (EnterQueue(SQ, num)) {
			cout << "插入成功！"<<endl;
		}else {
			cout << "插入失败！"<< endl;
		}
		i++;
	}
	//打印队列
	PrintQueue(SQ);

	//出队
	if (DeleteQueue(SQ, data)) {
		cout << "出队成功！" << endl;
	}else {
		cout << "出队失败！" << endl;
	}
	cout << data << endl;
	//打印队列
	PrintQueue(SQ);

	//获取首元素
	if (GetHead(SQ, data)) {
		cout << "首元素获取成功，元素为：" << data << endl;
	}else {
		cout << "首元素获取失败" << endl;
	}

	//获取队列长度
	int len = GetLength(SQ);
	cout << "队列长度为：" << len << endl;

	//清空队列
	ClearQueue(SQ);

	system("pause");
	return 0;
}