【题目】
- 编写一个类，用两个栈实现队列，支持队列的基本操作（enQueue、deQueue、peek）
【分析】
- 队列的访问规则是First In First Out;栈的访问规则是First In Last Out。
- 用栈来模拟队的访问规则，核心思想就是：将入栈的顺序逆序，然后再出栈
- 根据上面的核心思想，不难看出，我们可以使用两个栈，一个存储队列的入队顺序，一个存储队列的出队顺序
- 入队栈和出队栈的关系：将入队栈的数据不断向出队栈入栈即可。（形象点就是一个杯子往另一个杯子倒东西，前一个杯子的上半部分跑到后一个杯子的下半部分去了，操作起逆序的作用）
- 当出队时，如果存储出队顺序的栈为空时，需要从入队栈更新数据。
- 两个栈皆为空时，队列也为空。
【实现】
- 实现语言：C++
- 源代码如下：
/*由两个栈组成的队列*/
#include<iostream>
#include<stack>
using namespace std;
#define Error -1class TwoStacksQueue
{private:stack<int> m_InputStack; //专供入队的栈stack<int> m_OutputStack; //专供出队的栈public:void enQueue(int value) //入队函数 {m_InputStack.push(value); } int deQueue() //出队函数 {if(m_OutputStack.empty()&&m_InputStack.empty()){cout<<"此队列为空，操作无效！！"<<endl; return Error;}InputToOutput();int temp=m_OutputStack.top();m_OutputStack.pop();return temp;}int peek(){if(m_OutputStack.empty()&&m_InputStack.empty()){cout<<"此队列为空，操作无效！！"<<endl; return Error;}InputToOutput();return m_OutputStack.top();}private://当输出栈为空时，将输入栈的数据转到输出栈中 void InputToOutput(){if(m_OutputStack.empty()){while(!m_InputStack.empty()){m_OutputStack.push(m_InputStack.top());m_InputStack.pop();}}}
};int main()
{TwoStacksQueue queue;queue.enQueue(1);queue.enQueue(2);queue.enQueue(3);queue.enQueue(4);cout<<queue.deQueue()<<endl; queue.enQueue(5);cout<<"获取队首元素："<<queue.peek()<<endl;cout<<queue.deQueue()<<endl; cout<<queue.deQueue()<<endl; cout<<queue.deQueue()<<endl; cout<<queue.deQueue()<<endl;
}
- 控制台截图