C++实现一个简单的双栈队列
2024-10-08 07:41:22
双栈队列的原理是用两个栈结构模拟一个队列, 一个栈A模拟队尾, 入队的元素全部压入此栈, 另一个栈B模拟队首, 出队时将栈A的元素弹入栈B, 将栈B的栈顶元素弹出
此结构类似汉诺塔, 非常经典, 这里附上C++代码简单实现, 有问题欢迎指出
#include <stack> template <typename T>
class CStkQueue
{
public:
T queuePop(); //出队列
void queuePush(T value); //入队列
size_t queueSize(); //队列长度
bool queueEmpty(); //队列判空 private:
std::stack<T> std_stack_push; //入栈,模拟队尾
std::stack<T> std_stack_pop; //出栈,模拟队首
}; template <typename T>
T CStkQueue<T>::queuePop()
{
T temp; //返回值 //如果出栈不为空,直接将出栈的栈顶元素弹出
if (!std_stack_pop.empty())
{
temp = std_stack_pop.top();
std_stack_pop.pop();
return temp;
} //将入栈元素弹出并压进出栈至仅剩一个元素
while (std_stack_push.size() != )
{
std_stack_pop.push(std_stack_push.top());
std_stack_push.pop();
} //将入栈仅有的一个元素作为返回值弹出
temp = std_stack_push.top();
std_stack_push.pop();
return temp;
} template <typename T>
void CStkQueue<T>::queuePush(T value)
{
//如果出栈不为空,先将出栈元素弹回入栈
while (!std_stack_pop.empty())
{
std_stack_push.push(std_stack_pop.top());
std_stack_pop.pop();
} //元素压栈
std_stack_push.push(value);
} template <typename T>
size_t CStkQueue<T>::queueSize()
{
return (std_stack_push.size() + std_stack_pop.size());
} template <typename T>
bool CStkQueue<T>::queueEmpty()
{
return ((std_stack_push.size() + std_stack_pop.size()) == ) ? true : false;
}
下面做个简单的测试
结果如下
最新文章
- XmlSerializer(Type type, Type[] extraTypes) 内存泄漏
- \(\S2. \)The Ornstein-Uhlenbeck operator and its semigroup
- linux下使用ffmpeg将amr转成mp3
- WCF并发控制与实例模式
- Android Touch(4)我不知道的MotionEvent(*)
- 使你的 Google Summer of Code 建议被接收的5个技巧
- MyBatis之五:动态sql语句
- PGA突破pga_aggregate_target限制
- A记录、CNAME记录、MX记录
- share js 分享代码
- 获取android源码时repo的错误
- 菜鸟的jQuery源码学习笔记(二)
- HtmlAgilityPack --解析Html源码
- Xcode4.5 本地化,多语言设置
- magento寄存器的使用
- 关于JavaScript的那些话
- Mapbox浅析(快速入门Mapbox)
- react Hooks
- 【Javascript系列】变量作用域
- orcl 之 导入和导出(2)