用两个栈实现一个队列（C++）
2024-09-07 03:35:57
分析
- 栈：后进先出
- 队列：先进先出
要使用两个栈实现队列（先进先出），主要思路是
1.插入一个元素：直接将元素插入stack1即可。
2.删除一个元素：当stack2不为空时 ，直接弹出栈顶元素，当stack2为空时，将stack1元素逐个弹出并压入stack2，然后再弹出栈顶元素。
具体看下面的代码。
代码实现
#include <iostream>
#include <stack>
using namespace std;
template<class T>
class Queue
{
private:
stack<T> s1;
stack<T> s2;
public:
//入队
void Push(const T &val);
//出队
void Pop();
//返回队首元素
T& Front();
//返回对尾元素
T& Back();
//判断队列是否为空
bool Empty();
//返回队列大小
T Size();
};
//归纳：
//1.插入一个元素：直接将元素插入stack1即可；
//2.删除一个元素：当stack2不为空时 ，直接弹出栈顶元素，当stack2为空时，将stack1元素逐个弹出并压入stack2，然后在弹出栈顶元素；
//入队
template<class T>
void Queue<T>::Push(const T &val)
{
//栈s1做队列的队尾，s2做队列的对头
s1.push(val);
}
//出队
template<class T>
void Queue<T>::Pop()
{
if (!s2.empty())
{
s2.pop();
}
//s2为空时，s1中的所有内容逐一出栈压入s2
else
{
while (!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
//压入之后，s2的存放顺序正好和s1的相反，符合队列的先进先出，直接s2出栈
if (s2.empty())
{
cout << "队列为空" << endl;
exit(1);
}
s2.pop();
}
}
//返回队首元素
template<class T>
T& Queue<T>::Front()
{
if (!s2.empty())
{
return s2.top();
}
//s2为空时，s1中的所有内容逐一出栈压入s2
else
{
while (!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
//压入之后，s2的存放顺序正好和s1的相反，符合队列的先进先出
if (s2.empty())
{
cout << "队列为空" << endl;
exit(1);
}
return s2.top();
}
}
//返回对尾元素
template<class T>
T& Queue<T>::Back()
{
//s1不为空直接取
if (!s1.empty())
{
return s1.top();
}
//s2不为空，把s2中的内容放回s1,然后返回
while (!s2.empty())
{
s1.push(s2.top());
s2.pop();
}
if (!s1.empty())
{
return s1.top();
}
else
{
cout << "队列为空" << endl;
exit(1);
}
}
//判断是否为空
template<class T>
bool Queue<T>::Empty()
{
if (s1.empty() && s2.empty())
{
return true;
}
else
{
return false;
}
}
//返回对列尺寸
template<class T>
T Queue<T>::Size()
{
return s1.size() + s2.size();
}
int main()
{
Queue<int> q;
q.Push(1);
q.Push(2);
q.Push(3);
q.Push(4);
q.Push(5);
q.Push(6);
cout << "队列空否: " << q.Empty() << endl;
cout << "获取队头元素：" << q.Front() << endl;
cout << "获取队尾元素: " << q.Back() << endl;
cout << "获取队列的大小：" << q.Size() << endl;
cout << "出队" << endl;
q.Pop();
cout << "获取队列的大小：" << q.Size() << endl;
cout << "入队" << endl;
q.Push(7);
cout << "队列空否: " << q.Empty() << endl;
cout << "获取队头元素：" << q.Front() << endl;
cout << "获取队尾元素: " << q.Back() << endl;
cout << "获取队列的大小：" << q.Size() << endl;
cout << "出队" << endl;
q.Pop();
cout << "获取队列的大小：" << q.Size() << endl;
cout << "出队" << endl;
q.Pop();
cout << "获取队列的大小：" << q.Size() << endl;
system("pause");
return 0;
}
运行测试
最新文章
- 【转载】Scarbee Pre-Bass 贝司的使用教程
- MySQL运行出错：无法连接驱动、无root访问权限解决办法
- NSS_11 Server Error in '/' Application
- $.ligerDialog 操作
- centos6.5安装tomcat8.0.15
- typeahead使用配置参数。
- JOHN W. TUKEY: HIS LIFE AND PROFESSIONAL CONTRIBUTIONS
- 容易被忽视的后端服务 chunked 性能问题
- toFixed（）精度丢失；复选框全选、取消
- C\C++学习笔记 2
- Python使用import导入相对路径的其他py文件
- Linux之Ubuntu下安装屏幕录像软件（SimpleScreenRecorder）【摘抄】
- rimraf node_modules 快速删除
- Android 开发 AlarmManager 定时器
- jpg转yuv420抠图后转为jpg
- S5PV210 看门狗定时和复位
- EASYUI DATAGRID 改变行值
- js和jquery中获取非行间样式
- golang基础之二-基本数据类型和操作符
- Web 服务器被配置为不列出此目录的内容