1. 基础

队列：先进先出，即插入数据在队尾进行，删除数据在队头进行；

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

2. 思路

两个栈实现一个队列的思想：用pushStack栈作为push数据的栈，用popStack栈作为pop数据的栈。

只要是对队列进行push操作，就将数据push入pushStack栈中。

要实现队列的pop操作，有二点原则，如果popStack为空的话那么我们就将pushStack所有的元素放到popStack中，然后取popStack栈顶元素就是队列的队头；如果popStack不为空的话，我们就直接获取popStack的栈顶元素。

对于top操作来说和pop操作类似，只是最后一步不用pop了。

3. 代码

#include <iostream>#include <stack>#include <exception>template<class T> class MyQueue { public: void push(const T& num); // 入队列 T pop(); // 出队列 T top(); private: std::stack<T> pushStack; std::stack<T> popStack;};template<typename T>void MyQueue<T>::push(const T& num) { pushStack.push(num);}template<typename T>T MyQueue<T>::pop() { if (pushStack.empty() && popStack.empty()) { // 如果二个栈都为空 throw std::runtime_error("queue is empty"); } else if (popStack.empty()) { // 如果popStack为空,将pushStack全部元素倒popStack while (!pushStack.empty()) { T data = pushStack.top(); // 获取pushStack栈顶元素 pushStack.pop(); // 出栈 popStack.push(data); } } T data = popStack.top(); popStack.pop(); return data;}template<typename T>T MyQueue<T>::top() { if (pushStack.empty() && popStack.empty()) { // 如果二个栈都为空 throw std::runtime_error("queue is empty"); } else if (popStack.empty()) { // 如果popStack为空,将pushStack全部元素倒popStack while (!pushStack.empty()) { T data = pushStack.top(); // 获取pushStack栈顶元素 pushStack.pop(); // 出栈 popStack.push(data); } } else { // 如果popStack不为空的话直接返回popStack栈顶 T data = popStack.top(); return data; }}int main() { MyQueue<int> myQueue1; myQueue1.push(1); myQueue1.push(2); myQueue1.push(3); myQueue1.push(4); std::cout << "current pop is:" << myQueue1.pop() << std::endl; std::cout << "current pop is:" << myQueue1.pop() << std::endl; std::cout << "current pop is:" << myQueue1.pop() << std::endl; std::cout << "current pop is:" << myQueue1.pop() << std::endl; std::cout << "current pop is:" << myQueue1.pop() << std::endl; return 0;}

4. 参考文献

• 用两个栈实现一个队列——我作为面试官的小结
• C++之用两个栈实现一个队列

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对的支持。