C++_Hello算法_队列

队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

如图 5-4 所示，我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。

图 5-4   队列的先入先出规则

5.2.1   队列常用操作¶

队列的常见操作如表 5-2 所示。需要注意的是，不同编程语言的方法名称可能会有所不同。我们在此采用与栈相同的方法命名。

表 5-2   队列操作效率

我们可以直接使用编程语言中现成的队列类：

/* 初始化队列 */
queue<int> queue;

/* 元素入队 */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);

/* 访问队首元素 */
int front = queue.front();

/* 元素出队 */
queue.pop();

/* 获取队列的长度 */
int size = queue.size();

/* 判断队列是否为空 */
bool empty = queue.empty();

5.2.2   队列实现¶

为了实现队列，我们需要一种数据结构，可以在一端添加元素，并在另一端删除元素，链表和数组都符合要求。

1.   基于链表的实现¶

如图 5-5 所示，我们可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”，规定队尾仅可添加节点，队首仅可删除节点。

图 5-5   基于链表实现队列的入队出队操作

以下是用链表实现队列的代码：

#include <iostream>
#include <vector>
#include <stdexcept> // 用于异常处理
#include <stack>
using namespace std;
/* 用列表实现队列的代码*/


struct ListNode {
	int val;
	ListNode* next;

	ListNode(int value) : val(value), next(nullptr) {}
};



// 队列类的定义
class LinkedListQueue
{


private:
	ListNode* front, * rear; //队列头，队列尾
	int queSize; //队列长度


	//释放链表内存
	void freeMemoryLinkedList(ListNode* node) {
		while (node != nullptr) {
			ListNode* temp = node;
			node = node->next;
			delete temp;
		}
	}


public:
	// 构造函数
	LinkedListQueue() : front(nullptr), rear(nullptr), queSize(0) {}

	//析构函数
	~LinkedListQueue() {
		freeMemoryLinkedList(front);
	}

	//获取队列大小
	int size() {
		return queSize;
	}

	//判断队列是否为空
	bool isEmpty() {
		return queSize == 0;
	}

	//入队 (尾插) 
	void push(int num) {
		ListNode* node = new ListNode(num);
		if (front == nullptr) { // 队列为空，头尾部指向新节点
			front = node;
			rear = node;
		}
		else { // 队列不为空，尾插
			rear->next = node;
			rear = node;
		}
		queSize++;
	}

	//出队 (删除头节点)
	int pop() {
		if (isEmpty())
		{
			throw out_of_range("队列为空，不能出队");
		}

		int val = front->val;//先保存队首值
		ListNode* temp = front;	//备份队节点
		front = front->next;	 //指向下一节点
		delete temp;//释放原队首节点
		queSize--;

		if (front == nullptr) { //如果队列为空，重置rear
			rear = nullptr;
		}

		return val;
	}

	//访问队列首元素
	int peek() {
		if (isEmpty())
		{
			throw out_of_range("队列为空");
		}
		return front->val;
	}

	//转换为vector返回
	vector<int> toVector() {
		vector<int> res(size());
		ListNode* node = front;
		for (int i = 0; i < res.size(); i++)
		{
			res[i] = node->val;
			node = node->next;
		}
		return res;
	}
};


int main() {
	LinkedListQueue q;
	q.push(10);
	q.push(20);
	q.push(30);

	cout << "队列中元素 : ";
	vector<int> v = q.toVector();
	for (int num : v)
	{
		cout << num << " ";
	}
	cout << endl;
	cout << "队首元素: " << q.peek() << endl;
	while (!q.isEmpty()) {
		cout << "出队元素: " << q.pop() << endl;
	}
	cout << "队列长度: " << q.size() << endl;


	system("pause");
	return 0;

}