C++中利用两个std::stack实现Queue队列详解
在C++开发中，有时需要利用现成的栈结构来模拟队列行为。本文将深入解析如何使用两个 `std::stack` 容器构建一个符合 FIFO（先进先出）特性的自定义队列类，并提供完整的 C++11 及以上版本的代码实现与原理说明。
设计思路与核心逻辑
队列的核心特征是先进先出（FIFO），而栈的特征是后进先出（LIFO）。仅使用一个栈无法实现队列的逻辑，因为最后进入的元素会最先出来。要实现从栈到队列的转换，我们需要两个栈协作：通常命名为 input_stack 和 output_stack（或文中的 stack1 和 stack2）。
第1步：理解双栈配合机制
目的： 确保后进入栈底的元素最终能位于栈顶，从而优先被弹出。
- 入队操作（Push）： 当新元素进入时，如果
output_stack中有旧数据，必须先将output_stack的所有元素依次弹出并压入input_stack。这样做的目的是将之前的元素“倒手”到另一个栈，腾出位置给新元素。新元素压入output_stack后，再将input_stack中的所有元素重新弹回output_stack。经过这两次翻转，新加入的元素会被沉底，而最早进入的元素依然位于栈顶。 - 出队操作（Pop）： 由于我们在入队时已经维护了顺序，
output_stack的栈顶永远是最早进入队列的元素。因此，出队操作只需直接执行output_stack.pop()即可。
C++ 完整代码实现
以下是基于 `
// StackToQueue.cpp : 定义控制台应用程序的入口点。
// 用两个标准容器stack，实现一个队列
#include "stdafx.h"
#include <iostream>
#include <stack>
using namespace std;
template <class T>
class StackToQueue
{
public:
StackToQueue()
{
// 初始化两个空栈
}
void push(T e)
{
// 1. 将 output_stack 中的现有元素全部转移到 input_stack
while (!stack2.empty())
{
T temp;
temp = stack2.top();
stack2.pop();
stack1.push(temp);
}
// 2. 插入新元素到 output_stack
stack2.push(e);
// 3. 将 input_stack 中的元素全部转回 output_stack
// 此时，新元素在最下面，旧元素在上面，保证栈顶是最老元素
while (!stack1.empty())
{
T temp;
temp = stack1.top();
stack1.pop();
stack2.push(temp);
}
}
void pop()
{
// 直接弹出栈顶（即最早的元素）
if (!empty()) {
stack2.pop();
}
}
T front()
{
if (!empty())
{
return stack2.top();
}
else
{
// 对于非指针类型，返回 NULL 可能引起编译警告或错误，
// 实际应用中建议使用 optional 或抛异常处理空值情况
return NULL;
}
}
bool empty()
{
return stack2.empty();
}
size_t size()
{
return stack2.size();
}
private:
stack<T> stack1, stack2;
};
int _tmain(int argc, _TCHAR* argv[])
{
StackToQueue<int> queue;
int i(0);
cout << "Enter several integer number,and press ctrl+z to the end." << endl;
// 循环读取输入，直到遇到 EOF (Ctrl+Z)
while (cin >> i)
{
queue.push(i);
}
// 验证队列状态
cout << "The front element is: " << queue.front() << endl;
cout << "The size now is: " << queue.size() << endl;
if (!queue.empty())
{
cout << "Pop one element now." << endl;
queue.pop();
}
cout << "The front element is: " << queue.front() << endl;
cout << "The size now is: " << queue.size() << endl;
return 0;
}关键细节与注意事项
时间复杂度分析
虽然每次 `push` 操作涉及两次栈遍历，看起来像是 $O(N)$，但从均摊的角度来看，每个元素最多被压入和弹出各两次。因此，序列操作的平摊时间复杂度仍然是 $O(1)$。这对于大多数应用场景而言是完全可以接受的。
关于 front() 的空值处理
在原代码中，front() 在非空检查失败时返回 `NULL`。对于基本整型变量，这等同于 0。如果在生产环境中用于对象指针或更复杂的泛型编程，建议抛出 std::out_of_range 异常，或者结合 C++17 的 std::optional 来安全地处理无值情况，避免隐式类型转换带来的潜在 Bug。
头文件依赖
代码依赖于 C 风格的预处理头 #include "stdafx.h"（Visual Studio 预编译头）以及标准的 #include <iostream> 和 #include <stack>。在实际移植到其他编译器（如 GCC/Clang）时，可移除 stdafx.h 并将 _tmain 替换为标准的 main。
总结
通过两个 std::stack 的巧妙配合，我们成功实现了具备 FIFO 特性的队列。这种方法展示了 STL 容器适配器的灵活性，即在基础数据结构之上通过算法组合衍生出新的行为模式。以上就是利用两个标准容器stack实现一个队列的方法详解，更多关于C++数据结构设计与实现的资料请关注本站其它相关文章！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
