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