【数据结构】两个栈模拟队列

思路

创建一个队列，该队列中包含着两个相同容量的栈，分别是一个数据存入栈（stack1）和数据取出栈（stack2）。数据存入栈负责数据入队列（push），数据取出栈负责数据出队列（pop）。
数据入队列只需在数据存入栈直接存入数据即可。
数据出队列分为三个步骤：

1. 将数据存入栈中的数据全部转移至数据取出栈中。
2. 从数据取出栈中取出数据作为出队列数据。
3. 将数据取出栈中剩余的数据再重新转移至数据存入栈中。

栈部分代码

public class MyStack {

    private int[] stack;
    // 最大容量
    private int capacity;
    // 当前容量
    private int size;
    // 栈的特点：栈顶标记
    private int top;

    public MyStack(int capacity) {
        this.stack = new int[capacity];
        this.capacity = capacity;
        this.size = 0;
        this.top = 0;
    }

    // 入栈
    public void push(int value) throws Exception {
        if (size >= capacity) {
            throw new Exception("Stack is full");
        }
        size ++;
        stack[top ++] = value;
    }

    // 出栈
    public int pop() throws Exception {
        if (size == 0) {
            throw new Exception("Stack is empty");
        }
        size --;
        return stack[-- top];
    }

    public boolean isEmpty() {
        if (top == 0) {
            return true;
        }
        return false;
    }

}

队列部分代码

public class MyQueue {

    // stack1为存入栈，stack2为取出栈
    private MyStack stack1, stack2;

    public MyQueue(int capacity) {
        stack1 = new MyStack(capacity);
        stack2 = new MyStack(capacity);
    }

    public void push(int value) throws Exception {
        stack1.push(value);
    }

    /**
     * 每次取出一个数都要将stack1中所有数全部转移到stack2中，从stack2栈顶取数，再重新返回stack1
     * @return
     * @throws Exception
     */
    public int pop() throws Exception {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        int result = stack2.pop();
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        return result;
    }

}

测试代码

public class Test {

     public static void main(String[] args) throws Exception {
        MyQueue queue = new MyQueue(3);
        queue.push(1);
        queue.push(2);
        queue.push(3);

        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
    }

}