循环双端队列(转自CSDN,有修改)

循环队列中,由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是“空”还是“满”。

队列的操作特点是“先进先出”。前者主要是“头指针”、“尾指针”的使用,后者主要是理解循环队列提出的原因及其特点。两者都要掌握队列空与满的判定条件以及出队列、入队列操作的实现。

为充分利用向量空间,克服“假溢出”现象的方法是:将向量空间想象成一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列成为循环队列(Circular Queue)。

我们基于C++实现之。

实现代码如下:

//循环双端队列

//循环双端队列顺序表示

#include <iostream>
#include <iomanip>
#include <assert.h>

using namespace std;
template <class T> class DoubleQueue
{
	int end1, end2; //end1和end2为端点
	T * data;
	int size;
	public:
		DoubleQueue(int sz = 10);
		~DoubleQueue(){delete[] data;}
		void Enqueue(T item, int end);
		void Dequeue(int end);
		int IsEmpty(){return end1 == end2;}
		int IsFull(){return (end1+1)%size == end2;}
		void list(int end);
};

//循环双端队列操作
template <class T>
DoubleQueue <T>::DoubleQueue(int sz):end1(0), end2(0),size(sz){
	data = new T[size];
	assert(data != 0);
}

//循环双端队列插入新元素操作
template <class T>
void DoubleQueue <T>::Enqueue(T item, int end)
{
	assert(!IsFull());
	if(end == 1)
	{
		end1 = (end1+1)%size;
		data[end1] = item;
	}
	else
	{
		data[end2] = item;
		end2 = (end2-1+size)%size;
	}
}

//循环双端队列删除操作
template <class T>
void DoubleQueue <T>::Dequeue(int end)
{
	assert(!IsEmpty());
	if(end == 1)
	{
		end1 = (end1+size-1)%size;
	}
	else
	{
		end2 = (end2+1)%size;
	}
}

//循环双端队列输出操作
template <class T>
void DoubleQueue <T>::list(int end)
{
	if(end == 1)
	{
		for(T p=(end2+1)%size; p<=end1; p=(p+1)%size)
			cout<<setw(3)<<data[p];
		cout<<endl;
	}
	else
	{
		for(T p=end1; p!=end2; p=(p+size-1)%size)
			cout<<setw(3)<<data[p];
		cout<<endl;
	}
}

//循环双端队列的测试
int main(void)
{
	DoubleQueue <int> Q;
	cout<<"运行结果:"<<endl;
	//向队列end1插入4,5,6,7,8五个元素
	Q.Enqueue(4,1);
	Q.Enqueue(5,1);
	Q.Enqueue(6,1);
	Q.Enqueue(7,1);
	Q.Enqueue(8,1);
	cout<<"输出向队列end1插入4,5,6,7,8五个元素后的情况:"<<endl;
	Q.list(1);
	//删除最后插入的两个元素
	Q.Dequeue(1);
	Q.Dequeue(1);
	cout<<"输出删除最后两个元素后的队列end1的情况:"<<endl;
	Q.list(1);
	//向队列end2插入7,8,9,10,11五个元素
	Q.Enqueue(7,2);
	Q.Enqueue(8,2);
	Q.Enqueue(9,2);
	Q.Enqueue(10,2);
	Q.Enqueue(11,2);
	cout<<"输出向队列end2插入7,8,9,10,11五个元素后的情况:"<<endl;
	Q.list(2);
}