双端队列

deque 即双端队列。是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出队列的每一端都可以插入数据项和移除数据项。相对于普通队列，双端队列的入队和出队操作在两端都可进行。

双端队列的示意图：

这里我们使用最常用的顺序结构来存储双端队列，为了节省空间，把它首尾相连，构成循环队列。并且规定left指向左端的第一个元素，right指向右端的下一个位置。那么队空的判断则是left==right，队满是(left-1+MAX)%MAX==right或者(right-left+MAX)%MAX==MAX。

#include<iostream>
#include<iomanip>
using namespace std;
//队列的最大存储空间为MAX 
const int MAX = 10;
typedef int ElemType;
//双端队列类 
class Deque    //double flaged queue
{
private:
	int size;  //队列中元素个数 
	ElemType *base;   //存放数据的数组采用指针的形式，后续操作中只需改变下标的值
	int left, right;  //0代表左端left，1代表右端right，下标设置为int型，一直在改变
public:
	//构造函数 
	Deque();
	//析构
	~Deque()
	{
		delete []base;
	}
	//获取大小
	int getSize()
	{
		return size;
	}
	//队空判断 
	bool empty()
	{
		return left == right;
	}  //或者size==0 
	//队满判断
	bool full()
	{
		return (left - 1 + MAX) % MAX == right;  //求余报保证为正，且逻辑关系不变
	}
	//获取指定端的头元素
	bool topAt(ElemType&, int);
	//在指定端插入(入队) 
	bool pushAt(ElemType, int);
	//在指定端删除(出队) 
	bool popAt(int);
	//从指定端打印队列 
	void print(int);
	//请空队列
	void clear();
};

Deque::Deque()
{
	base = new ElemType[MAX];
	left = right = 0;
	size = 0;
}
bool Deque::topAt(ElemType& data, int flag)
{
	if (empty())
		return false;
	if (flag == 0)
		data = base[left];
	else
		data = base[(right - 1 + MAX) % MAX];//因为right指向下一个位置所以要减一
	return true;
}
bool Deque::pushAt(ElemType data, int flag)
{
	if (full())
		return false;
	if (flag == 0)
	{
		left = (left - 1 + MAX) % MAX; //通过取余操作，left指针一直在后退,一开始是最大的
		base[left] = data;
	}
	else
	{
		base[right] = data; //right直接赋值
		right = (right + 1) % MAX;  //先赋值再前进
	}
	return true;
}
bool Deque::popAt(int flag)
{
	if (empty())
		return false;
	if (flag == 0)
		left = (left + 1) % MAX; //left是类的变量，值一直在变，后进先出
	else
		right = (right - 1 + MAX) % MAX;  //取余防止溢出
	return true;
}
void Deque::print(int flag)
{
	if (empty())
	{
		cout << "空队列，无法遍历！" << endl;
		return;
	}
	if (flag == 0)
	{
		int i = left;   //此时left不位于0位置，而在最后一次操作它的位置
		while (i != right)
		{
			cout << setw(4) << base[i];
			i = (i + 1) % MAX;
		}
	}
	else
	{
		int i = right;  //同理此时right不位于0位置，而在最后一次操作它的位置
		while (i != left)
		{
			i = (i - 1 + MAX) % MAX;
			cout << setw(4) << base[i];
		}
	}
	cout << endl;
}
void Deque::clear()
{
	left = right = 0;
	size = 0;
}
void check(int& flag)  //对端号进行检查
{
	while (cin >> flag && !(flag == 0 || flag == 1))
	{
		cout << "端号不对，重新输入：";
	}
}
void input(Deque& deque)  //输入函数
{
	int flag;
	cout << "在指定端入队，0左端，1右端：";
	check(flag);
	ElemType data;
	cout << "输入数据，输入0结束" << endl;
	while (cin >> data && data)
	{
		deque.pushAt(data, flag);
	}
}
void traverse(Deque& deque)   //从指定端遍历
{
	int flag;
	cout << "从指定端遍历：";
	check(flag);
	deque.print(flag);
}
int main()
{
	cout << "******双端队列演练******" << endl;
	Deque deque;
	cout << "新建双端队列" << endl;
	cout << "队列是否为空：";
	deque.empty() ? cout << "Yes!" << endl : cout << "No!" << endl;
	input(deque);
	traverse(deque);
	input(deque);
	traverse(deque);
	ElemType data;
	int flag;
	cout << "获取指定定端的头元素：";
	check(flag);
	deque.topAt(data, flag) ? cout << data << endl : cout << "队空！" << endl;
	cout << "删除指定定端的头元素：";
	check(flag);
	deque.popAt(flag) ? cout << "删除成功" << endl : cout << "队空！" << endl;
	traverse(deque);
	cout << "清空队列，队列是否为空：";
	deque.clear();
	deque.empty() ? cout << "Yes!" << endl : cout << "No!" << endl;
	system("pause");
	return 0;
}

本文转自https://blog.csdn.net/zhangxiangDavaid/article/details/31744845，文章left和right的转换很巧妙，我根据自己的理解加了注释，感谢原作者分享

双端队列

Ferry