题目:
用两个栈来实现一个队列, 完成队列的 Push 和 Pop 操作. 队列中的元素为 int 类型.
分析:
栈的特点是先进后出, 队列的特点则是先进先出.
题目要求我们用两个栈来实现一个队列, 栈和队列都有入栈 (入队) 的操作, 所以我们可以使用一个栈来模拟入队的操作, 另一个栈用来负责出队.
利用 stack1 模拟入队操作, stack2 模拟出队操作.
当有元素入队时, 就直接压入 stack1 中, 当要出出队时, stack1 中元素弹出的顺序和要求出队的顺序是正好相反的, 我们可以将 stack1 的元素依次弹出, 再压入 stack2 中, 此时 stack2 中元素弹出的顺序, 正好与要求出队的顺序是一致的. 当然每次出队的时候都要判断 stack2 是否为空, 为空的话就将 stack1 中元素弹出再压入 stack2 中, 再弹出 stack2 中的栈顶元素, 如果不为空, 直接弹出栈顶元素即可.
程序:
- C++
- class Solution
- {
- public:
- void push(int node) {
- stack1.push(node);
- }
- int pop() {
- int res;
- if(!stack2.empty()){
- res = stack2.top();
- stack2.pop();
- return res;
- }
- else{
- while(!stack1.empty()){
- stack2.push(stack1.top());
- stack1.pop();
- }
- res = stack2.top();
- stack2.pop();
- return res;
- }
- }
- private:
- stack<int> stack1;
- stack<int> stack2;
- };
- Java
- import java.util.Stack;
- public class Solution {
- Stack<Integer> stack1 = new Stack<Integer>();
- Stack<Integer> stack2 = new Stack<Integer>();
- public void push(int node) {
- stack1.push(node);
- }
- public int pop() {
- int res;
- if(stack2.empty()){
- while(!stack1.empty()){
- stack2.push(stack1.peek());
- stack1.pop();
- }
- }
- res = stack2.peek();
- stack2.pop();
- return res;
- }
- }
剑指 Offer-5. 用两个栈实现队列(C++/Java)
来源: http://www.bubuko.com/infodetail-3280002.html