频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
队列的应用:双端队列
2014-06-18 10:59:33      个评论    来源:队列的应用:双端队列  
收藏   我要投稿

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

双端队列的示意图:

\

left:左端 right:右端

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

运行:



若是有所帮助,顶一个哦!

专栏目录:数据结构与算法目录



点击复制链接 与好友分享!回本站首页
相关TAG标签 队列
上一篇:C++中传送函数指针
下一篇:poj 1201 Intervals(差分约束)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站