232. 用栈实现队列

用两个栈实现队列

import java.util.Stack;

public class Algorithm {

    public static void main(String[] args) {

        MyQueue myQueue = new MyQueue();

        for (int i = 0; i < 10; i++) {

            myQueue.push(i);
            if (i % 2 == 0){
                myQueue.pop();
            }
            System.out.println(myQueue.peek());
        }
    }
}

class MyQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;
    int topElement;

    public MyQueue() {

        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {

        /**
         * 队首元素是第一个入栈的元素,因此栈为空时入栈的元素就是队首元素
         */
        if (stack1.isEmpty()){
            topElement = x;
        }
        stack1.push(x);
    }

    public int pop() {

        /**
         * 当需要出队时,队首元素在栈底,把栈底元素上面的元素全部转移到另一个栈
         * 新栈的栈顶就是新的队首
         * 此时stack2的出栈顺序和队列的出队顺序一致,不用急着把元素再还原回去,如果再次调用pop(),直接让stack2出栈,直到stack2为空
         */
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {

        if (!stack2.isEmpty()) {
            return stack2.peek();
        }

        /**
         * 如果stack2空了,那队首就是stack1的栈底(即最先入栈的那个元素)
         */
        return topElement;
    }

    public boolean empty() {

        /**
         * stack1和stack2同时为空,队列才为空
         */
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

https://leetcode-cn.com/problems/implement-queue-using-stacks/

上一篇:数据挖掘与分析练习——蘑菇(涉及聚类、降维)


下一篇:【点宽专栏】国信证券——关于量化选股之聚类分析的探讨