20210305 232. 用栈实现队列

题目

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

题解

直接两个栈互相导就可以,栈A导入到栈B里面就是队列的正序

import java.util.Stack;
public class MyQueue {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.push(1);
        myQueue.push(2);
        myQueue.push(3);
        myQueue.push(4);
        System.out.println(myQueue.pop());
        myQueue.push(5);
        System.out.println(myQueue.pop());
        System.out.println(myQueue.pop());
        System.out.println(myQueue.pop());
        System.out.println(myQueue.pop());
    }

    Stack<Integer> stackOne;

    Stack<Integer> stackTwo;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        stackOne = new Stack<>();
        stackTwo = new Stack<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        if (stackOne.size() != 0 || (stackOne.size() == 0 && stackTwo.size() == 0)) {
            stackOne.push(x);
        } else {
            while (!stackTwo.isEmpty()) {
                stackOne.push(stackTwo.pop());
            }
            stackOne.push(x);
        }
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (stackTwo.size() != 0) {
            return stackTwo.pop();
        }
        while (!stackOne.isEmpty()) {
            stackTwo.push(stackOne.pop());
        }
        return stackTwo.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (stackTwo.size() != 0) {
            return stackTwo.peek();
        }
        while (!stackOne.isEmpty()) {
            stackTwo.push(stackOne.pop());
        }
        return stackTwo.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return stackTwo.size() + stackOne.size() == 0;
    }
}
优化

我们每次push都维护了一个全局的正序,所以没次push和pop的时候如果stackTwo有值我们会把two的在放回到one中,保持一个全局的一致性,但是其实可以不这么做,push的时候只需要直接push one即可,pop也直接two的,如果two没有值了,在将one的导入到two中,因为one里面的数据一定在pop的后边,所以并不需要没次push的时候都清空two所以push方法,只需要直接push到one里面即可

发表评论

邮箱地址不会被公开。 必填项已用*标注