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

[yanglr]

思路

使用两个栈

使用两个栈s1, s2设计一个"队列", 就是要求弄出一个容器, 按照先进先出的要求工作, 且注意栈必须是从同一端插入和弹出。而"队列"是从一端插入、另一端弹出。

s1用来做一开始的push, pop功能使用s2做反向：将s1中的数全扔到s2中，再从s2中取时顺序就是先进先出了。

代码

实现语言: C++

class MyQueue {
    stack<int> s1, s2;
    int front;

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

    /** Push element x to the back of queue. */
    void push(int x) {
        if(s1.empty())
            front = x;

        s1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(s2.empty()){
            while(!s1.empty()){     /* 把s1中的元素全部移到s2中 */
                s2.push(s1.top());
                s1.pop();
            }
        }
        int res = s2.top();
        s2.pop();

        return res;
    }

    /** Get the front element. */
    int peek() {
        if(!s2.empty())
            return s2.top();

        return front;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

代码已上传到: leetcode-ac/91algo daily - github.com

复杂度分析

• 时间复杂度： push: O(1) pop: 平均 O(1) peek: O(1) empty: O(1)

• 空间复杂度：O(n)

[yachtcoder]

Use a helper stack and data stack. The data stack handles push() in O(1). Helper stack handles pop() and peek() by holding data in a reverse order we push to the data stack. We only load the helper stack when it is empty. Time: amortized O(1) Space: O(n)

class MyQueue:

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

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

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

    def d2h(self):
        while self.data:
            self.helper.append(self.data.pop())

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

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

[last-Battle]

思路

关键点

• 用2个栈去模拟
• push就往realst里面搞
• pop和peek就先看helperst，不为空就搞helperst，为空就把realst里面的元素都搞到helperst里面
• empty同时判断realst和helperst是否都为空

代码

• 语言支持：C++

C++ Code:

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

    }

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

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int res;
        if (helperst.empty()) {
            while (!realst.empty()) {
                helperst.push(realst.top());
                realst.pop();
            }
        }
        res = helperst.top();
        helperst.pop();

        return res;
    }

    /** Get the front element. */
    int peek() {
        if (helperst.empty()) {
            while (!realst.empty()) {
                helperst.push(realst.top());
                realst.pop();
            }
        }

        return helperst.top();
    }

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

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

复杂度分析

令 n 为数组长度。

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

[fzzfgbw]

思路

代码

type MyQueue struct {
    stack []int
}

/** Initialize your data structure here. */
func Constructor() MyQueue {
    return MyQueue{}
}

/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {
    this.stack = append(this.stack,x)
}

/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
    pop:=this.stack[0]
    this.stack = this.stack[1:]
    return pop
}

/** Get the front element. */
func (this *MyQueue) Peek() int {
    return this.stack[0]
}

/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
    return len(this.stack) == 0
}

复杂度分析

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

[BpointA]

思路

使用双栈。一个输入，一个输出。在输出栈用pop，将结果push到输入栈，即可保持输出栈pop结果与队列相同。

Python3代码

class MyQueue:

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

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

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

        return self.outstk.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if len(self.outstk)==0:
            while len(self.instk)>0:
                self.outstk.append(self.instk.pop())

        return self.outstk[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.instk)==0 and len(self.outstk)==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()

复杂度

时间复杂度：O(1)，均是push和pop的组合

空间复杂度：O(n)，n为栈长度，共利用了两个栈

[pzl233]

思路

用两个stack in and out，在push的时候只push到in上面，而当需要取出来的时候，如果out不含任何元素，那就把in里面的元素全部转移到out里面，这样的话最早push进in里面的就会变成out的top，从而满足queue的要求

代码

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

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        peek();
        return out.pop();
    }

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

    /** Returns whether the queue is empty. */
    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) 空间复杂度: Amortized O(1)

[yuxiangdev]

class MyQueue { Stack s1 = new Stack<>(); Stack s2 = new Stack<>(); int front; /* Initialize your data structure here. / public MyQueue() { this.front = front; }

/** Push element x to the back of queue. */
public void push(int x) {
    if (s1.isEmpty()) {
        front = x;
    }
    while (!s1.isEmpty()) {
        s2.push(s1.pop());
    }
    s2.push(x);
    while (!s2.isEmpty()) {
        s1.push(s2.pop());
    }  
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
    if (!s1.isEmpty()) {
        int pop = s1.pop();
        if (!s1.isEmpty()){
            front = s1.peek();
        }
        return pop;
    }
    return -1;
}

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

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

}

[nonevsnull]

思路

借助两个栈，一个input-stack用于接收push，一个output-stack用于pop；

• 所有的push都进入input；
• 所有的pop都出自output；
• 如果output空了，就从input提取；

代码

/*
1. init two stacks: input and output
2. when push, push to the input
3. when pop, pop from output, if output is empty, pop from input to output, then pop from output
*/

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

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

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(!out.isEmpty()){
            return out.pop();
        } else if(!in.isEmpty()){
            while(!in.isEmpty()){
                out.add(in.pop());
            }
            return out.pop();
        } else {
            return Integer.MIN_VALUE;
        }
    }

    /** Get the front element. */
    public int peek() {
        if(!out.isEmpty()){
            return out.peek();
        } else if(!in.isEmpty()){
            while(!in.isEmpty()){
                out.add(in.pop());
            }
            return out.peek();
        } else {
            return Integer.MIN_VALUE;
        }
    }

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

复杂度

push: O(1); pop/peek: 如果output-stack站内有元素，O(1)，如果没有，O(M)，M是当前input站内的元素数量； isEmpty: O(1)

space: O(N),需要维护两个栈，如果这两个栈算是计划内，那就为O(1)，即除栈外只需常数空间。

[chang-you]

思路

使用两个Stack:
s1:代表的是没进行处理的stack, aka queue的反方向. s2: 处理过的stack, 和queue方向一样.

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()) {
            return stack2.pop();
        } else {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }

    }

    /** Get t he front element. */
    public int peek() {
        if (!stack2.isEmpty()) {
            return stack2.peek();
        } else {
            while (!stack1.isEmpty()) {
                stack2.push((stack1.pop()));
            }
            return stack2.peek();
        }
    }

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

复杂度

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

Space = O(n)

[JiangyanLiNEU]

Two Ideas

Two stacks

• Use two stacks
• stack1 stores elements, stack2 is only used when someone call pop and peek.
• pop all elements in stack1 and append them into stack2
• after find the right elements, do the same thing from stack2 to stack1

  One stack, one index indicating the location of the first element in the stack

• index is always the location of the first elements in the stack
• every time we pop, we increase index by 1.

Implement

• 2 stacks (Runtime = O(n) Space = O(n) )

  class MyQueue(object):
  def __init__(self):
      self.stack1 = []
      self.stack2 = []
  def push(self, x):
      self.stack1.append(x)
  def helper(self, array1, array2):
      while array1:
          array2.append(array1.pop())
      return 
  def pop(self):
      self.helper(self.stack1, self.stack2)
      target = self.stack2.pop()
      self.helper(self.stack2, self.stack1)
      return target
  def peek(self):
      self.helper(self.stack1, self.stack2)
      target = self.stack2[-1]
      self.helper(self.stack2, self.stack1)
      return target
  def empty(self):
      return len(self.stack1) == 0

• Index and stack ( Runtime = O(1) Space = O(n) )

  class MyQueue(object):
  def __init__(self):
      self.stack1 = []
      self.index = 0
  def push(self, x):
      self.stack1.append(x)
  def pop(self):
      target = self.stack1[self.index]
      self.index += 1
      return target
  def peek(self):
      return self.stack1[self.index]
  def empty(self):
      return self.index > len(self.stack1)

[ai2095]

LC232. Implement Queue using Stacks

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

Topics

• Stack
• Queue

Similar Questions

Easy

• https://leetcode.com/problems/implement-stack-using-queues/

思路

Separate the input and output. Only move the elements from input to output when needed, so that the complexity can be amortized O(1).

代码 Python

class MyQueue:

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

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

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        self.peek()
        return self.output.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if len(self.output) == 0:
            while len(self.input) > 0:
                self.output.append(self.input.pop())
        return self.output[-1]

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

复杂度分析

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

[leungogogo]

LC232. Implement Queue using Stacks

Main Idea

We can use stack1 as the input stack, and stack2 as the output stack.

• push(): Push to stack1, so this new element will be on the stack top of stack1 (which is the end of our queue).
• pop() and peek(): Since we use stack2 as our output stack, when we call pop() or peek():
• If stack2 is empty, we want to move all elements from stack1 to stack2, and their order will be reversed, so the bottom of stack1 will be the top of stack2, which is the head of our queue.

• If not, then we have access to the top of stack2 already.

  Code

  class MyQueue {
  private Deque<Integer> stack1;
  private Deque<Integer> stack2;
  private int size;
  /** Initialize your data structure here. */
  public MyQueue() {
      stack1 = new ArrayDeque<>();
      stack2 = new ArrayDeque<>();
      size = 0;
  }
  
  /** Push element x to the back of queue. */
  public void push(int x) {
      stack1.push(x);
      ++size;
  }
  
  /** Removes the element from in front of queue and returns that element. */
  public int pop() {
      if (empty()) return -1;
      peek();
      --size;
      return stack2.pop();
  }
  
  /** Get the front element. */
  public int peek() {
      if (empty()) return -1;
      if (stack2.isEmpty()) {
          while (!stack1.isEmpty()) {
              stack2.push(stack1.pop());
          }
      }
      return stack2.peek();
  }
  
  /** Returns whether the queue is empty. */
  public boolean empty() {
      return size == 0;
  }
  }

  Complexity Analysis

  Time:

• push(): O(1)
• pop() and peek():
  • The worst case of pop() and peek() will be O(n), where we have to move all elements from stack1 to stack2.
  • Amortized Analysis: Say we have n elements in stack1, and 0 elements in stack2, and we want to call pop() or peek() n times. The first call will take n operations to move all elements from stack2 to stack1. But after the first call we will have at least n - 1 elemetns in stack2, which makes the next n - 1 calls O(1). So the amrotized time will be O(n + 1 + 1 +...+1 / n) = O((2n-1)/n) = O(1).

Space: O(1), the two stacks are given and we didn't use any extra spaces.

[shixinlovey1314]

Title:232. Implement Queue using Stacks

Question Reference LeetCode

Solution

We use 1 stack for push(push_stack) and the other stack for pop(pop_stack). Initialy, we only push data to the stack, until there's an requst for peek or top. When peek or top, if pop_stack is not empty, pop the item from the pop_stack, otherwise, pop all the items from the push_stack and push them into the pop_stack.

Code

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

    }

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

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int val =  peek();
        pop_stack.pop();

        return val;
    }

    /** Get the front element. */
    int peek() {
        if (!pop_stack.empty())
            return pop_stack.top();

        while(!push_stack.empty()) {
            pop_stack.push(push_stack.top());
            push_stack.pop();
        }

        return pop_stack.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return push_stack.empty() && pop_stack.empty();
    }

private:
    stack<int> push_stack;
    stack<int> pop_stack;
};

Complexity

Time Complexity and Explaination

Push: O(1)
Pop: O(n) for worst case,  Amortized O(1)
Peek: O(n) for worst case, Amortized O(1)
empty: O(1)

Space Complexity and Explaination

O(n)

[zhangzz2015]

关键点

• 队列先进先出，栈后进先出。利用两个栈进行reverse操作。例如[ 1 2 3 4 5] 出栈的顺序为5 4 3 2 1。队列的顺序为1 2 3 4 5。如果使用两个栈，把第一个栈的出栈再放入另外一个栈[5 4 3 2 1]。在出栈的顺序则为1 2 3 4 5 和队列顺序相同。具体实现，所有的入栈放入栈1。不要马上把栈1的内容出栈放入栈2。出栈操作栈2。只有当栈2的内容为空时，才把栈1内容移动到栈2。平均的时间复杂度为O(2)。所有的元素入栈两次，出栈两次，先入栈1，再出栈1，再入栈2，再出栈2。空间复杂度为O(2N)。需要两个栈维护栈内元素。

C++ Code:

class MyQueue {
public:
    /** Initialize your data structure here. */
    vector<int> stack1;
    vector<int> stack2; 
    MyQueue() {

    }

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

        stack1.push_back(x); 

    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        transferStack1ToStack2();
        int topVal = stack2.back();
        stack2.pop_back();
        return topVal;                                
    }

    /** Get the front element. */
    int peek() {
        transferStack1ToStack2(); 
        return stack2.back();
    }

    /** Returns whether the queue is empty. */
    bool empty() {

        return stack1.size()==0 && stack2.size()==0; 

    }
private:
    void transferStack1ToStack2()
    {
        if(stack2.size()==0)
        {
            while(stack1.size())
            {
                int topVal = stack1.back(); 
                stack2.push_back(topVal);
                stack1.pop_back();
            }            
        }        
    }
};

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

[falconruo]

思路:

使用两个栈stack s1, s2用于push, pop/peek

复杂度分析:

1. 时间复杂度: O(1)， 平均时间
2. 空间复杂度: O(n), n为队列长度

代码(C++):

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

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        s1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        int val = s2.top();
        s2.pop();
        return val;
    }

    /** Get the front element. */
    int peek() {
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        return s2.top();
    }

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

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

[wangwiitao]

思路

用俩个栈，从一个挪出来到另一个，在另一个出栈时，顺序就对了

代码

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

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

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

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

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
    return this.inStack.length == 0 && this.outStack.length == 0
};
MyQueue.prototype.in2out = function () {
    while (this.inStack.length) {
        this.outStack.push(this.inStack.pop());
    }
}
/**
 * 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,enpty,O(1),peek,pop,O(N)
• 空间复杂度：O(N)

[thinkfurther]

思路

两个stack，一个用于主要数据存储，另外一个用于pop的时候临时存储

代码

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)
    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        while(self.stack1 != []):
            self.stack2.append(self.stack1.pop())
        returnValue = self.stack2.pop()
        while(self.stack2 != []):
            self.stack1.append(self.stack2.pop())
        return returnValue 
    def peek(self) -> int:
        """
        Get the front element.
        """
        while(self.stack1 != []):
            self.stack2.append(self.stack1.pop())
        returnValue = self.stack2.pop()
        self.stack1.append(returnValue)
        while(self.stack2 != []):
            self.stack1.append(self.stack2.pop())
        return returnValue
    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return True if self.stack1 == [] else False

复杂度

时间复杂度: O(N)

空间复杂度: O(N)

[comst007]

232. 用栈实现队列

思路

• 内部使用两个栈st_in， st_out， 和一个记录st_in栈底的in_base。
• 执行push(x)的时候， 将x放入st_in这个栈，如果在入栈之前st_in 为空，则in_base = x。
• 执行pop()的时候， 如果st_out为空，则先将st_in中的数据出栈然后压入st_out栈中。将st_out栈顶弹出。
• 执行peek()的时候， 如果st_out为空，则队列的第一个元素是in_st的栈底元素， 返回in_base， 如果st_out不为空， 则返回'st_out'的栈顶元素.。
• 执行empty()的时候， 如果st_in 和 st_out都为空则返回true, 否则返回false。

---

代码

• C++

class MyQueue {
private:
    stack<int> st_in;
    stack<int> st_out;
    int in_base;
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        if(st_in.empty()){
            in_base = x;
        }
        st_in.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(st_out.empty()){
            while(!st_in.empty()){
                st_out.push(st_in.top());
                st_in.pop();
            }
        }
        int tp = st_out.top();
        st_out.pop();
        return tp;
    }

    /** Get the front element. */
    int peek() {
        if(st_out.empty()){
            return in_base;
        }

        return st_out.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return st_in.empty() && st_out.empty();
    }
};

---

复杂度分析

栈中元素规模为n

• 时间复杂度： push操作为O(1), empty操作为O(1)， peek操作为O(1)， pop操作因为在'st_out'为空的时候会发生数据从'st_in'转移到'st_out'的操作，st_in中的数据都会经历一次出栈入栈操作。所以pop操作并不是每次操作都是O(1)。
• 空间复杂度 ：O(n)

[Menglin-l]

思路：

用栈A模拟入队，栈B模拟出队。

元素入队时，push进栈A；出队时，将元素pop出栈A，再push进栈B，最后pop，以实现先进先出。

(做完题了才知道还有“java中的Stack有设计上的缺陷，官方推荐使用Deque代替Stack”这个说法。。。先打卡。。。)

---

代码部分：

class MyQueue {

    private Stack<Integer> sA;
    private Stack<Integer> sB;

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

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

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (!empty()) {
            if (!sB.empty()) return sB.pop();
            else {
                while (!sA.empty()) {
                    sB.push(sA.pop());
                }
            }
            return sB.pop();
        }
        else return -1;
    }

    /** Get the front element. */
    public int peek() {
        if (!empty()) {
            if (!sB.empty()) return sB.peek();
            else {
                while (!sA.empty()) {
                    sB.push(sA.pop());
                }
            }
            return sB.peek();
        }
        else return -1;
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        if (sA.empty() && sB.empty()) return true;
        else return false;
    }
}

---

复杂度：

Time: O(1)

Space: O(N)

[cicihou]

class MyQueue:

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

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

    如果用栈的思想来做，栈在 push 不能保证先入先出的
    每一次要用一个help_stack 实现栈的翻转
    while self.stack:
        self.help_stack.append(self.stack.pop())
    self.help_stack.append(x)
    while self.help_stack:
        self.stack.append(self.help_stack.pop())
    """
    self.item.append(x)

def pop(self) -> int:
    """
    Removes the element from in front of queue and returns that element.
    """
    return self.item.pop(0)

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

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

[mmboxmm]

思路

一个负责入，一个负责出。双栈。

代码

class MyQueue() {
  /** Initialize your data structure here. */
  private val inStack = ArrayDeque<Int>()
  private val outStack = ArrayDeque<Int>()

  /** Push element x to the back of queue. */
  fun push(x: Int) = inStack.addLast(x)

  /** Removes the element from in front of queue and returns that element. */
  fun pop(): Int {
    prep()
    return outStack.removeLast()
  }

  /** Get the front element. */
  fun peek(): Int {
    prep()
    return outStack.last()
  }

  private fun prep() {
    if (outStack.isEmpty()) {
      require(inStack.isNotEmpty())
      while (inStack.isNotEmpty()) {
        outStack.addLast(inStack.removeLast())
      }
    }
  }

  /** Returns whether the queue is empty. */
  fun empty(): Boolean = inStack.isEmpty() && outStack.isEmpty()
}

复杂度分析

• Time: amortized O(1)

[ruohai0925]

思路

关键点

代码

• 语言支持：Python3

Python3 Code:

class MyQueue:

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

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

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        return self.stack.pop()

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

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

复杂度分析

时间复杂度：O(1)，均是push和pop的组合

空间复杂度：O(n)，n为栈长度，共利用了两个栈

[heyqz]

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)

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

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

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

Complexity

• time complexity: O(1)
• space complexity: O(n)

[pophy]

思路

• 队列FIFO 栈FILO 所以考虑用2个栈 2次进出操作模拟队列
• 分为压入栈和弹出栈 inStack outStack
  • push操作时 元素进inStack
  • pop时 如果outStack为空 就弹出全部inStack元素到outStack 然后pop
  • 不为空就直接pop

Java Code

class MyQueue {

    Deque<Integer> inStack = new LinkedList();
    Deque<Integer> outStack = new LinkedList();

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

    }

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

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (empty()) {
            return -1;
        } 
        if (outStack.isEmpty()) {
            dump();
        }
        return outStack.pop();
    }

    /** Get the front element. */
    public int peek() {
        if (empty()) {
            return -1;
        } 
        if (outStack.isEmpty()) {
            dump();
        }
        return outStack.peek();
    }

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

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

}

时间 & 空间

• 时间
  • push/pop O(1)
• 空间
  • o(n)

[Jding0]

思路

双栈，解决队列

代码 (Python)

class MyQueue:

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

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

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())

        return self.outstack.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())

        return self.outstack[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.instack) == len(self.outstack) == 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()

复杂度分析

• 时间：O(N)
• 空间: O(N)

[MonkofEast]

232. Implement Queue using Stacks

Click Me

Algo

1. KEY: 1 stack in + 1 stack out = 1 queue
2. I choose push to be O(n), other O(1)

Code

class MyQueue:
    # if want to use deque
    # from collections import deque

    # but here I just use list
    """
     LC is not smart enough to check operation used.....
     So self limit that stacks can only use pop()
    """
    # 2 stacks for mutually containing
    # stack 1 receive push(), stack take pop()

    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.
        """
        # I push everything to stack 2 back, stack 1 holds nothing
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        # then append at tail
        self.stack1.append(x)
        # then push everything back to stack 2
        while self.stack1:
            self.stack2.append(self.stack1.pop())

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        # harder push() makes pop() easier
        return self.stack2.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        # in fact a pointer will do, whatever
        return self.stack2[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not 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()

Comp

T: O(N) for push(), O(1) for others

S: O(N)

[erik7777777]

思路

2 stacks

代码

class MyQueue {
    Deque<Integer> push;
    Deque<Integer> pop;
    int size;
    /** Initialize your data structure here. */
    public MyQueue() {
        push = new ArrayDeque<>();
        pop = new ArrayDeque<>();
        size = 0;
    }

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

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        peek();
        size--;
        return pop.pop();
    }

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

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

复杂度

push: O(1) peek: O(n) pop: O(n) size: O(1)

[zol013]

Python 3 code:

class MyQueue:

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.stack1 = []
    self.size1 = 0
    self.stack2 = []
    self.size2 = 0
def push(self, x: int) -> None:
    """
    Push element x to the back of queue.
    """
    self.stack1.append(x)

def pop(self) -> int:
    """
    Removes the element from in front of queue and returns that element.
    """
    while self.stack1:
        self.stack2.append(self.stack1.pop())
    pop_val = self.stack2.pop()
    while self.stack2:
        self.stack1.append(self.stack2.pop())
    return pop_val
def peek(self) -> int:
    """
    Get the front element.
    """
    while self.stack1:
        self.stack2.append(self.stack1.pop())
    peek_val = self.stack2[-1]
    while self.stack2:
        self.stack1.append(self.stack2.pop())
    return peek_val

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

Time complexity: pop: O(1) push O(1), peek O(n) Space complexity: O(n)

[yiwchen]

思路： 双栈

C++

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

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

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

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

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

    /** Get the front element. */
    int peek() {
        if (outStack.empty()) {
            inToout();
        }
        return outStack.top();
    }
    /** Returns whether the queue is empty. */
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

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

Complexity: TC: pop: O(1) push O(1), peek O(n) SC: O(n) from the stack size

[XinnXuu]

思路

用两个栈来模拟队列，栈1负责push，栈2负责pop，每次队列出列入列时先检查负责另一个功能的栈中是否有元素，有则全部出栈到本栈，再进行push或者pop（也就是每次队列push或pop时总要先把另一个栈排空）。如此操作使得队列尾在栈1顶，队列首在栈2顶。

代码

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

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

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

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

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

复杂度分析

• 时间复杂度：push/pop/peek操作为O(N)，N为栈的长度。其他操作O(1)。
• 空间复杂度：O(N)，使用了两个栈。

[littlemoon-zh]

day 5

232 Implement Queue using Stacks

Stack is FILO and queue is FIFO. In order to implement FIFO using FILO, we need two stacks.

When we add a new element, we push it into stack1. When we retrieve the element, it's at the bottom of stack1. Then we pop all the elements from stack1 to stack2, then the desired element is on the top of stack2.

Next time we want to push an element, just push it to stack 1. If we want to retrieve an elements, it has two cases, 1 if stack2 is not empty, pop from it, 2 if stack 2 is empty, we pop all the elements from stack1 to stack2, then we pop from stack2.

class MyQueue {
    LinkedList<Integer> s1;
    LinkedList<Integer> s2;

    public MyQueue() {
        s1 = new LinkedList<>();
        s2 = new LinkedList<>();
    }

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

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

        return s2.pop();
    }

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

        return s2.peek();
    }

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

[BlueRui]

Problem 232. Implement Queue using Stacks

Algorithm

• Use two stacks to implement the queue
• Each element will be first pushed into stack1.
• If stack2 is not empty, we will pop from stack2. If stack2 is empty, when pop/peek is called on the queue, we pop all elements in stack1 and push them to stack2. After this, the head of the queue is at the top of stack2.

Complexity

• push(): time complexity O(1).
• pop(): amortized time complexity O(1). Each element will only be moved from stack1 to stack2 once with total time of O(n). If we pop n times, the amortized time for each pop() is O(1).
• peek(): same as pop().

Code

Language: Java

class MyQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;

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

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

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

    /** Get the front element. */
    public int peek() {
        if (!stack2.isEmpty()) {
            return stack2.peekFirst();
        }
        while (!stack1.isEmpty()) {
            stack2.addFirst(stack1.removeFirst());
        }
        return stack2.peekFirst();
    }

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

[Maschinist-LZY]

思路

参考了官方题解的双栈思路，一个入栈，一个出栈

代码

• 语言支持：C++

C++ Code:

class MyQueue {
private:
    stack<int> S_a,S_b;

    void move(){
        while(!S_a.empty()){
            S_b.push(S_a.top());
            S_a.pop();
        }
    }
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

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

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

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

    /** Returns whether the queue is empty. */
    bool empty() {
        return S_b.empty() && S_a.empty();
    }
};

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

复杂度分析

令 n 为数组长度。

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

[a244629128]

思路

利用两个stack一个装数据

pushStack是专门放push的数据

popStack 是放要pop的数据

每次执行pop 都会先检查popStack是否为空是的话就从pushStack调去数据，不是的话就直接pop popStack里面的数据

是否empty 要检查两个stack的长度都为零才算empty

代码

javascript

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

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

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

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
      if(this.popStack.length === 0){
        while(this.pushStack.length >0){
            this.popStack.push(this.pushStack.pop());
        }
    }
    return this.popStack[this.popStack.length -1];
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.popStack.length === 0 && this.pushStack.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()
 */

[st2yang]

思路

• 两个stack

代码

• python

  class MyQueue:
  
  def __init__(self):
      """
      Initialize your data structure here.
      """
      self.push_stack = []
      self.pop_stack = []
  
  def push(self, x: int) -> None:
      """
      Push element x to the back of queue.
      """
      self.push_stack.append(x)
  
  def pop(self) -> int:
      """
      Removes the element from in front of queue and returns that element.
      """
      self.peek()
  
      return self.pop_stack.pop()
  
  def peek(self) -> int:
      """
      Get the front element.
      """
      if not self.pop_stack:
          while self.push_stack:
              self.pop_stack.append(self.push_stack.pop())
  
      return self.pop_stack[-1]
  
  def empty(self) -> bool:
      """
      Returns whether the queue is empty.
      """
      return len(self.push_stack) == 0 and len(self.pop_stack) == 0

复杂度

• 时间: O(1)
• 空间: O(n)

[pangjiadai]

思路

用两个list, append(), pop() 实现队列: [12345] -> [54321]

• 一个stack用来接收元素，一个stack用来pop元素
• 什么时候pop stack1的元素？当stack2为空的时候将stack1中的元素pop出来，pop全部元素直到stack1为空

Python3

class MyQueue:
    # 一个stack用来接收元素，一个stack用来pop元素
    # 需要等到self.stack2为空的时候再将stack1的元素弹出

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

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

    def pop(self) -> int:
        if self.stack2 == []:
            while self.stack1 != []:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    def peek(self) -> int:
        if self.stack2 == []:
            while self.stack1 != []:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]

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

复杂度：

time: pop()，peak() -> O(n), 其他为O(1) space: O(n)

[yyangeee]

232

思路

两个栈，一个负责pop,一个负责push

代码

class MyQueue:

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

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

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

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

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

复杂度

• 时间复杂度：$O(N)$, N 为数组长度。
• 空间复杂度：$O(N)$。

[hwpanda]

时间复杂度：O(n)

空间复杂度: O(n)

class MyQueue {
    constructor() {
        this.helperStack = [];
        this.outputStack = [];
    }

    //Pushes element x to the back of the queue.
    push(x) {
        this.outputStack.push(x);
    }

    //Removes the element from the front of the queue and returns it.
    pop() {
        if (this.helperStack.length === 0) {
            while (this.outputStack.length !== 0) {
                this.helperStack.push(this.outputStack.pop());
            }
        }
        return this.helperStack.pop();
    }

    //Returns the element at the front of the queue.
    peek() {
        if (this.helperStack.length === 0) {
            while (this.outputStack.length !== 0) {
                this.helperStack.push(this.outputStack.pop());
            }
        }
        return this.helperStack[this.helperStack.length - 1];
    }

    //Returns true if the queue is empty, false otherwise.
    empty() {
        return this.outputStack.length === 0 && this.helperStack.length === 0;
    }
}

[florenzliu]

Explanation

• Use stack 1 to keep the newly added element (push)
• Use stack 2 to store the current elements of stack 1 in the reverse order, i.e., the sequence of queue elements (pop)
• The last element in the stack 1 will be the last element in the queue.
• The last element in the stack 2 will be the first element in the queue.

Python

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.st1 = [] # keep the newly added element on top of stack 1
        self.st2 = []        

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

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

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

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not self.st1 and not self.st2

Complexity		push	pop	peek	empty
Time Complexity	O(1)	amortized O(1), worst-case O(n)	O(1)	O(1)
Space Complexity	O(n)	O(1)	O(1)	O(1)

[Daniel-Zheng]

思路

使用两个Stack，一个Push，另一个Pop。

代码(C++)

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

    }
    stack<int> res;
    stack<int> help;
    /** Push element x to the back of queue. */
    void push(int x) {
        while (!help.empty()) {
            res.push(help.top());
            help.pop();
        }
        res.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while (!res.empty()) {
            help.push(res.top());
            res.pop();
        }
        int ans = help.top();
        help.pop();
        return ans;
    }

    /** Get the front element. */
    int peek() {
        while (!res.empty()) {
            help.push(res.top());
            res.pop();
        }
        int ans = help.top();
        return ans;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return res.empty() && help.empty();
    }
};

复杂度分析

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

[chenming-cao]

解题思路

创建两个栈in和out分别储存入列元素和出列元素，in栈元素出栈然后入栈得到out栈，顺序相反，可以实现FIFO。当有元素入列时，push进in栈。当有元素出列时，先看out栈是否非空，如果为空将in栈中元素导入到out栈中，然后出列。

代码

class MyQueue {

    Stack<Integer> in;
    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);
    }

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

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

    /** Returns whether the queue is empty. */
    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();
 */

复杂度分析

• 时间复杂度：push和empty为O(1)，pop和peek平均O(1)，最坏O(n)
• 空间复杂度：O(n)，使用了两个栈

[Mahalasu]

思路

用两个栈实现队列，则在push或者pop的时候，选择其中一个操作将所有的item都添加到一个stack中，另一个操作就可以简单append或者pop，实现queue的功能。

class MyQueue:

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

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

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        result = self.stack2.pop()
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        self.size -= 1
        return result

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

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

T: O(N) S: O(N)

[tongxw]

思路

两个栈分别负责入列和出列； 入列时直接把元素压进入列栈； 出列时先检查出列的栈是否为空，如果不空就直接取栈顶元素；如果空就把入列栈的所有元素转移到出列栈； peek()同理； 判空的时候要判断两个栈是否同时为空。

代码

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

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

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

  if (this.outStack.length === 0) {
    this.peek();
  }
  return this.outStack.pop(); 
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if (this.empty()) {
      return -1;
    }

    if (this.outStack.length === 0) {
      while(this.inStack.length !== 0) {
        this.outStack.push(this.inStack.pop());
      }
    }

    return this.outStack[this.outStack.length - 1];
};

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

复杂度分析

• 时间复杂度： push O(1), pop / peek 最坏情况O(n), empty O(1)
• 空间复杂度：O(n)

[okbug]

思路

一个类继承于Array 可以原生实现push方法，只需要重写pop为shift即可，并且添加peek和empty方法

代码

class MyQueue extends Array {
    constructor() {
        super();
    }

    pop() {
        return this.shift();
    }

    peek() {
        return this[0];
    }

    empty() {
        return this.length === 0
    };
}

这是基于数组的shift方法实现的

[zhangyalei1026]

Main idea:

• Two stack. One is for input, the other one is for output.
• When push, add element to input stack.
• When pop, transfer all elements in input stack to helper from top. And return the top element in helper which is bottom element in input stack

• when peek, use the same strategy mention above.

  Code

  class MyQueue:
  
  def __init__(self):
      """
      Initialize your data structure here.
      """
      self.stack = []
      self.helper = []
  
  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.
      """
      if len(self.stack) == 0:
          return 
      while self.stack:
          self.helper.append(self.stack.pop())
      temp = self.helper.pop()
      while self.helper:
          self.stack.append(self.helper.pop())
      return temp
  
  def peek(self) -> int:
      """
      Get the front element.
      """
      if len(self.stack) == 0:
          return 
      while len(self.stack) > 1:
          self.helper.append(self.stack.pop())
      temp = self.stack.pop()
      self.helper.append(temp)
      while self.helper:
          self.stack.append(self.helper.pop())
      return temp
  
  def empty(self) -> bool:
      """
      Returns whether the queue is empty.
      """

  Complexity

  Time complexity: O(n) Space complexity: O(n)

[kidexp]

thoughts

use two stacks, one is used to push, one for pop

whenever we do pop or peek, we will check the 2nd stack is empty or not, if empty, we will push all the first stack's content into it

when check empty we will check both stack are empty

code

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

    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.
        """
        if not self.queue:
            while self.stack:
                self.queue.append(self.stack.pop())
        return self.queue.pop()

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

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

complexity

all operation takes O(1) amortized

space complexity O(n))

[freesan44]

思路

peekIndex作为指针记录最后一位，Alist和Blist实现push和pop，在pop里面等BList空了才把A倒过去

代码

• 语言支持：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(1)$
• 空间复杂度：$O(n)$

[ImSingee]

struct MyQueue {
    stack_for_push: Vec<i32>,
    stack_for_pop: Vec<i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyQueue {

    /** Initialize your data structure here. */
    fn new() -> Self {
        MyQueue {
            stack_for_push: Vec::new(),
            stack_for_pop: Vec::new(),
        }
    }

    /** Push element x to the back of queue. */
    fn push(&mut self, x: i32) {
        self.stack_for_push.push(x);
    }

    fn clean(&mut self) {
        if self.stack_for_pop.is_empty() {
            while let Some(x) = self.stack_for_push.pop() {
                self.stack_for_pop.push(x);
            }
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    fn pop(&mut self) -> i32 {
        self.clean();

        self.stack_for_pop.pop().unwrap()    
    }

    /** Get the front element. */
    fn peek(&mut self) -> i32 {
        self.clean();

        self.stack_for_pop.last().unwrap().to_owned()
    }

    /** Returns whether the queue is empty. */
    fn empty(&self) -> bool {
        self.stack_for_push.is_empty() && self.stack_for_pop.is_empty()
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * let obj = MyQueue::new();
 * obj.push(x);
 * let ret_2: i32 = obj.pop();
 * let ret_3: i32 = obj.peek();
 * let ret_4: bool = obj.empty();
 */

时间复杂度: O(1)

[skinnyh]

Note

• Use input stack and output stack. Push new numbers to the input stack. When doing pop, if output stack is empty, move all the numbers from input stack to the output stack so the order is reversed.

Solution

class MyQueue:

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

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

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if not self.out_stack:
            self.peek()
        return self.out_stack.pop()

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

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

Time complexity: O(1) amortized. Every number only gets among the two stacks once.

Space complexity: O(N)

[HZHENGZHI]

思路 利用两个栈保存队列的出队和入队顺序 代码

class MyQueue {
        Stack<Integer> in;
        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);
            out.clear();
            for (int i=in.size()-1; i >=0; i--) {
                out.push(in.get(i));
            }

        }

        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            in.clear();

            int data=out.pop();
            for (int i =out.size()-1; i >=0; i--) {
                in.push(out.get(i));
            }
            return data;
        }

        /** Get the front element. */
        public int peek() {
            return out.peek();
        }

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

复杂度

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