RobbEr's Blog

Welcome

数据结构-队列

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 4.7k 阅读时长 ≈ 4 分钟

简介

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

特点

  1. 队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构
  2. 在队尾添加元素，在队头删除元素

队列的相关概念

  1. 队头与队尾： 允许元素插入的一端称为队尾，允许元素删除的一端称为队头
  2. 入队：队列的插入操作
  3. 出队：队列的删除操作

队列的操作(stl中<queue>库)

1
2
3
4
5
6
q.empty()	//如果队列为空返回true，否则返回false
q.size()	//返回队列中元素的个数
q.pop()		//删除队列首元素但不返回其值
q.front()	//返回队首元素的值，但不删除该元素
q.push()	//在队尾压入新元素
q.back()	//返回队列尾元素的值，但不删除该元素

队列的实现

此大标题下代码实现及原理转载自C++数据结构——队列，并在此基础上加上了自己的见解和代码运行发生问题时的解决方法

基于数组的循环队列

以数组作为底层数据结构时，一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足：每次从数组头部删除元素（出队）后，需要将头部以后的所有元素往前移动一个位置，这是一个时间复杂度为O（n）的操作。

循环队列，可以把数组看出一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。参考博客：【c++版数据结构】之循环队列的实现，判断循环队列是“空”还是“ 满”，有两种处理方法：

  1. 设置状态标志位以区别空还是满
  2. 少用一个元素，约定“队头front在队尾rear的下一个位置（指的是环的下一个位置）”作为“满”的标志

以下为C++实现

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
#include <iostream>
#include <queue>
#include <string>
using namespace std;
 
template <typename T>
class LoopQueue{
public:
	LoopQueue(int c = 10);
	~LoopQueue();
	bool isEmpty();				//队列的判空
	int size();				//队列的大小
	bool push(T t);				//入队列
	bool pop();				//出队列
	T front();				//队首元素
 
private:
	int capacity;
	int begin;
	int end;
	T*  queue;
};
 
template<typename T>
LoopQueue<T>::LoopQueue(int c = 10)
	:capacity(c), begin(0), end(0), queue(nullptr){//构造函数
	queue = new T[capacity];
};
 
template<typename T>
LoopQueue<T>::~LoopQueue(){						//析构函数
	delete[]queue;
}
 
template <typename T>
bool LoopQueue<T>::isEmpty(){                   //判断循环队列是否为空
	if (begin == end)
		return true;
	return false;
};
 
template<typename T>
int LoopQueue<T>::size(){
	return (end - begin + capacity) % capacity; //计算循环队列的长度
};
 
template<typename T>
bool LoopQueue<T>::push(T t){
	if (end + 1 % capacity == begin){            //判断队列是否已满
		return false;
	}
	queue[end] = t;
	end = (end + 1) % capacity;
	return true;
};
 
template <typename T>
bool LoopQueue<T>::pop(){                        //判断队列是否为空
	if (end == begin){
		return false;
	}
	begin = (begin + 1) % capacity;
	return true;
};
 
template <typename T>
T LoopQueue<T>::front(){
	if (end == begin){
		return false;//编译器报错时使用return NULL，好像是库版本不一样的原因
	}
	return queue[begin];
};
 
int main(){
	LoopQueue<string> queue(6);
	queue.push("one");
	queue.push("two");
	queue.push("three");
	queue.push("four");
	queue.push("five");
	cout << "队列长度" << queue.size() << endl;
	while (!queue.isEmpty()){
		cout << queue.front() << endl;
		queue.pop();
	}
	getchar();
	//system("pause");
	return 0;
}

基于链表的队列

链队列是基于链表实现的队列，它不存在数组的O(n)的元素移动问题或空间浪费问题。我们所要确定的就是链表哪头做队首，哪头做队尾。显然我们应该以链表头部为队首，链表尾部为队尾。存储一个指向队尾的指针，方便从链表尾插入元素；使用带头节点的链表，方便从链表头删除元素。

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
#include <iostream>
#include <cstdlib>
using namespace std;
 
struct QNode{				//定义队列结点的数据结构
	QNode *next;			//指针域,指向下一个结点
	double data;			//数据域，存储队列信息
};
 
struct LinkQueue{			//定义队列的数据结构
	QNode *front;			//队首指针,指向QNode类型的指针
	QNode *rear;			//队尾指针
};
 
void InitQueue(LinkQueue &Q){//构造一个空的队列
	QNode *q;
	q = new QNode;			//申请一个结点的空间
	q->next = NULL;			//当作头结点
	//队首与队尾指针都指向这个结点，指针域为NULL
	Q.front = q;
	Q.rear = q;
}
 
int IsEmpty(LinkQueue &Q){	//判断队列是否为空
	if (Q.rear == Q.front)
		return 0;
	else
		return 1;
}
 
void EnQueue(LinkQueue &Q, double e){//从队列尾部插入元素
	QNode *p;				//新创建一个结点
	p = new QNode;
	p->next = NULL;
	p->data = e;			//输入数据信息
	//将新结点插入队列尾部
	Q.rear->next = p;
	Q.rear = p;				//设置新的尾结点
}
 
void DeQueue(LinkQueue &Q, double &e){//从队列首部删除一个结点
	QNode *p;
	p = Q.front->next;
	e = p->data;			//保存要出队列的数据
	Q.front->next = p->next;//将下一个结点当作头结点后面链接的第一个结点
	if (Q.rear == p)		//如果要删除的元素即为尾结点，则将头指针赋予尾指针，一同指向头结点，表示队列为空
		Q.rear = Q.front;
	delete p;
}
 
void DestoryQueue(LinkQueue &Q){//销毁一个队列
	while (Q.front)
	{
		Q.rear = Q.front;	//从头节点开始，一个一个删除队列结点，释放空间
		delete Q.front;
		Q.front = Q.rear;
	}
}

int main(){
	LinkQueue *Q;			//定义一个队列Q
	Q = new LinkQueue;
	InitQueue(*Q);
	cout << "开始往队列里输入数据，以-1作为结束符" << endl;
	cout << "请输入一个数：" << endl;
	double a, x;
	cin >> a;
	while (a != -1){		//输出队列元素,队首->队尾
		EnQueue(*Q, a);
		cout << "请输入一个数：" << endl;
		cin >> a;
	}
	QNode *p;
	p = Q->front->next;
	if (p == NULL){			//如果为空表，直接退出
		cout << "队列为空！" << endl;
		return 0;
	}
	cout << "队列数据依次为：" << endl;
	while (p != NULL){		//输出队列元素
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
	while (!IsEmpty(*Q)){	//删除队列元素
		DeQueue(*Q, x);
		cout << x << " ";
	}
							//释放内存空间
	delete Q->front;
	delete Q;
	system("pause");
	return 0;
}

例题

两个队列实现栈