【Day 5 】2021-12-16 - 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 操作）。

[yan0327]

思路： 用两个栈实现一个队列。一个作为队列头栈，一个作为队列尾栈。 插入则直接插入到队列尾栈。弹出和查看队列头，关键要先判断队列头栈是否为空，不空为可直接弹出值或取出队列头。 如果队列头栈为空，则循环将队列尾栈压入队列头栈。 判断是否为空即判断两个栈是否为空即可

type MyQueue struct {
    stackfront []int
    stacktail []int
}

func Constructor() MyQueue {
    return MyQueue{[]int{},[]int{}}
}

func (this *MyQueue) Push(x int)  {
    this.stacktail = append(this.stacktail,x)
}

func (this *MyQueue) Pop() int {
    if len(this.stackfront) > 0{
        out := this.stackfront[len(this.stackfront)-1]
        this.stackfront = this.stackfront[:len(this.stackfront)-1]
        return out
    }
    for len(this.stacktail) > 0{
        this.stackfront = append(this.stackfront,this.stacktail[len(this.stacktail)-1])
        this.stacktail = this.stacktail[:len(this.stacktail)-1]
    }
        out := this.stackfront[len(this.stackfront)-1]
        this.stackfront = this.stackfront[:len(this.stackfront)-1]
    return out
}

func (this *MyQueue) Peek() int {
    if len(this.stackfront) > 0{
        out := this.stackfront[len(this.stackfront)-1]
        return out
    }
    for len(this.stacktail) > 0{
        this.stackfront = append(this.stackfront,this.stacktail[len(this.stacktail)-1])
        this.stacktail = this.stacktail[:len(this.stacktail)-1]
    }
        out := this.stackfront[len(this.stackfront)-1]
    return out
}

func (this *MyQueue) Empty() bool {
    return len(this.stackfront) == 0 && len(this.stacktail)==0
}

时间复杂度 O（n）【内部操作】 外部操作是O（1） 空间复杂度O（N）

[Alexno1no2]

'''python ''' 操作两个栈，一个「输入栈」，一个「输出栈」。 当 push() 新元素的时候，放到「输入栈」的栈顶。 当 pop() 元素的时候，从「输出栈」弹出元素。如果「输出栈」为空，则把「输入栈」的元素逐个 pop() 并且 push() 到「输出栈」中，这一步会把「输入栈」的栈底元素放到了「输出栈」的栈顶。此时再从「输出栈」的 pop() 元素的顺序与「输入序」相同。

''' 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

'''

[Grendelta]

思路

建立两个栈，一个负责输入，一个负责peek和输出 当peek或者输出时，将输入栈的元素放入输出栈

代码

class MyQueue(object):

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

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

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

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

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

复杂度分析

时间复杂度 O(N)

空间复杂度 O(N)

[wxj783428795]

思路

1.使用两个栈，一个为输入栈，一个为输出栈。 2.数据入队列时，把数据压入输入栈。 3.数据出队列时，如果输出栈为空，则依次弹出输入栈的所有元素，并压入输出站。然后弹出输出栈的第一个元素。 4.peek方法就是返回输入栈的第一个元素，或输出站的最后一个元素。 5.empty方法就是判断两个栈是否都为空。

代码

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 === 0) {
        while (this.inStack.length > 0) {
            this.outStack.push(this.inStack.pop())
        }
    }
    return this.outStack.pop()
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
    return this.inStack[0] || this.outStack[this.outStack.length - 1];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
    return this.inStack.length === 0 && this.outStack.length === 0;
};

/**
 * 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() : O(1)
  • peek() : O(1)
  • empty() : O(1)
  • pop() : O(1)
• 空间复杂度：O(n)

[Bochengwan]

思路

通过辅助栈作为pop的存储，通过主栈作为push的存储

代码

class MyQueue:
    from collections import deque
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.main_stack = []
        self.aux_stack = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        if len(self.main_stack) == 0:
            self.front = x
        self.main_stack.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if len(self.aux_stack)==0:

            self.aux_stack = self.main_stack[::-1]
            self.main_stack = []
        return self.aux_stack.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if len(self.aux_stack) == 0:
            return self.front
        return self.aux_stack[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """

        return len(self.main_stack)==0 and len(self.aux_stack)==0

复杂度分析

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

[wujunhong-max]

思路

用两个栈模拟队列，队尾push，队头pop

代码

class MyQueue {
public:
    MyQueue() {

    }

    void push(int x) {
        while(!b.empty())  // 如果b非空
        {
            a.push(b.top());
            b.pop();
        }
        a.push(x);
        while(! a.empty())
        {
            b.push(a.top());
            a.pop();
        }
    }

    int pop() {
        int ret = b.top();
        b.pop();
        return ret;
    }

    int peek() {
        return b.top();
    }

    bool empty() {
        return b.empty();
    }
private:
    stack<int> a,b;
};

/**
 * 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();
 * bool param_4 = obj->empty();
 */

复杂度

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

[CodeWithIris]

Note

• Use two stacks to store the integer. Out_stack is to store the elements like the queue while the in_stack helps to push elements into the out_stack.
• Push: When faced with the push operation, push all the elements of the out_stack into the in_stack and after that, push the new element in. Then, push all the elements of the in_stack into the out_tack.
• Peek: Return the top element of the out_stack because the out_stack's distribution is already the same as the queue.
• Pop: Pop out the top element and return that integer.
• Empty: If the out_stack is empty, return 'true'.

Solution

class MyQueue {
public:
    stack<int> in_queue;
    stack<int> out_queue;
    MyQueue() {

    }

    void push(int x) {
        while(!out_queue.empty()){
            in_queue.push(out_queue.top());
            out_queue.pop();
        }
        in_queue.push(x);
        while(!in_queue.empty()){
            out_queue.push(in_queue.top());
            in_queue.pop();
        }
    }

    int pop() {
        int tmp = out_queue.top();
        out_queue.pop();
        return tmp;
    }

    int peek() {
        return out_queue.top();
    }

    bool empty() {
        if(out_queue.empty()) return true;
        return false;
    }
};

Complexity

• T: O(n)
• S: O(n)

[Alfie100]

直接模拟

Python代码：

class MyQueue:

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

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

    def pop(self) -> int:
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop()) 
        return self.s2.pop()

    def peek(self) -> int:
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop()) 
        return self.s2[-1]

    def empty(self) -> bool:
        if self.s1 or self.s2:
            return False
        else:
            return True

复杂度分析

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

[CoreJa]

思路

将一个栈定义为输入栈，一个栈定义为输出栈。 push就往输入栈里压数据，pop的话就从输出栈里拿数据。如果输出栈里没有数据了，那就将输入栈的所有数据全部倒腾到输出栈里。

这就好像是两个栈把底部黏在了一起，一个吃输入，一个吐输出，这就形成了一个队列。唯一要解决问题是两个栈之间的交流，即输入栈如何把数据挪到输出栈来。那要挪的时候没办法，只能一个一个搬，但是因为pop的总次数和搬运的总次数相当，所以"均摊时间复杂度"为 O(1)。 这里解释一下，假设一共要pop n次，那么我一共也只需要挪n次数据(pop+push)，故均摊下来执行O(2n/n)得到O(1)的时间复杂度

代码

class MyQueue:

    def __init__(self):
        self.front = None
        self.in_stack = []
        self.out_stack = []

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

    def pop(self) -> int:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()

    def peek(self) -> int:
        return self.out_stack[-1] if self.out_stack else self.front

    def empty(self) -> bool:
        return len(self.in_stack) == 0 and len(self.out_stack) == 0

[falconruo]

思路: 使用两个栈head, end来实现队列

复杂度分析:

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

代码(C++):

class MyQueue {
public:
    MyQueue() {

    }

    void push(int x) {
        while (!end.empty()) {
            head.push(end.top());
            end.pop();
        }

        end.push(x);
    }

    int pop() {
        while (!head.empty()) {
            end.push(head.top());
            head.pop();
        }

        int val = end.top();
        end.pop();
        return val;
    }

    int peek() {
        while (!head.empty()) {
            end.push(head.top());
            head.pop();
        }

        return end.top();
    }

    bool empty() {
        return head.empty() && end.empty();
    }
private:
    stack<int> head, end;
};

/**
 * 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();
 * bool param_4 = obj->empty();
 */

[ginnydyy]

Problem

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

Note

• Stack
• No need to use size variable to make the current queue size. Only need to use stack's api.

Solution

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

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

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

    public int pop() {
        if(outStack.empty()){
            toOutStack();
        }
        return outStack.pop();
    }

    public int peek() {
        if(outStack.empty()){
            toOutStack();
        }
        return outStack.peek();
    }

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

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

/**
 * 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();
 */

Complexity

• T: O(1) for push and empty methods. Amortized O(1) for pop and peek methods.
• S: O(n) n is the size of the queue.

[zhy3213]

思路

lazy 倒

代码

class MyQueue:

    def __init__(self):
        self.forward=collections.deque()
        self.backward=collections.deque()

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

    def pop(self) -> int:
        if len(self.backward)==0:
            while self.forward:
                self.backward.append(self.forward.pop())
        return self.backward.pop()

    def peek(self) -> int:
        if not len(self.backward)==0:
            return self.backward[-1]
        return self.forward[0]

    def empty(self) -> bool:
        return len(self.backward)==0 and len(self.forward)==0

[feifan-bai]

思路

1. Using 2 stacks to finalize the Quene
2. Stack2 to store the elements reversely from stack 1
3. Stack1 and front to implement the quene

代码

class MyQueue:

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

    def push(self, x: int) -> None:
        # Push element x to the back of queue
        if not self.stack1:
            self.front = x
        self.stack1.append(x)

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

    def peek(self) -> int:
        if self.stack2:
            return self.stack2[-1]
        return self.front

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

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

复杂度分析

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

[qixuan-code]

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack1.append(x)
        return self.stack1

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        while self.stack1:
            a = self.stack1.pop()
            self.stack2.append(a)
        res= self.stack2.pop()
        while self.stack2:
            b = self.stack2.pop()
            self.stack1.append(b)

        return res

    def peek(self) -> int:
        """
        Get the front element.
        """
        return self.stack1[0]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        if len(self.stack1) == 0:
            return True
        else:
            return False

[wenjialu]

thought

每次在push的时候，就是push在底部。 push之前把stack1先倒腾到stack2，Stack2.append().再倒回去 那pop stack1 321 --》 stack2 123 + 4 ---〉 stack1 4321 # push stack1 4321 pop1 # pop

code

class MyQueue: def init(self): self.stack1 = [] self.stack2 = []

def push(self, x: int) -> None:
    while self.stack1:
        self.stack2.append(self.stack1.pop())
    self.stack2.append(x)
    while self.stack2:
        self.stack1.append(self.stack2.pop())

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

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

def empty(self) -> bool:
    return False if self.stack1 else True

completity

time & space O(n)

[MongoCZK]

思路

• 构建两个栈stack和reverseStack，reverseStack的栈顶始终是最先入栈的元素，即队头
• push操作：若reverseStack为空，则入栈reverseStack，否则，入栈stack
• pop操作：reverseStack弹出栈顶元素，当reverseStack为空时，将stack中的元素依次弹出并入栈reverseStack
• peek操作：取reverseStack的栈顶元素值
• empty操作： 判断两个栈是否均为空

代码

var MyQueue = function() {
  this.stack = []
  this.reverseStack = []
};

/** 
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
  if(this.reverseStack.length > 0){
      this.stack.push(x)
  }else{
      this.reverseStack.push(x)
  }
};

/**
* @return {number}
*/
MyQueue.prototype.pop = function() {
  let item = this.reverseStack.pop()
  if(this.reverseStack.length == 0){
      while(this.stack.length > 0){
          this.reverseStack.push(this.stack.pop())
      }
  }
  return item
};

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

/**
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
  return this.reverseStack.length == 0 && this.stack.length ==0
};

复杂度分析

• 时间复杂度：摊还复杂度 O(1)，最坏情况下的时间复杂度 O(n)
• 空间复杂度： push和pop操作时需要额外的空间来储存元素，空间复杂度为O(n),其他操作为O（1）

[laofuWF]

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        stack2 = []
        while self.stack:
            stack2.append(self.stack.pop())
        res = stack2.pop()

        while stack2:
            self.stack.append(stack2.pop())

        return res

    def peek(self) -> int:
        """
        Get the front element.
        """
        stack2 = []
        while self.stack:
            stack2.append(self.stack.pop())
        res = stack2[-1]

        while stack2:
            self.stack.append(stack2.pop())

        return res

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.stack) == 0

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

[Husky-Gong]

Note

1. When push a new element (we need to add it to the bottom of S1 stack) -- make S1 result stake reverse -> push to S2 stack -- add new element to S2 top -- push back to S1 -> make the new element to the bottom of previous elements

Code

class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {
        // use s1 to record final result
        if (s1.isEmpty()) {
            s1.push(x);
        } else {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }

            s2.push(x);

            while (!s2.isEmpty()) {
                s1.push(s2.pop());
            }
        }
    }

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

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

    public boolean empty() {
        return s1.isEmpty();
    }
}

Complexity

Time Complexity: push: O(n) pop: O(1) peek: O(1) empty: O(1)

Space Complexity: O(n)

[yangziqi1998666]

class MyQueue {
    Stack<Integer> stack;
    Stack<Integer> temp;

    public MyQueue() {
        this.stack = new Stack();
        temp = new Stack();
    }

    /*
    时间复杂度: O(n)
    空间复杂度: O(n)
     */
    public void push(int x) {
        while(!stack.isEmpty())
            temp.push(stack.pop());
        temp.push(x);
        while(!temp.isEmpty())
            stack.push(temp.pop());
    }

    /* 
    Removes the element from the front of queue.
    时间复杂度: O(1)
    空间复杂度: O(1)
    */
    public int pop() {
        return stack.pop();
    }

    /* 
    Get the front element.
    时间复杂度: O(1)
    空间复杂度: O(1)
    */
    public int peek() {
        return stack.peek();
    }

    public boolean empty() {
        return stack.isEmpty();
    }
}

[zwx0641]

思路： 一个栈用来入列，一个用来出列

class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

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

    public int pop() {
        if (!s2.isEmpty()) {
            return s2.pop();
        } else {
            while(!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    public int peek() {
        if (!s2.isEmpty()) {
            return s2.peek();
        } else {
            while(!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

时间: push O(1) pop,peek O(n)

[xj-yan]

class MyQueue:

    def __init__(self):
        self.in_stack, self.out_stack = [], []

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

    def move(self) -> None:
       if not self.out_stack:
            while self.in_stack: self.out_stack.append(self.in_stack.pop())     

    def pop(self) -> int:
        self.move()
        return self.out_stack.pop()

    def peek(self) -> int:
        self.move()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return (not self.in_stack) and (not self.out_stack)

Time Complexity: O(n), Space Complexity: O(n)

[Yrtryannn]

class MyQueue {
    public Stack<Integer> a;
    puiblic Stack<Integer> b;

    public MyQueue() {
        a = new Stack<>();
        b = new Stack<>();
    }

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

    public int pop() {
        if(b.isEmpty()){
            while(!a.isEmpty()){
                b.push(a.pop());
            }
        }
        return b.pop();
    }

    public int peek() {
        if(b.isEmpty()){
            while(!a.isEmpty()){
                b.push(a.pop());
            }
        }
        return b.peek();
    }

    public boolean empty() {
        return a.isEmpty() && b.isEmpty();
    }
}

[SHAO-Nuoya]

队列

Code

class MyQueue:

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

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

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

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

    def empty(self) -> bool:
        if len(self.queue)>0:
            return False
        else:
            return True

[ZhangNN2018]

思路

• 存的时候直接append()就行。
• 删除并返回队首元素的时候，需要从stack1倒腾到stack2，这样才能使stack1栈底（即队首）的元素变成stack2的栈顶。
• 返回队首元素的时候，记得把pop()出的元素，再append()回去，不然就被删了。

复杂度

• 时间复杂度: O(N), pop函数的for循环；
• 空间复杂度：O(N), 引入了两个栈。

代码

class MyQueue(object):

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

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

    def pop(self):
        """
        :rtype: int
        """
        if self.empty():
            return None
        if self.stack2:
            return self.stack2.pop()
        else:
            for i in range(len(self.stack1)):
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

    def peek(self):
        """
        :rtype: int
        """
        ans = self.pop()
        self.stack2.append(ans)
        return ans

    def empty(self):
        """
        :rtype: bool
        """
        return not (self.stack1 or self.stack2)

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

[guangsizhongbin]

type MyQueue struct {
    inStack, outStack []int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (q *MyQueue) Push(x int)  {
    q.inStack = append(q.inStack, x)
}

func (q *MyQueue) Pop() int {
    if len(q.outStack) == 0 {
        for len(q.inStack) > 0 {
            q.outStack = append(q.outStack, q.inStack[len(q.inStack) - 1])
            q.inStack = q.inStack[:len(q.inStack) - 1]
        }
    }
    x := q.outStack[len(q.outStack) - 1]
    q.outStack = q.outStack[:len(q.outStack) - 1]
    return x
}

func (q *MyQueue) Peek() int {
    if len(q.outStack) == 0 {
        for len(q.inStack) > 0 {
            q.outStack = append(q.outStack, q.inStack[len(q.inStack) - 1])
            q.inStack = q.inStack[:len(q.inStack) - 1]
        }
    }
    x := q.outStack[len(q.outStack) - 1]
    return x
}

func (q *MyQueue) Empty() bool {
    return len(q.outStack) == 0 && len(q.inStack) == 0
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

[freesan44]

思路

创建List来实现

关键点

代码

• 语言支持：Python3

Python3 Code:

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.Alist = []
        self.Blist = []
        self.peekIndex = None

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.Alist.append(x)
        if len(self.Alist)== 1:
            self.peekIndex = x

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        #如果B为空，就从A倒到B再处理
        if len(self.Blist) == 0 and len(self.Alist) == 0:
            return None
        if len(self.Blist) != 0:
            return self.Blist.pop()
        else:
            while len(self.Alist)!=0:
                self.Blist.append(self.Alist.pop())
            self.peekIndex = None
            return self.Blist.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if self.Blist.__len__() == 0:
            return self.peekIndex
        else:
            return self.Blist[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        if self.peekIndex == None and len(self.Blist) == 0:
            return True
        else:
            return False

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

复杂度分析

令 n 为数组长度。

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

[JudyZhou95]

思路

把一个stack中的元素转移到另一个stack把栈头转成栈尾，等同于逆序。这个class中有一个input stack和output stack。input stack负责存储输入，output stack负责把元素按照queue的方式输出。O(1)时间复杂度的秘诀就是不要重复来回倒，每个元素只转一次。输出时检查output是否为空，output stack若不为空则直接输出，如果空了就再把input全部倒进去。

代码

class MyQueue:

    def __init__(self):
        self.input = []
        self.output = []

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

    def pop(self) -> int:
        self.move()           
        return self.output.pop()

    def peek(self) -> int:
        self.move()
        return self.output[-1]

    def empty(self) -> bool:
        return len(self.input) == 0 and len(self.output) == 0

    def move(self):
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())

复杂度

Time: O(1) Space: O(n)

[ZacheryCao]

Idea

Stack

Code

class MyQueue:

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

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

    def pop(self) -> int:
        tmp = self.stack[0]
        self.stack = self.stack[1:]
        return tmp

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

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

Complexity:

Time: push, peak, empty: O(1) pop: O(n) Space: O(n)

[declan92]

关键字: 两个栈、实现队列、总操作时间复杂度为O(n);
思路:

1. 队列push操作,全部元素push栈1;
2. 队列pop操作,如果栈2没有元素,将栈1元素全部pop,然后push至栈2;
3. 如果栈2有元素,直接pop栈2;
4. 队列peek操作的实现类似pop;

5. 队列empty,栈1和栈2同为空则队列空,否则非空; java

   class MyQueue {
   Stack<Integer> stackIn;
   Stack<Integer> stackOut;
   public MyQueue() {
        stackIn = new Stack();
        stackOut = new Stack();
   }
   
   public void push(int x) {
       stackIn.push(x);
   }
   
   public int pop() {
       if(empty()){
           return -1;
       }
       if(!stackOut.empty()){
           return stackOut.pop();
       }
       while(!stackIn.empty()){
           stackOut.push(stackIn.pop());
       }
       return stackOut.pop();
   }
   
   public int peek() {
       if(empty()){
           return -1;
       }
       if(!stackOut.empty()){
           return stackOut.peek();
       }
       while(!stackIn.empty()){
           stackOut.push(stackIn.pop());
       }
       return stackOut.peek();
   }
   
   public boolean empty() {
       if(stackIn.empty() && stackOut.empty()){
           return true;
       }
       return false;
   }
   }

   时间:O(n),n为队列长度;队列pop()与peek()获取的元素,全部是从栈1pop,然后push进栈2,一个元素发生一次,n个元素时间复杂度为O(n);
   额外空间:O(1); 错误: peek()操作没写return

[wangzehan123]

代码

• 语言支持：Java

Java Code:

class MyQueue {

    //定义栈
    private Stack<Integer> stackA;
    private Stack<Integer> stackB;

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

    /** Push element x to the back of queue. */
    //栈A入栈
    public void push(int x) {
        stackA.push(x);

    }

    /** Removes the element from in front of queue and returns that element. */
    //栈A出栈到栈B，栈B出栈
    public int pop() {
        if(stackB.isEmpty()) {
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
        }
        return stackB.pop();
    }

    //栈A出栈到栈B，栈B出栈
    /** Get the front element. */
    public int peek() {
        if(stackB.isEmpty()) {
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
        }
        return stackB.peek();
    }

    /** Returns whether the queue is empty. */
    //栈A和栈B都为空
    public boolean empty() {
        if(stackA.isEmpty() && stackB.isEmpty()){
            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();
 */

[Liuxy94]

思路

两个stack stack1装插入 stack2等到pop的时候 辅助stack1 清空

代码

class MyQueue:

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

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

    def pop(self) -> int:
        if self.stack2:
            return self.stack2.pop()
        else:
            self.stack2 = self.stack1[::-1]
            self.stack1 = []
            return self.stack2.pop()

    def peek(self) -> int:
        if self.stack2:
            return self.stack2[-1]
        elif self.stack1:
            return self.stack1[0]

    def empty(self) -> bool:
        if (not self.stack1) and (not self.stack2):
            return True
        else:
            return False

复杂度分析

时间： O(n)

空间：O(n)

[watermelonDrip]

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stk1 = list()
        self.stk2 = list()  # create new queue

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stk1.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self.stk2:
            return self.stk2.pop()
        else:
            while self.stk1:
                self.stk2.append(self.stk1.pop())
            return self.stk2.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if self.stk2:
            return self.stk2[-1]
        while self.stk1:
            self.stk2.append(self.stk1.pop())
        return self.stk2[-1] 

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return (len(self.stk2) == 0 and  len(self.stk1)== 0)

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

[hdyhdy]

思路：用数组实现栈，用栈实现队列

type MyQueue struct {
    in Stack
    out Stack
}

type Stack []int

func Constructor() MyQueue {
    return MyQueue{}
}

func (this *MyQueue) Push(x int)  {
    this.in = append(this.in, x)
}

func (this *MyQueue) Pop() int {
    if len(this.in) == 0 {
        return -1
    }
    que := this.in[0]
    this.in = this.in[1:]
    this.out = append(this.out, que)
    return this.out[len(this.out)-1]
}

func (this *MyQueue) Peek() int {
    return this.in[0]
}

func (this *MyQueue) Empty() bool {
    if len(this.in) == 0 {
        return true
    }
    return false 
}

时间复杂度和空间复杂度均为n

[simbafl]

--java

class MyQueue {
    private Stack<Integer> stackA;
    private Stack<Integer> stackB;

    public MyQueue() {
        stackA = new Stack<Integer>();
        stackB = new Stack<Integer>();
    }

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

    public int pop() {
        if(stackB.isEmpty()) {
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
        }
        return stackB.pop();
    }

    public int peek() {
        if(stackB.isEmpty()) {
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
        }
        return stackB.peek();
    }

    public boolean empty() {
        if(stackA.isEmpty() && stackB.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}

-- python

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

[Yark-yao]

思路

感觉对JS来说，这个题没什么意义，用数组自带的api就可以了

代码

class MyQueue {
    private arr:number[]=[];
    constructor() {
      this.arr = []
    }

    push(x: number): void {
      this.arr.push(x)
    }

    pop(): number {
      return this.arr.shift()
    }

    peek(): number {
      return this.arr[0]
    }

    empty(): boolean {
      return !this.arr.length
    }
}

复杂度

时间：O(1) 都是单个操作

[Victoria011]

思路

使用两个 list, input 用来存输入, output 用来pop 元素(逆序输出)

代码

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

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

    def pop(self):
        self.peek()
        return self.output.pop()

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

    def empty(self):
        return not self.input and not self.output

复杂度分析

Time complexity: O(1)

Space complexity: O(1)

[1052561252]

思路

1.stack的特性是先进后出，queue的特性是先进先出

2.使用2个stack来模拟queue，stack2主要用于存储val，每次新的val都回push进stack2的栈顶

3.每次要执行pop()或peek()时，先将stack2中的val暂存至stack1。因此stack2栈底的val是最先进入的，也就是要返回的数值。这些数值在放入stack1后，会到stack1的栈顶，所以才可以返回

代码

class MyQueue {

    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        this.stack1 = new Stack<>();
        this.stack2 = new Stack<>();
    }

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

    public int pop() {
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        Integer pop = stack1.pop();
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return pop;
    }

    public int peek() {
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        Integer peek = stack1.peek();
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return peek;
    }

    public boolean empty() {
        return stack2.isEmpty();
    }
}

复杂度分析

时间复杂度：

• push():O(1)
• pop():O(n)
• peek():O(n)
• empty:O(1)

空间复杂度：

• O(n)

[moirobinzhang]

class MyQueue:

def __init__(self):
    self.stack_input = []
    self.stack_output = []               

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

def pop(self) -> int:
    if len(self.stack_output) == 0:
        while self.stack_input:
            self.stack_output.append(self.stack_input.pop())
    return self.stack_output.pop()         

def peek(self) -> int:
    if not len(self.stack_output) == 0 :
        return self.stack_output[-1]
    return self.stack_input[0]

def empty(self) -> bool:
    return len(self.stack_input) == 0 and len(self.stack_output) == 0

[zwmanman]

思路

Use two stack

1. push: Everything will be pushed to stack1 first
2. pop: while stack2 is not empty, pop() from stack2, else move everything to stack2 3.peek: if stack is not empty, return last element from stack2 else return front
3. empty: when both stack1 and stack2 are empty then it is empty

代码

class MyQueue(object):

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

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        if len(self.stack1) == 0:
            self.front = x
        self.stack1.append(x)

    def pop(self):
        """
        :rtype: int
        """
        if len(self.stack2) == 0:
            while len(self.stack1) != 0:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    def peek(self):
        """
        :rtype: int
        """
        if self.stack2:
            return self.stack2[-1]
        else:
            return self.front

    def empty(self):
        """
        :rtype: bool
        """
        return len(self.stack1) == 0 and len(self.stack2) == 0

复杂度分析

• 时间复杂度：O(N) for pop()，O(1) for other method
• 空间复杂度：O(N)

[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();
    }
};

[suukii]

Link to LeetCode Problem

S1: 优化模拟

维护两个栈，一个用来写 (push)，一个用来读 (pop)。

往写栈中 push，从读栈中 pop。当读栈为空时，将写栈中的数据全部倒入读栈中。

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
    }

    /** Push element x to the back of queue. */
    void push(int x) {
        write_stack_.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if (read_stack_.empty()) pour_();
        int value = read_stack_.top();
        read_stack_.pop();
        return value;
    }

    /** Get the front element. */
    int peek() {
        if (read_stack_.empty()) pour_();
        return read_stack_.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return read_stack_.empty() && write_stack_.empty();
    }
private:
    stack<int> write_stack_;
    stack<int> read_stack_;

    void pour_() {
        while (!write_stack_.empty()) {
            read_stack_.push(write_stack_.top());
            write_stack_.pop();
        }
    }
};

/**
 * 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();
 * bool param_4 = obj->empty();
 */

• Time: push 是 $O(1)$，pop 均摊下来也是 $O(1)$，连续 N 次的 push 才会碰到一次 $O(N)$ 的 pop。
• Space: $O(N)$

[GaoMinghao]

思路

使用两个栈实现，结合栈FILO的特性和队列FIFO的要求，可以在push的时候进行一次倒腾，均摊时间复杂度可以缩短整体的时间复杂度到O(1)

代码

import java.util.Stack;

class MyQueue {
    Stack<Integer> stack;
    Stack<Integer> tempStack;

    public MyQueue() {
        this.stack = new Stack<>();
        this.tempStack = new Stack<>();
    }

    public void push(int x) {
        if(stack.isEmpty()) {
            stack.push(x);
        } else {
          while(!stack.isEmpty()) {
              tempStack.push(stack.pop());
          }
          stack.push(x);
          while(!tempStack.empty()) {
              stack.push(tempStack.pop());
          }
        }
    }

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

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

    public boolean empty() {
        return stack.isEmpty();
    }
}

时间复杂度 push O(N) pop O(1)

[KennethAlgol]

思路

栈

语言

java

class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(stack2.isEmpty()){
            outStack1ToStack2();
        }
        return stack2.pop();
    }

    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()){
            outStack1ToStack2();
        }
        return stack2.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack2.isEmpty()&&stack1.isEmpty();
    }

    public void outStack1ToStack2(){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
    }
}

复杂度分析

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

[Aobasyp]

思路： 题目要求用栈的原生操作来实现队列，也就是说需要用到 pop 和 push 但是我们知道 pop 和 push 都是在栈顶的操作， 而队列的 enque 和 deque 则是在队列的两端的操作，这么一看一个 stack 好像不太能完成， 所以用两个队列

class MyQueue { Stack pushStack = new Stack<> (); Stack popStack = new Stack<> ();

/** Initialize your data structure here. */
public MyQueue() {

}

/** Push element x to the back of queue. */
public void push(int x) {
    while (!popStack.isEmpty()) {
        pushStack.push(popStack.pop());
    }
    pushStack.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
    while (!pushStack.isEmpty()) {
        popStack.push(pushStack.pop());
    }
    return popStack.pop();
}

/** Get the front element. */
public int peek() {
    while (!pushStack.isEmpty()) {
        popStack.push(pushStack.pop());
    }
    return popStack.peek();
}

/** Returns whether the queue is empty. */
public boolean empty() {
    return pushStack.isEmpty() && popStack.isEmpty();
}

}

复杂度分析 时间复杂度：O(N)， 空间复杂度：O(N)，

[Joyce94]

class MyQueue:

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

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

    def pop(self) -> int:
        top = self.stack1[0]
        for i in range(1, len(self.stack1)):
            self.stack2.append(self.stack1[i])
        self.stack1 = self.stack2
        self.stack2 = []
        return top

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

    def empty(self) -> bool:
        if len(self.stack1) == 0:
            return True 
        return False

[demo410]

思路

• 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
• push的时候，如果stackout为空，是则直接push到stackin中。否则，将stackout中的元素全pop到stackin中再将x push到栈中
• pop的时候，判断stackin是否为空，是则直接pop stackout中的元素、否则，将stackin中的元素全pop到stackout中，然后再将stackout中的栈顶元素pop出来

代码

 private Stack<Integer> stackIn;
    private Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    public void push(int x) {
        if (stackOut.isEmpty()) {
            stackIn.push(x);
        } else{
          while (!stackOut.isEmpty()){
              stackIn.push(stackOut.pop());
          }
          stackIn.push(x);
        }
    }

    public int pop() {

        if (stackIn.isEmpty()) return stackOut.pop();

        else{
            while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
            return stackOut.pop();
        }
    }

    public int peek() {
        if (stackIn.isEmpty()) return stackOut.peek();

        else{
            while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
            return stackOut.peek();
        }
    }

    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

复杂度

• 时间复杂度：每个操作均摊时间复杂度为 O(1) ，执行 n 个操作的总时间复杂度为 O(n)
• 空间复杂度：O(N)

[shamworld]

/**
 * Initialize your data structure here.
 */
var MyQueue = function() {
    this.stackInList = [];
    this.stackOutList = [];
};

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

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    if(!this.stackOutList.length){
        while(this.stackInList.length){
            this.stackOutList.push(this.stackInList.pop());
        }
    }
    return this.stackOutList.pop();
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if(!this.stackOutList.length){
        while(this.stackInList.length){
            this.stackOutList.push(this.stackInList.pop());
        }
    }
    if(!this.stackOutList.length) return null;
    return this.stackOutList[this.stackOutList.length-1];
};

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

[ivangin]

思路

两个栈，一个负责输入，一个负责输出，注意pop和peek的情况分析，2无1有的时候，需要把1里的元素全部压入2。

代码

class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

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

    public int pop() {
        if (!s2.isEmpty()) return s2.pop();
        else {
            while (!s1.isEmpty()) s2.push(s1.pop());
            return s2.pop();
        }
    }

    public int peek() {
        if (!s2.isEmpty()) return s2.peek();
        else {
            while (!s1.isEmpty()) s2.push(s1.pop());
            return s2.peek();
        }
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

/**
 * 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();
 */

[iambigchen]

思路

用栈实现队列，需要将栈整体倒序，借助于另外一个栈B. A.pop -> B.push 即可实现。每次push时，需要先将栈A复原再push，push完后再做倒序操作

关键点

代码

• 语言支持：JavaScript

JavaScript Code:

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

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

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

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
   return  this.list.pop()
};

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

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

复杂度分析

令 n 为数组长度。

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

[gova-i267]

题目：

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

思路：

• 前提：
  1. in 栈只存push的数据
  2. out 是 peek 和 pop 的栈
• 做法：
  1. push 时，直接存 in 栈
  2. pop 和 peek 时需要判断 out 栈是否为空，如果为空，则把 in 栈的数据 pop 后再 push 进 out 栈中(栈是后进先出，经过两次压栈后就变成了先进先出)，在 out 栈中 peek 和 pop
  3. isEmpty 需要同时判断 in 和 out 栈是否为空

Java 代码

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

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

    public int pop() {
        if (out.isEmpty()) {
            int n = in.size();
            for (int i=0;i<n;i++) {
                out.push(in.pop());
            }
        }
        return out.pop();
    }

    public int peek() {
        if (out.isEmpty()) {
            int n = in.size();
            for (int i=0;i<n;i++) {
                out.push(in.pop());
            }
        }
        return out.peek();
    }

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

/**
 * 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();
 */

复杂度分析：

• 时间复杂度：O(n) 一次遍历
• 空间复杂度：O(n) 两个栈辅助存储