LeetCode232之用栈实现队列(Implement Queue using Stacks)

一、题目
请输入图片描述

二、一种解题思路

1)介绍:双栈实现队列法

  方法解析:使用两个栈做为基础,一个栈保存输入的元素,另外一个栈将前面栈中的元素保存到自己中,这样就实现了队列的效果,最先进的元素在in栈的栈底,out栈的栈顶。 ()从一个栈到另外一个栈的操作,仅在out栈为empty时进行,也就是实现了队列的先进先出)。

   时间复杂度:O(n)

   空间复杂度:O(n)

2)核心代码:

public class MyQueue {
 
    //两个辅助栈
    private Stack<Integer> in;
    private Stack<Integer> out;
 
    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }
 
    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        in.push(x);
    }
 
    private void repair() {
        while (!in.empty()) {
            out.push(in.pop());
        }
    }
 
    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (out.empty()) {
            repair();
        }
        return out.pop();
    }
 
    /**
     * Get the front element.
     */
    public int peek() {
        while (out.empty()) {
            repair();
        }
        return out.peek();
    }
 
    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

三、LeetCode成功截图

请输入图片描述

四、感想

感觉自己还没做到最好,希望大家有好方法指教下,加油,加油,再加油,坚持,坚持,再坚持。

Last modification:October 25th, 2019 at 12:39 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment