【Day 5 】2023-11-20 - 232. 用栈实现队列

[azl397985856]

232. 用栈实现队列

入选理由

暂无

题目地址

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

前置知识

• 栈
• 队列

  题目描述

  
  使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。 示例:

MyQueue queue = new MyQueue();

queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false 说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。 假设所有操作都是有效的、 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

[EggEggLiu]

思路

学习官方题解的优雅写法

代码

class MyQueue {
private:
    stack<int> inStack, outStack;

    void in2out() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

public:
    MyQueue() {}

    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        if (outStack.empty()) {
            in2out();
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }

    int peek() {
        if (outStack.empty()) {
            in2out();
        }
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

[Junru281]

Leetcode 232 Nov 20

232. Implement Queue using Stacks

Ideas

The huge difference between a stack and a queue is the order to retrieve an element. By the hint that we are going to us e two stack, we can use one stack to store elements just as queue and use the other stack to reverse the order of one queue. In other words, before we push the new element, we first pop all existing elements and then push the new element to the bottom of a stack. Then push all the element back, so that the first element is still at the top of the stack.

class MyQueue {
    Stack<Integer> queue;
    Stack<Integer> records;

    public MyQueue() {
        queue = new Stack<>();
        records = new Stack<>();
    }

    public void push(int x) {
        while(!queue.empty()){
            int top_queue = queue.pop();
            records.push(top_queue);
        }
        queue.push(x);
        while(!records.empty()){
            int next = records.pop();
            queue.push(next);
        }
    }

    public int pop() {
        return queue.pop();
    }

    public int peek() {
        return queue.peek();
    }

    public boolean empty() {
        if(queue.empty()){
            return true;
        }
        else return false;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

[Chloe-C11]

用两个栈和一个元素记录

class MyQueue:
    def __init__(self):
        # stack1 出
        # stack2 入
        # s1[]
        # s2[1,2]
        # top 1
        self.stack1 = []
        self.stack2 = []
        self.top = None

    def push(self, x: int) -> None:
        if not self.stack2:
            self.top = x
        self.stack2.append(x)

    def pop(self) -> int:
        if not self.stack1:
            while self.stack2:
                self.stack1.append(self.stack2.pop())
        return self.stack1.pop()

    def peek(self) -> int:
        # 返回队列开头的元素
        # 返回最先入栈的元素
        # 拿一个top来记录
        if not self.stack1:
            return self.top
        else:
            return self.stack1[-1]

    def empty(self) -> bool:
        return not self.stack1 and not self.stack2

[joe-the-plumber]

class Stack(object):
    def __init__(self):
        self.stack = []

    def push(self, x):              # 入栈
        self.stack.append(x)

    def pop(self):                  # 出栈
        if self.is_empty:           # 注意特殊情况
            return None
        return self.stack.pop()

    @property
    def length(self):               # 获取栈中元素
        return len(self.stack)

    @property                      
    def is_empty(self):            # 获取栈的状态：是否为空
        return self.length == 0

class MyQueue:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack1 = Stack()                           # 基本栈
        self.stack2 = Stack()                           # 辅助栈

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        self.stack1.push(x)                             # 入栈，即入队列

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        while self.stack1.length > 1:                   # 卡住要出栈的最后一个元素
            self.stack2.push(self.stack1.pop())         # 其他元素倒进辅助栈
        res = self.stack1.pop()                         # 那个被卡住的元素就是所需
        while not self.stack2.is_empty:                 # 只要辅助栈不为空
            self.stack1.push(self.stack2.pop())         # 辅助栈中的元素倒回基本栈
        return res                                      # 返回栈底元素即为出队队头

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        while self.stack1.length > 1:                   # 卡住要出栈的最后一个元素
            self.stack2.push(self.stack1.pop())         # 其他元素倒进辅助栈
        res = self.stack1.pop()                         # 那个被卡住的元素就是所需
        self.stack2.push(res)                           # 记得把被卡住的元素放回
        while self.stack2.length > 0:                   # 只要辅助栈不为空
            self.stack1.push(self.stack2.pop())         # 辅助栈中的元素倒回基本栈
        return res                                      # 返回栈底元素即为出队队头

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return self.stack1.is_empty                     # 队列的状态即为基本栈的状态

[jsaki]

class MyQueue:

    def __init__(self):
        self.stack=[]
        self.ex=0

    def push(self, x: int) -> None:
        self.stack.append(x)
        self.ex+=1
        return self.stack

    def pop(self) -> int:
        self.ex+=1
        return self.stack.pop(0)

    def peek(self) -> int:
        self.ex+=1
        return self.stack[0]

    def empty(self) -> bool:
        if self.ex==0:
            return True
        if not self.stack:
            return True
        return False

[adfvcdxv]

思路

双栈：一个栈输入，一个输出

pop和peek只有在输出栈为空，才将输入栈的元素push到输出栈

代码

var MyQueue = function () {
    this.instack = []
    this.outstack = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
    this.instack.push(x)
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
    if (!this.outstack.length) this.intoout()
    return this.outstack.pop()
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
    if (!this.outstack.length) this.intoout()
    return this.outstack[this.outstack.length - 1]
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
    return !this.outstack.length && !this.instack.length
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */
MyQueue.prototype.intoout = function () {
    while (this.instack.length) {
        this.outstack.push(this.instack.pop())
    }
};

复杂度分析

时间复杂度：O(1)。

空间复杂度：O(n)。

[ycan253]

思路

没有使用双栈实现队列，双栈实现可参考 232. 用栈实现队列（清晰图解）

代码

class MyQueue:

    def __init__(self):
        self.deque = []

    def push(self, x: int) -> None:
        self.deque.insert(0, x)

    def pop(self) -> int:
        return self.deque.pop()

    def peek(self) -> int:
        return self.deque[len(self.deque) - 1]

    def empty(self) -> bool:
        return len(self.deque) == 0

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()

复杂度分析

[rennzhang]

题目

232. 用栈实现队列

思路

按照题目所说，使用两个栈来操作，我的思路是队列每次进行 push 操作时，同时对 栈A 进行入栈操作，直到队列使用pop\peek 方法时，操作 A 栈全部弹出并依次入栈 B，此时栈顶就是队列首部。

队列的push操作依旧全部同时入栈 A，直到栈 B 为空并且队列使用pop\peek时，重复以上步骤。

代码

class MyQueue:

    def __init__(self):
        self.stackA = []
        self.stackB = []

    def push(self, x: int) -> None:
        self.stackA.append(x)

    def pop(self) -> int:
        self.transferEl()
        return self.stackB.pop()

    def peek(self) -> int:
        self.transferEl()
        return self.stackB[-1]

    def empty(self) -> bool:
        return not self.stackA and not self.stackB

    def transferEl(self) -> None:
        if not self.stackB:
            while self.stackA:
                self.stackB.append(self.stackA.pop())

复杂度分析

• 时间复杂度：O(N),

• 空间复杂度：O(N)

[verkru]

牛刀初试🪫

/*
 * @lc app=leetcode.cn id=232 lang=javascript
 *
 * [232] 用栈实现队列
 */

// @lc code=start
/**
 * Initialize your data structure here.
 */
var MyQueue = function () {
  this.stack = [];
};

/**
 * Push element x to the back of queue.
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
  this.stack.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function () {
  return this.stack.length ? this.stack.splice(0, 1) : -1;
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function () {
  return this.stack[0] || -1;
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
  return !this.stack.length;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */
// @lc code=end

时间复杂度为 O(1)，空间复杂度为 O(n)

[Danielyan86]

思路

• 其实不用所谓的双栈，直接用 del stack[0] 就可以实现栈的 pop 功能，但是题目要求必须使用双栈实现
• 很多示例代码处理了 pop 时候 stack 为空的时候情况，其实题目已经说了“例如，一个空的队列不会调用 pop 或者 peek 操作）”

双栈实现

• 两个 list，一个模拟入栈，一个模拟出栈
• pop 和 peek 都操作出栈的 list
• 如果出栈的 list 为空，则把入栈 list 的元素搬过来，用 pop 和 list 方法刚好反转
• 如果两个 list 都为空，则为空

code

class MyQueue:
    def __init__(self):
        self.A, self.B = [], []

    def push(self, x: int) -> None:
        self.A.append(x)

    def pop(self) -> int:
        if self.B:
            return self.B.pop()
        self._move()
        return self.B.pop()

    def peek(self) -> int:
        if self.B:
            return self.B[-1]
        self._move()
        return self.B[-1]

    def _move(self):
        while self.A:
            self.B.append(self.A.pop())

    def empty(self) -> bool:
        return not (self.A or self.B)

# with one list
class MyQueue2(object):
    def __init__(self):
        self._data = []

    def push(self, x):
        self._data.append(x)

    def pop(self):
        if not self.empty():
            first_item = self._data[0]
            del self._data[0]
            return first_item

    def peek(self):
        if not self.empty():
            return self._data[0]

    def empty(self):
        if self._data:
            return False
        else:
            return True

complexity

N is length of the queue

• push, peek, empty is O(1)
• move method : time O(N), space O(N)

[javajianghu]

题目

232. 用栈实现队列

解题思路

1、因为栈的操作是先入后出，那么使用pop的话，是把栈最上层的元素出栈，但是题目要求是把最底层的元素出栈。

2、借助另外一个栈，把这个栈的元素都pop到另外一个栈，那么最底层的元素就变成了最上层的元素。

​ 2.1 创建两个栈，firstStack、secondStack，firstStack用于存储插入顺序的栈，secondStack表示倒叙的栈。

​ 2.2 当插入元素时，需要把secondStack的元素都倒回到firstStack中，然后再push

​ 2.3 当弹出元素时，就把firstStack的元素导出到secondStack中，然后secondStack中pop就可以了。

思路

代码

class MyQueue {

    private Stack<Integer> firstStack = new Stack<>();
    private Stack<Integer> secondStack = new Stack<>();

    public MyQueue() {

    }

    // 将元素 x 推到队列的末尾
    public void push(int x) {
        while (!secondStack.isEmpty()) {
            firstStack.push(secondStack.pop());
        }
        firstStack.push(x);
    }

    //  从队列的开头移除并返回元素
    public int pop() {
        // 把firstStack的全部元素都倒腾到secondStack中
        while (!firstStack.isEmpty()) {
            secondStack.push(firstStack.pop());
        }
        return secondStack.pop();
    }

    // 返回队列开头的元素
    public int peek() {
        while (!firstStack.isEmpty()) {
            secondStack.push(firstStack.pop());
        }
        return secondStack.peek();
    }

    // 如果队列为空，返回 true ；否则，返回 false
    public boolean empty() {
        return firstStack.isEmpty() && secondStack.isEmpty();
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[witerth]

【Day 5】232. 用栈实现队列

232. 用栈实现队列

思路

原本思路每次push都要把输出栈压会输入栈，看官方思路后已改进

代码

var MyQueue = function() {

​    this.s = [];

​    this.s1 = [];

};

/** 

 * @param {number} x

 * @return {void}

 */

MyQueue.prototype.push = function(x) {

​    this.s.push(x);

​    return this.s;

};

/**

 * @return {number}

 */

MyQueue.prototype.pop = function() {

​    if (!this.s1.length) {

​        while (this.s.length) {

​            this.s1.push(this.s.pop());

​        }

​    }

​    return this.s1.pop();

};

/**

 * @return {number}

 */

MyQueue.prototype.peek = function() {

​    if (!this.s1.length) {

​        while (this.s.length) {

​            this.s1.push(this.s.pop());

​        }

​    }

​    return this.s1[this.s1.length -1];

};

/**

 * @return {boolean}

 */

MyQueue.prototype.empty = function() {

​    return !this.s.length && !this.s1.length;

};

/**

 * Your MyQueue object will be instantiated and called as such:

 * var obj = new MyQueue()

 * obj.push(x)

 * var param_2 = obj.pop()

 * var param_3 = obj.peek()

 * var param_4 = obj.empty()

 */

复杂度分析

- 时间复杂度：push和empty复杂的为O(1) pop和peek复杂度为O(N) - 空间复杂度：O(N)

[laurallalala]

class MyQueue(object):

    def __init__(self):
        self.s1, self.s2 = [], []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.s1.append(x)

    def pop(self):
        """
        :rtype: int
        """
        while self.s1:
            self.s2.append(self.s1.pop())
        first = self.s2.pop()
        while self.s2:
            self.s1.append(self.s2.pop())
        return first

    def peek(self):
        """
        :rtype: int
        """
        while self.s1:
            self.s2.append(self.s1.pop())
        first = self.s2[-1]
        while self.s2:
            self.s1.append(self.s2.pop())
        return first

    def empty(self):
        """
        :rtype: bool
        """
        if len(self.s1) == 0:
            return True
        else:
            return False

[kiirii4]

思路

区分了输入和输出栈，只有在输出栈为空时，才从输入栈中取元素压入，如此一来每一个元素最多被分别被压入压出2次

代码

class MyQueue {
public:
    MyQueue() {

    }

    void push(int x) {
        stk1.push(x);
    }

    int pop() {
        int ret = 0;
        if(stk2.empty())
            in2out();
        ret = stk2.top();
        stk2.pop();
        return ret;
    }

    int peek() {
        if( stk2.empty()){
            in2out();
        }
        return stk2.top();
    }

    bool empty() {
        return stk1.empty() && stk2.empty();
    }
private:
    stack<int> stk1;
    stack<int> stk2;

    void in2out(){
        while(!stk1.empty()){
            stk2.push(stk1.top());
            stk1.pop();
        }
    }
};

[emergence23]

思路

参考官方思路 将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。

每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

Code

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new ArrayDeque<Integer>();
        outStack = new ArrayDeque<Integer>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

作者：力扣官方题解 链接：https://leetcode.cn/problems/implement-queue-using-stacks/solutions/632369/yong-zhan-shi-xian-dui-lie-by-leetcode-s-xnb6/ 来源：力扣（LeetCode）

[qingkediguo]

public static class MyQueue {
        private Deque<Integer> inStack;
        private Deque<Integer> outStack;

        public MyQueue() {
            this.inStack = new ArrayDeque<>();
            this.outStack = new ArrayDeque<>();
        }

        public MyQueue push(int x) {
            inStack.push(x);
            return this;
        }

        public int pop() {
            if (outStack.isEmpty()) {
                moveInStackToOutStack();
            }
            return outStack.pop();
        }

        public int peek() {
            if (outStack.isEmpty()) {
                moveInStackToOutStack();
            }
            return outStack.peek();
        }

        public boolean empty() {
            return inStack.isEmpty() && outStack.isEmpty();
        }

        private void moveInStackToOutStack() {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }

[larscheng]

思路

暴力：

• 长度为100的数组 stack存储队列元素，变量len记录已使用的位数
• push：入栈，len++
• peek：返回数组第首个元素
• pop：删除stack[0]，剩余元素整体前移，返回删除的stack[0]
• empty：判断数组第一个元素是否为0

双栈（利用栈：先进后出的特性，来实现队列先进先出）：

• 定义两个栈intput/output
• push：入栈元素压入input（先进后出）
• peek(pop)：若output无元素，将input中的元素压入output(先进后出)，从output中peek(pop)出栈
• empty：判断两个栈中元素是否为空

整体流程如下，通过在两个栈中流转，实现了队列特性：先进先出 压入input[1,2,3] => input出栈[3,2,1] => 压入output[3,2,1] => output出栈[1,2,3]

代码

//双栈
class MyQueue {

    Stack<Integer> input;
    Stack<Integer> output;
    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }

    public void push(int x) {
        input.push(x);
    }

    public int pop() {
        if (output.empty()){
            in2out();
        }
        return output.pop();
    }

    public int peek() {
        if (output.empty()){
            in2out();
        }
        return output.peek();
    }

    private void in2out() {
        while (!input.empty()){
            output.push(input.pop());
        }
    }

    public boolean empty() {
        return input.empty() && output.empty();
    }
}

复杂度

• 时间复杂度：O(1)
• 空间复杂度：O(n)

[freeroo2]

思路

用两个栈，一个输入栈一个输出栈。每次入队操作直接push到输入栈，每次遇到pop/peek就尝试从输出栈输出，若没有元素可输出了，就将输入栈的所有元素全部出栈并依次push到输出栈中，这样输出栈就可以按照队列从前往后的顺序出栈了。

代码

class MyQueue {
        private Stack<Integer> in;
        private Stack<Integer> out;

        public MyQueue() {
            in = new Stack<>();
            out = new Stack<>();
        }

        public void push(int x) {
            in.push(x);
        }

        public int pop() {
            if (out.empty()) {
                in2out();
            }
            return out.pop();
        }

        public int peek() {
            if (out.empty()) {
                in2out();
            }
            return out.peek();
        }

        public boolean empty() {
            return in.isEmpty() && out.isEmpty();
        }

        public void in2out() {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }

[Ludwig-LL]

思路

看到用两个栈来实现队列，就像是用两个#*%#&% 实现#%%&，不懂这个要求的概念。 先查资料： 栈：类似存放的空间，但是像是排队进胡同，要退出来肯定要从最后一个开始退出，然后倒数第二个才能继续。 队列：这个比较像火车过山，最先进的车头也一定会最先出山洞。 （这先进先出、后进先出的概念有点类似会计的存货过程计算）

有了基本的认知之后，就回来再次解读题目：要用两个后进先出的空间，来完成一个先进先出的概念（或是做法） 这样理解并不合理，因为两个先进后出的栈，他们最先进的只能是最后出，那要怎么达到先进的能先出呢？ 想了一下，如果有两个冰棒袋子，这时候我不管拆开的冰棒袋子露出的是冰棒或木板，我都可以用手拿木板。 概念就是如果是冰棒，那倒入到另一个冰棒袋中，这样露出的末尾就会是木板。 （应该是这样） 看了一下力扣里面大家的说法也像是这样子，接下来就是操作。

代码 功力还不足以进行这个情况的操作，偷看了大佬的设定： (目前还不会Markdown 上色，自己看了有点痛苦）

class MyQueue(object):

def __init__(self):
    self.stack1 = []
    self.stack2 = []

def push(self, x):
    self.stack1.append(x)

def pop(self):
    if not self.stack2:
        while self.stack1:
            self.stack2.append(self.stack1.pop())
    return self.stack2.pop()

def peek(self):
    if not self.stack2:
        while self.stack1:
            self.stack2.append(self.stack1.pop())
    return self.stack2[-1]

def empty(self):
    return not self.stack1 and not self.stack2

时间复杂度 还在学习如何对设定进行计算。

[JinhMa]

class MyQueue {
    private Stack<Integer> stackOne;
    private Stack<Integer> stackTwo;
    public MyQueue() {
        this.stackOne = new Stack<Integer>();
        this.stackTwo = new Stack<Integer>();
    }

    public void push(int x) {
        stackOne.add(x);
    }

    public int pop() {
        while (!stackOne.empty()){
            stackTwo.add(stackOne.pop());
        }
        int result = stackTwo.pop();
        while (!stackTwo.empty()){
            stackOne.add(stackTwo.pop());
        }
        return result;
    }

    public int peek() {
        while (!stackOne.empty()){
            stackTwo.add(stackOne.pop());
        }
        int result = stackTwo.peek();
        while (!stackTwo.empty()){
            stackOne.add(stackTwo.pop());
        }
        return result;
    }

    public boolean empty() {
        return stackOne.empty();
    }
}

[snmyj]

class MyQueue:

    def __init__(self):
        self.arr=[]

    def push(self, x: int) -> None:
        self.arr.append(x)

    def pop(self) -> int:
        return self.arr.pop(0)

    def peek(self) -> int:
        return self.arr[0]

    def empty(self) -> bool:
        return not self.arr