队列的应用：双端队列 - c++编程基础

双端队列(Deque:double ended queue)就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。相对于普通队列，双端队列的入队和出队操作在两端都可进行。

双端队列的示意图：

left：左端 right：右端

这里我们使用最常用的顺序结构来存储双端队列，为了节省空间，把它首尾相连，构成循环队列。并且规定left指向左端的第一个元素，right指向右端的下一个位置。那么队空的判断则是left==right，队满是(left-1+MAX)%MAX==right或者(right-left+MAX)%MAX==MAX。<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+z+rPuM+4vdq/tLT6wuujujwvcD4KPHA+wOC2qNLlus3A4Mq1z9Y8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">#include #include using namespace std; //队列的最大存储空间为MAX const int MAX = 10; typedef int ElemType; //双端队列类 class Deque //double ended queue { private: int size; //队列中元素个数 ElemType *base; int left, right; //0代表左端left，1代表右端right 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 end) { if (empty()) return false; if (end == 0) data = base[left]; else data = base[(right - 1 + MAX) % MAX]; return true; } bool Deque::pushAt(ElemType data, int end) { if (full()) return false; if (end == 0) { left = (left - 1 + MAX) % MAX; base[left] = data; } else { base[right] = data; right = (right + 1) % MAX; } return true; } bool Deque::popAt(int end) { if (empty()) return false; if (end == 0) left = (left + 1) % MAX; else right = (right - 1 + MAX) % MAX; return true; } void Deque::print(int end) { if (empty()) { cout << "空队列，无法遍历！" << endl; return; } if (end == 0) { int i = left; while (i != right) { cout << setw(4) << base[i]; i = (i + 1) % MAX; } } else { int i = right; 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& end)  //对端号进行检查
{
	while (cin >> end && !(end == 0 || end == 1))
	{
		cout << "端号不对，重新输入：";
	}
}
void input(Deque& deque)  //输入函数
{
	int end;
	cout << "在指定端入队，0左端，1右端：";
	check(end);
	ElemType data;
	cout << "输入数据，输入0结束" << endl;
	while (cin >> data && data)
	{
		deque.pushAt(data, end);
	}
}
void traverse(Deque& deque)   //从指定端遍历
{
	int end;
	cout << "从指定端遍历：";
	check(end);
	deque.print(end);
}
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 end;
	cout << "获取指定定端的头元素：";
	check(end);
	deque.topAt(data, end) ? cout << data << endl : cout << "队空！" << endl;
	cout << "删除指定定端的头元素：";
	check(end);
	deque.popAt(end) ? cout << "删除成功" << endl : cout << "队空！" << endl;
	traverse(deque);
	cout << "清空队列，队列是否为空：";
	deque.clear();
	deque.empty() ? cout << "Yes!" << endl : cout << "No!" << endl;
	system("pause");
	return 0;
}

运行：

若是有所帮助，顶一个哦！