数据结构——队列

2024-02-22 10:54:16

1.队列的定义

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列储存的图像表示：

（图片来源于网络，侵删）

2、队列的基本运算

1）初始化队列：Init_Queue(q) ，初始条件：队q 不存在。操作结果：构造了一个空队；

2）入队操作： In_Queue(q,x),初始条件：队q 存在。操作结果：对已存在的队列q，插入一个元素x 到队尾，队发生变化；

3）出队操作： Out_Queue(q,x)，初始条件: 队q 存在且非空，操作结果：删除队首元素，并返回其值，队发生变化；

4）读队头元素：Front_Queue(q,x)，初始条件: 队q 存在且非空，操作结果：读队头元素，并返回其值，队不变；

5）判队空操作：Empty_Queue(q)，初始条件：队q 存在，操作结果：若q 为空队则返回为1，否则返回为0。

3、队列的顺式储存实现

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置

顺式储存的图示：

（图片来源于百度：https://baike.baidu.com/pic/%E9%98%9F%E5%88%97/14580481/0/cdbf6c81800a19d8116a4d8030fa828ba71e46ce?fr=lemma&ct=single#aid=0&pic=cdbf6c81800a19d8116a4d8030fa828ba71e46ce）

顺式队列的存储实现

#include <iostream>
#define MAXSIZE 100		//定义最大元素个数 
#define ElemType int		//定义数据类型 
#define ERROR 0
#define TRUE 1 
#define OVERFLOW -1

using namespace std;

typedef struct QNode *Queue;
struct QNode{
	ElemType Data[MAXSIZE];
	int rear;		//数组下标，表示最后一项
	int front;		//数组下标，表示第一项
};

相信你学到队列时，对顺序表的插入和删除已经很熟练了，在这里就不再赘述，重点在于下面的循环队列！！！（如果不熟练可以看我另外的内容->本博主.其他文章）

循环队列的储存实现

循环队列的储存图示：

（图片来源于百度：https://baike.baidu.com/pic/%E5%BE%AA%E7%8E%AF%E9%98%9F%E5%88%97/3685773/1/5d6034a85edf8db1ee973ff60a23dd54574e74e2?fr=lemma#aid=1&pic=5d6034a85edf8db1ee973ff60a23dd54574e74e2）

循环队列的插入

void AddQueue(Queue Ptrq, ElemType X){
	if((Ptrq->rear+1)%MAXSIZE == Ptrq->front)		//用取余判断的是否队列已满
		cout << "Data overflow";
	Ptrq->rear = (Ptrq->rear+1)%MAXSIZE;
    //关于这里为什么要%MAXSIZE,这是循环的关键
    //如果后面add满了，会从前面空出的位置继续添加
    //此时rear所指向的数组下标应该为前面空出位置的下标
    //故%MAXSIZE
    
	Ptrq->Data[Ptrq->rear] = X;		//插入元素X
}

循环队列的删除

ElemType DeleteQueue(Queue Ptrq){
	if(Ptrq->front == Ptrq->rear){		//判断是否为空队列
		cout << "No data";
		return ERROR;
	}
	else{
		Ptrq->front = (Ptrq->front+1)%MAXSIZE;
		return Ptrq->Data[Ptrq->front];		//出列表
	}
}

4、队列的链式储存实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头节点，而队尾指针指向终端节点。空队列时，front和rear都指向头节点。

链式队列的图示：

（图片来源于百度：https://baike.baidu.com/pic/%E9%98%9F%E5%88%97/14580481/0/7dd98d1001e939015d4345bb78ec54e737d196f6?fr=lemma&ct=single#aid=0&pic=7dd98d1001e939015d4345bb78ec54e737d196f6）

链式队列的储存实现

#include <iostream>
#define MAXSIZE 100		//定义最大元素个数 
#define ElemType int		//定义数据类型 
#define ERROR 0
#define TRUE 1 
#define OVERFLOW -1

using namespace std;

typedef struct QNode *Queue;
struct QNode{
	ElemType Data;
	Queue Next;
};

链式队列的删除

ElementType DeleteQueue (Queue PtrQ ){
	Queue FrontCell;
	ElementType FrontElem;
	if (PtrQ->front == nullptr){		//判断是否为空队列
		cout << "No data";
		return ERROR;
	}
	FrontCell = PtrQ->front;
	if ( PtrQ->front == PtrQ->rear)		//如果队列只有一个元素 
		PtrQ->front = PtrQ->rear = nullptr;		//删除后队列置为空
	else
		PtrQ->front = PtrQ->front->Next;
	FrontElem = FrontCell->Data;
	free(FrontCell);		//释放被删除结点空间
	return FrontElem;
}

码农公寓