[Day11]程序菜鸟自学C++资料结构演算法 – 伫 列Queue

前言：上一篇结束了堆叠的实作，今天要来介绍新东西「伫列」。

伫列的特性：伫列和堆叠非常类似，同样都是有序串列(元素以某种顺序排列 ，该顺序具有一定的意义，不可错置)，且同样属於抽象资料型态。
伫列与堆叠的差别在於伫列为「先进先出(FIFO,First In First Out)」，就好比先排队的人先买到门票一样。

图片来源：http://runningmanmacau.weebly.com/uploads/2/7/2/0/27203993/s416834513424666157_p2_i1_w640.jpeg

如果以电脑的角度来看，堆叠的新增和删除只能发生在头节点，而伫列多了一个後端指标负责新增资料，前端指标用来读取和删除。

环状伫列：伫列的实际应用之一，经常用於行车纪录器或监视器之类的装置，储存特定天数的资料，若天数已满则将第一天从前端删除，并从末端加入新的一天。



依照这样的做法就能成功创建了喔！

接着就实际操作看看，一样要先创建新的专案୧| ” •̀ ل͜ •́ ” |୨

伫列：

std::cout << Q.front() << std::endl;为显示伫列前端指标的资料，所以可以看到12位在伫列最前端，将其pop之後最前端的位置就变为3。

也可持续pop直到伫列为空的，首先要判断伫列是否没有资料。

这样就完成最初始的伫列了喔，紧接着就来挑战进阶一些的环状伫列。

环状伫列：

直接在资源档中新增项目即可，不需要创建新的专案。但同样一个专案不能有两个main程序，如果不知道怎麽操作的，可以看看上一篇文章

之後就可以开始实作了。

因为是环状伫列，所以也可以从末端查询资料。

这样就完成了喔！

本日小结：今天做完了伫列和循环伫列，循环伫列和伫列的概念非常类似，但是如果要对循环伫列进行新增和删除的话，都必须要用除以容量的余数去考虑，这个部分比较复杂，需要花时间理解，伫列还有一些东西没讲到，会在之後的文章说明，明天将要进入资料结构中最重要的一环「树」的部分१|˚–˚|५

伫列

#include<iostream>
using namespace std;

template<class T> class Queue {
	struct Node { //设立节点前端和後端指标
		T data;
		Node* next;
	};
	Node* front_;
	Node* rear;

public: //宣告函式
	Queue();
	bool push(T e);
	bool pop();
	T& front() { //查询位在前端指标的资料
		if (front_ == rear) throw"伫列为空";
		return front_->next->data;
	}
	bool empty() {
		return front_ == rear;
	}
};

template<class T>
Queue<T>::Queue() { //初始化伫列
	front_ = rear = new Node();
	if (!front_) throw "No Memory";
	front_->next = 0;
}

template<class T> 
bool Queue<T>::push(T e) { //将资料新增置後端指标
	Node* p = new Node;
	if (!p)return false;
	p->data = e; p->next = 0;
	rear->next = p;
	rear = p;
	return true;
}
template<class T>
bool Queue<T>::pop() { // 将资料从前端指标删除
	if (front_ == rear) return false;
	Node* p = front_->next;
	front_->next = p->next;
	if (rear == p) rear = front_;
	delete p;
	return true;
}

int main() {
	Queue<int> Q;
	Q.push(12); 
	Q.push(3); 
	Q.push(6); 
	std::cout << Q.front() << std::endl;
	Q.pop();
	std::cout << Q.front() << std::endl << std::endl;

	Q.push(30);
	Q.push(16);
	while (!Q.empty()) {
		std::cout << Q.front() << std::endl;
		Q.pop();
	}
}

环状伫列

#include<iostream>
using namespace std;

template<typename T>
class SqlQueue { //创建新的伫列，并宣告会用到的变数名称
	T* data;
	int front_, rear_, capacity;
public:
	SqlQueue(int cap = 3) {
		data = new T[cap]; if(!data) throw "储存空间份配失败";
		capacity = cap;
		front_ = rear_ = 0; //表示空阵列
	}
	bool push(T e) {
		if ((rear_ + 1) % capacity == front_) {
			T* p = new T[2 * capacity];
			if(!p) return false; //检查伫列是否已满，若rear_+1的余数等於front，则伫列已满
			for (int i = 0; i < capacity; i++)
				p[i] = data[i];
			delete[] data;
			data = p;
			capacity *= 2;
		}
		data[rear_] = e; rear_ = (rear_ + 1) % capacity; //%为相除的余数 ex:3%5=2
		return true;
	}
	bool pop() {
		if (front_ == rear_) return false;
		front_ = (front_ + 1) % capacity;
		return true;
	}
	T& front() {
		if (front_ == rear_) throw "伫列为空";
		return data[front_];
	}
	T& rear() {
		if (front_ == rear_) throw "伫列为空";
		return data[(rear_ - 1 + capacity) % capacity];
	}
	int size() {
		return (rear_ - front_ + capacity) % capacity;
	} 
	bool empty() {
		return front_ == rear_;
	}
	bool clear() {
		front_ = rear_ = 0;
	}
};

int main() {
	SqlQueue<int> Q;
	Q.push(54);
	Q.push(94);
	Q.push(67);
	Q.push(39);
	Q.push(86);
	Q.push(13);
	int r = Q.rear();
	std::cout << r << std::endl;
	while (!Q.empty()) {
		int f = Q.front();
		Q.pop();
		std::cout << f << "　";
	}
	std::cout << std::endl;
}