用两个栈实现队列

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

代码格式要求

import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node) {   
    }    
    public int pop() {
    }
}

首先做这道题得知道栈的三个基本的方法：
1.pop（）：移除栈顶，并作为返回值返回给函数。
2.push（item）：入栈
3.isEmpty（）判断栈是否为空

解题一

1.思路
栈的特性：先进后出

image.png

队列的特性：先进先出

image.png

解析：使用两个栈来实现一个队列，其实就是组合两个栈，来实现队列，栈是先进后出，队列是先进先出，可使用以下操作使用栈来实现队列：

出队列的操作
把栈1中的元素依次插入到栈2中

image.png

ps：此时栈顶元素就是需要出队列的元素

2.代码

package jianzhi_offer;

import java.util.Stack;

public class Solution5_1 {
    static Stack<Integer> stack1=new Stack<Integer>();//当作主队列
    static Stack<Integer> stack2=new Stack<Integer>();//当作辅助队列
    //入栈函数
    public void push(int node) {
        stack1.push(node);//把元素放入栈1中，直接用栈的push方法
    }
    //出栈函数
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
               stack2.push(stack1.pop());//如果栈2为空，栈1不为空，把栈1的顶部元素放入栈2 中
             }
        }
        return stack2.pop();
     }
    public static void main(String[] args) {
        Solution5_1 testStack=new Solution5_1();
        testStack.push(1);
        testStack.push(2);
        testStack.push(3);
        testStack.push(4);
        System.out.println(testStack.pop());
        System.out.println(testStack.pop());
        System.out.println(testStack.pop());
        System.out.println(testStack.pop());
    }
}
//empty()和isEmpty()的区别

输出结果

image.png

解题二

1.思路
一个用于入队，一个用于出队，两个栈之间的值相互转换

image.png

2.代码

package jianzhi_offer;

import java.util.Stack;

public class Solution5_2 {
    Stack<Integer> stack1=new Stack<Integer>();
    Stack<Integer> stack2=new Stack<Integer>();
    public void push(int node) {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        stack1.push(node);
         //将栈1中的内容存入栈2，可以发现内容顺序反了过来
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }   
    }
    public int pop() {
        return stack1.pop();
    }
    public static void main(String[] args) {
        Solution5_2 testStack=new Solution5_2();
        testStack.push(4);
        testStack.push(5);
        testStack.push(6);
        testStack.push(7);
        System.out.println(testStack.pop());
        System.out.println(testStack.pop());
        System.out.println(testStack.pop());
        System.out.println(testStack.pop());
    }
}

运行结果

image.png