C++用两个队列实现栈

article/2025/8/27 13:49:42

1. 基础

队列：先进先出，即插入数据在队尾进行，删除数据在队头进行；
栈：后进先出，即插入与删除数据均在栈顶进行。

2. 思路

两个队列实现一个栈的思想：用dataQueue队列作为push数据的队列，用helpQueue队列暂存数据。

只要是对栈进行push操作，就将数据push入dataQueue队列中。
要实现栈的pop操作，就要在dataQueue队列不为空的情况下，把dataQueue队列中的N-1个数据按照队列的pop规则，都转移到helpQueue队列中，直到dataQueue中的数据只有一个时结束转移，然后我们将dataQueue最后一个元素返回就是栈顶元素。这个时候我们对dataQueue进行pop操作，dataQueue变成空队列，而此时helpQueue有N-1个元素。所以最后一步我们交换两个队列，让其可以一直pop操作。
对于top操作来说和pop操作类似，唯一的不同就是我们需要将res在放到我们的helpQueue里面。

3. 代码

#include <iostream>
#include <queue>
#include <exception>template<class T> class MyStack {public:void push(const T& num);T pop();T top();void swapQueue();// 交换dataQueue和helpQueueprivate:std::queue<T> dataQueue;    // 数据队列std::queue<T> helpQueue;    // 帮助队列
};
template<typename T>
void MyStack<T>::swapQueue() {std::queue<T> tmp = dataQueue;dataQueue = helpQueue;helpQueue = tmp;
}
template<typename T>
void MyStack<T>::push(const T& num) {   // 不管是上面情况,送入数据都是放到dataQueue里面dataQueue.push(num);
}
template<typename T>
T MyStack<T>::pop() {if (dataQueue.empty()) {throw std::runtime_error("queue is empty");} else {while (dataQueue.size() > 1) {  // 当dataQueuehelpQueue.push(dataQueue.front());dataQueue.pop();}T res = dataQueue.front();    // 这个dataQueue的最后元素也就是stack的栈顶元素dataQueue.pop();    // dataQueue已经为空,helpQueue存放n-1个数swapQueue();   // 交换二个队列return res;}
}
template<typename T>
T MyStack<T>::top() {if (dataQueue.empty()) {throw std::runtime_error("queue is empty");} else {while (dataQueue.size() > 1) {  // 当dataQueueT data = dataQueue.front();dataQueue.pop();helpQueue.push(data);}T res = dataQueue.front();    // 这个dataQueue的最后元素也就是stack的栈顶元素dataQueue.pop();    // 此时dataQueue已经为空,helpQueue存放n-1个数helpQueue.push(res);    // 获取top元素需要将原来数据返回swapQueue();return res;}
}int main() {MyStack<int> s;s.push(4);s.push(6);s.push(3);s.push(1);std::cout << s.pop() << std::endl;std::cout << s.pop() << std::endl;s.push(5);std::cout << s.pop() << std::endl;std::cout << s.pop() << std::endl;return 0;
}