堆和栈组合：双端队列c++
【摘要】
双端队列(Deque:double ended queue)就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。相对于普通队列，双端队列的入队和出队操作在两端都可进行。
双端队列的示意图：
left：左端 right：右端
这里我们使用最常用的顺序结构来存储双端队列，为了节省空间，把它首尾相连，构成...
双端队列(Deque:double ended queue)就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。相对于普通队列，双端队列的入队和出队操作在两端都可进行。
双端队列的示意图：
left：左端 right：右端
这里我们使用最常用的顺序结构来存储双端队列，为了节省空间，把它首尾相连，构成循环队列。并且规定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 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;
-
}
运行：
文章来源: blog.csdn.net，作者：网奇，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/jacke121/article/details/116325067
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）