C++環形隊列實作

1.環形隊列

• 普通隊列有着先入先出的特性，但是普通隊列如果删除隊頭，所删除的空間将不會被釋放，又由于隊列隻能由隊尾插入，這就導緻被删除部分的空間被浪費。
• 循環隊列就是用于解決普通隊列所存在的這個問題，其顧名思義就是将隊列串起來形成一個類似于環的結構。

• 循環隊列相對于普通隊列的操作不同點：

  1.判斷滿：循環隊列的滿不再是rear=front 而是改成(rear-front+maxn)%maxn。

  2.入隊操作: data[rear] = x; rear = (rear+1)%maxn;

總體思想就是不讓rear和front的值超過maxn的大小。于是就在rear和front自增時候模maxn。

注意！！：空隊時rear等于front，滿隊時必須空一個位置。但是size就是size，說存3個就是存3個

2.代碼與測試代碼

#include <iostream>
using namespace std;

template<typename T> class circlequeue
{
private:
	unsigned int m_size;
	int m_front;
	int m_rear;
	T* m_data;
public:
	circlequeue(unsigned int size)
	{
		m_front = m_rear = 0;
		m_data = new T[m_size = size];
	}
	~circlequeue()
	{
		delete[] m_data;
	}
	bool isEmpty()
	{
		return m_front == m_rear;
	}
	bool isFull()
	{
		//m_front與m_rear均會移動，%size來判斷，比如size = 10，m_rear = 9, m_front = 0的情況，需要考慮環形回環
		return m_front == (m_rear + 1) % m_size;
	}
	void push(T data)
	{
		if (isFull())
		{
			throw new exception("目前環形隊列已滿，不允許繼續push");
		}
		m_data[m_rear] = data;
		m_rear = (m_rear + 1) % m_size;
	}
	void pop()
	{
		if (isEmpty())
		{
			throw new exception("目前環形隊列為空，不允許繼續pop");
		}
		m_front = (m_front + 1) % m_size;
	}
	void popall()
	{
		if (isEmpty())
		{
			throw new exception("目前環形隊列為空，不允許繼續pop");
		}
		while (m_front != m_rear)
			m_front = (m_front + 1) % m_size;
	}
	T top()
	{
		if (isEmpty())
		{
			throw new exception("目前環形隊列為空，沒有top對象");
		}
		return m_data[m_front];
	}
};

int main()
{
	circlequeue<int> q(5);
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	for (int i = 0; i < 4; i++)
	{
		cout << q.top() << endl;
		q.pop();
	}
	q.push(5);
	q.push(5);
	q.push(5);
	cout << q.top() << endl;
	q.pop();
	cout << q.top() << endl;
	q.pop();
	cout << q.top() << endl;
	q.pop();
	q.push(5);
	q.push(5);
	q.push(5);
	q.popall();
	//cout << q.top() << endl;
	//q.pop();

	return 0;
}
           

參考文獻：

https://www.cnblogs.com/diegodu/p/4619104.html