【Day 5 】2023-02-18 - 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 操作）。

[xiaoDingc]

       public class MyQueue
        {
            private Stack<int> s1, s2;
            public MyQueue()
            {
                s1=new Stack<int>();
                s2=new Stack<int>();
            }

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

            public int Pop()
            {
                Peek();
                return s2.Pop();
            }

            //1 2 3 // 3 2 1
            public int Peek()
            {
                if (s2.Count==0)
                {
                    while (s1.Count!=0)
                    {
                        s2.Push(s1.Pop());
                    }
                }
                return s2.Peek();
            }

            public bool Empty()
            {
                if (s1.Count==0 && s2.Count==0)
                {
                    return true;
                }
                return false;
            }
        }

[yfu6]

1. We can use python's append and pop function to build a stack and implement these functions. 2 Code:

   class MyQueue:
   
   def __init__(self):
       self.arr=[]
   
   def push(self, x: int) -> None:
       self.arr.append(x)
   
   def pop(self) -> int:
       return self.arr.pop(0)
   
   def peek(self) -> int:
       return self.arr[0]
   
   def empty(self) -> bool:
       return not self.arr

2. Time and Space:O(n)

[snmyj]

class MyQueue {
public:
    stack<int> s1,s2;
    MyQueue() {

    }

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

    int pop() {
       while(!s1.empty()){
       s2.push(s1.top());
       s1.pop();
       }
       return(s2.top());
       s2.pop();
    }

    int peek() {
        int p=s2.top();
        return p;
    }

    bool empty() {
        if(!s1.empty()||!s2.empty())
        return false;
        else return true;
    }
};

[Zoeyzyzyzy]

/* 
 * imlpement a FIFO queue using only 2 stacks, stack is FILO, 
 * so we can think of use one stack to store In and other for Out.
 * We can also have a variable to store front value to decrease time complexity.
 */

class MyQueue {
    LinkedList<Integer> stackIn;
    LinkedList<Integer> stackOut;

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

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

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

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

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

//Time Complexity: push(), empty(): O(1), pop() and peek() amortized time complexity(best situation) : O(1)
//Space Complexity: O(n)

class MyQueue1 {
    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;
    int front;

    public MyQueue1() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    public void push(int x) {
        if (stack1.isEmpty())
            front = x;
        stack1.push(x);
    }

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

    }

    public int peek() {
        if (!stack2.isEmpty())
            return stack2.peek();
        return front;
    }

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

//Time Complexity: push(), empty(), peek(): O(1), pop(): amortized time complexity(best situation) : O(1)
//Space Complexity: O(n)

[huifeng248]

use only one stack. python pop(0) and append can do the work

class MyQueue:

    def __init__(self):
        self.stack_one = []
        # self.stack_two = []

    def push(self, x: int) -> None:
        self.stack_one.append(x)
        # self.stack_two.insert(0, x)

    def pop(self) -> int:
        res = self.stack_one.pop(0)
        # res = self.stack_two.pop(0)
        return res

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

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

pop(0) is O(n). others are O(1)

[enrilwang]

class MyQueue { Deque inStack; Deque outStack;

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

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

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

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

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

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

}

[LIMBO42]

class MyQueue {
private:
    stack<int> st1;
    stack<int> st2;
public:
    MyQueue() {

    }

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

    int pop() {
        if(!st2.empty()) {
            int res = st2.top();
            st2.pop();
            return res;
        }
        while(!st1.empty()) {
            int num = st1.top();
            st1.pop();
            st2.push(num);
        }
        int res = st2.top();
            st2.pop();
            return res;
    }

    int peek() {
        if(!st2.empty()) {
            int res = st2.top();
            return res;
        }
        while(!st1.empty()) {
            int num = st1.top();
            st1.pop();
            st2.push(num);
        }
        return st2.top();
    }

    bool empty() {
        return st1.empty() && st2.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();
 */

[Leonalhq]

class MyQueue(object):

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

def push(self, x):
    """
    :type x: int
    :rtype: None
    """
    self.s.insert(0,x)

def pop(self):
    """
    :rtype: int
    """
    return self.s.pop()

def peek(self):
    """
    :rtype: int
    """
    return self.s[-1]

def empty(self):
    """
    :rtype: bool
    """
    return not self.s

[Meisgithub]

用两个栈来模拟

class MyQueue {
private:
    stack<int> stk1;
    stack<int> stk2;

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

public:
    MyQueue() {

    }

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

    int pop() {
        if (stk2.empty())
        {
            move();
        }
        int ans = stk2.top();
        stk2.pop();
        return ans;
    }

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

    bool empty() {
        return stk1.empty() && stk2.empty();
    }
};

[wangqianqian202301]

思路

stack1用于push, stack2用于pop 如果stack2没有元素pop, stack1中的全部元素弹出到stack2中

代码

class MyQueue:

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

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

    def pop(self) -> int:
        if len(self.stack2) == 0:
            length = len(self.stack1)
            for i in range(length):
                self.stack2.append(self.stack1.pop())
        if len(self.stack2) == 0:
            return None
        else:
            return self.stack2.pop()

    def peek(self) -> int:
        peekEle = self.pop()
        if peekEle is not None:
            self.stack2.append(peekEle)
        return peekEle

    def empty(self) -> bool:
        return len(self.stack1) == 0 and len(self.stack2) == 0

复杂度

push O(1) pop O(1)

[JiangyanLiNEU]

class MyQueue:

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

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

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

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

    def empty(self) -> bool:
        if not self.queue:
            return True
        return False

• space = O(N)
• time = O(1) except that pop() is O(N)

[Fuku-L]

思路

使用ArrayDeque的栈作为数据结构。 设计两个栈，一个栈用来保存push的数据，一个栈用来保存pop的数据。

对应方法思考：

1. 入队：每次入队时直接入队就可以。
2. 出队：每次出队从pop栈中取值，如果pop栈中没有数据，就将push栈中的数据放到pop栈中，再将队头数据出栈。
3. peek()：和出队思路一样，只是将 pop() 操作改为 peek()。
4. 判断为空：需要判断两个栈是否都为空。

代码

class MyQueue {
    Deque<Integer> push_stack;
    Deque<Integer> pop_stack;
    public MyQueue() {
        this.push_stack = new ArrayDeque<Integer>();
        this.pop_stack = new ArrayDeque<Integer>();
    }

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

    public int pop() {
        if(pop_stack.isEmpty() && push_stack.isEmpty()){
            return -1;
        } else if(pop_stack.isEmpty()){
            while(!push_stack.isEmpty()){
                pop_stack.push(push_stack.pop());
            }
        } 
        return pop_stack.pop();
    }

    public int peek() {
        if(pop_stack.isEmpty() && push_stack.isEmpty()){
            return -1;
        } else if(pop_stack.isEmpty()){
            while(!push_stack.isEmpty()){
                pop_stack.push(push_stack.pop());
            }
        } 
        return pop_stack.peek();
    }

    public boolean empty() {
        return pop_stack.isEmpty() && push_stack.isEmpty();
    }
}

复杂度分析

• 时间复杂度：push()和empty()：O(1)，pop()，peek()：平均为O(1)。
• 空间复杂度：O(N)，其中 N 为数组长度。

[kofzhang]

思路

两个栈，instack和outstack 每次入队列的时候放入instack。 出队列的时候从outstack出。如果outstack没有数据了就把所有的instack的数据倒到outstack里。

复杂度

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

代码

class MyQueue:

    def __init__(self):
        self.instack = []
        self.outstack = []

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

    def pop(self) -> int:
        if not self.outstack:
            self.in2out()
        return self.outstack.pop()

    def in2out(self) -> None:        
            while self.instack:
                self.outstack.append(self.instack.pop())

    def peek(self) -> int:
        if not self.outstack:
            self.in2out()
        return self.outstack[-1]

    def empty(self) -> bool:
        if self.instack or self.outstack:
            return False
        return True

[bookyue]

TC: push O(1), pop O(n), peek O(n)
OC: O(n)

class MyQueue {
    private final Deque<Integer> in;
    private final Deque<Integer> out;

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

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

    public int pop() {
        transfer();
        return out.pop();
    }

    public int peek() {
        transfer();
        return out.peek();
    }

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

    private void transfer() {
        if (!out.isEmpty()) return;

        while (!in.isEmpty())
            out.push(in.pop());
    }
}

[Size-of]

var MyQueue = function() { this.a = [] this.b = [] };

/**

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

/**

• @return {number} */ MyQueue.prototype.pop = function() { if (this.b.length) return this.b.pop() while (this.a.length) { this.b.push(this.a.pop()) } return this.b.pop() };

/**

• @return {number} */ MyQueue.prototype.peek = function() { if (this.b.length) return this.b[this.b.length - 1] while (this.a.length) { this.b.push(this.a.pop()) }

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

/**

• @return {boolean} */ MyQueue.prototype.empty = function() { return !this.a.length && !this.b.length }; 时间复杂度push，empty O(1),peek pop 均摊O(1), 空间复杂度O(N)

[Horace7]

var MyQueue = function() {
    this.os = []; // 出队栈
    this.is = []; // 入队栈
};

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

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    if (!this.os.length) {
        while(this.is.length) {
            this.os.push(this.is.pop())
        }
    }
    return this.os.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if (!this.os.length) {
        while(this.is.length) {
            this.os.push(this.is.pop())
        }
    }
    return this.os[this.os.length - 1]
};

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

[csthaha]

复杂度：

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

代码：

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

    push(x) {
        this.list.push(x);
    }

    pop() {
        if(!this.size()) return;
        return this.list.shift();
    }

    size() {
        return this.list.length;
    }

    peek() {
        if(!this.size()) return;
        return this.list[0];
    }

    empty() {
        return this.size() === 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()
 */

[aoxiangw]

class MyQueue:

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

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

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

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

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

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

[Abby-xu]

class MyQueue:

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

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

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

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

    def empty(self):
        return not self.s1 and not self.s2 

[xiaoq777]

思路

使用两个栈模拟，peek或pop操作时将第一个栈中的元素全部移动到第二个栈中(第一个栈的栈顶元素将被放到第二个栈的栈底)。 这样从第二个栈的栈顶取元素相当于整体顺序先入先出。

代码

class MyQueue {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public MyQueue() {

    }

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

    public int pop() {
        move();
        if(!stack2.isEmpty()) {
            return stack2.pop();
        }else {
            return -1;
        }
    }

    public int peek() {
        move();
        return stack2.peek();
    }

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

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

复杂度分析

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

[Elsa-zhang]

class MyQueue:

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

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

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

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

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

[lp1506947671]

思路

构建两个栈一个作为输入栈,一个作为输出栈,输入栈逐个弹出放到输出栈,再从输出栈逐个弹出元素,则可以负负的正

实现先进先出

代码

class MyQueue:

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

    def push(self, x: int) -> None:
        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:
        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:
        if not self.in_stack and not self.out_stack:
            return True
        else:
            return False

复杂度

时间复杂度:push和empty的时间复杂度O(1),pop和peek时间复杂度为O(n)

空间复杂度:O(n)

[zpbc007]

思路

队列：先入先出 栈：先入后出 为了能快速的从栈中读取栈底的值，可以使用两个栈：

• 一个栈用于插入数据
• 一个栈用于读取数据 当读取数据栈为空时，从插入数据栈中把所有数据再导入到读取数据栈，这样原始数据经过两次 先入后出 就变成了 先入先出

代码

// push to top, peek/pop from top, size, 和 is empty 操作是合法的。
class MyStack<T> {
    private valueContainer: T[] = []

    push(val: T) {
        this.valueContainer.push(val)
    }

    pop(): T | undefined {
        return this.valueContainer.pop()
    }

    peek(): T | undefined {
        return this.valueContainer[this.valueContainer.length - 1]
    }

    size(): number {
        return this.valueContainer.length
    }

    isEmpty(): boolean {
        return this.valueContainer.length === 0
    }
}

export class MyQueue {
    // 插入数据
    private insertStack = new MyStack<number>()
    // 读取数据
    private readStack = new MyStack<number>()

    constructor() {}

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

    pop(): number {
        if (!this.readStack.isEmpty()) {
            return this.readStack.pop()!
        }

        if (!this.insertStack.isEmpty()) {
            this.insert2Read()

            return this.readStack.pop()!
        }

        return -1
    }

    peek(): number {
        if (!this.readStack.isEmpty()) {
            return this.readStack.peek()!
        }

        if (!this.insertStack.isEmpty()) {
            this.insert2Read()

            return this.readStack.peek()!
        }

        return -1
    }

    empty(): boolean {
        return this.readStack.isEmpty() && this.insertStack.isEmpty()
    }

    private insert2Read() {
        while(!this.insertStack.isEmpty()) {
            this.readStack.push(this.insertStack.pop()!)
        }
    }
}

复杂度分析

时间复杂度

• push、empty: O(1)
• pop、peek: O(1) （每个元素只会在两个栈中各出现一次）

空间复杂度

O(N)

[Hughlin07]

class MyQueue {

Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();

public MyQueue() {

}

public void push(int x) {
    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();
}

}

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

[JasonQiu]

• Use the second stack as a reversed stack

  class MyQueue:
  
  def __init__(self):
      self.stack = []
      self.stackR = []
  
  def push(self, x: int) -> None:
      self.stack.append(x)
  
  def pop(self) -> int:
      if len(self.stackR) == 0:
          for i in range(len(self.stack)):
              self.stackR.append(self.stack.pop(-1))
      return self.stackR.pop(-1)
  
  def peek(self) -> int:
      if len(self.stackR) == 0:
          for i in range(len(self.stack)):
              self.stackR.append(self.stack.pop(-1))
      return self.stackR[-1]
  
  def empty(self) -> bool:
      return len(self.stack) == 0 and len(self.stackR) == 0

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

[liuxiner]

var MyQueue = function () {
    this.stack1 = [];
    this.stack2 = [];
};

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

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
    if (this.stack2.length === 0) {
        while (this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
    if (this.stack2.length === 0) {
        while (this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    const top = this.stack2.pop();
    this.stack2.push(top);
    return top;
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
    return this.stack1.length === 0 && this.stack2.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()
 */

使用两个栈实现一个先入先出队列，其中一个栈 stack1 用于入队，另一个栈 stack2 用于出队。入队操作时，将元素压入 stack1；出队操作时，如果 stack2 不为空，则直接弹出栈顶元素；如果 stack2 为空，则依次将 stack1 的元素弹出并压入 stack2，再弹出 stack2 的栈顶元素。peek 操作时，先执行和 pop 操作类似的步骤，最后将栈顶元素压回 stack2 中。

复杂度

空间： O(2N) 时间：O(N)

[jmaStella]

思路 两个stack，一个是部分reverse queue的顺序，一个是正序 push：直接push到reverse_stack pop: 如果正序stack不为空，pop from 正序stack。otherwise，先把reverse stack所有element放进正序stack里，再pop from 正序stack。 peek：和pop思路一样 empty：两个stack都为空 代码

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

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

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

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

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

复杂度分析

时间复杂度：push()和empty()：O(1)，pop()，peek()：O(N)。 空间复杂度：O(N)，其中 N number of element push in stack。

[wangzh0114]

思路

• 构造正反两个方向的栈，在需要pop或peek队列时，访问反向栈的栈顶

  代码

  class MyQueue {
  private:
  stack<int> pos;
  stack<int> neg;
  
  void pos2neg(){
      while(!pos.empty()){
          neg.push(pos.top());
          pos.pop();
      }    
  }
  public:
  MyQueue() {
  }
  
  void push(int x) {
      pos.push(x);
  }
  
  int pop() {
      if(neg.empty()) pos2neg();
      int res = 0;
      res = neg.top();
      neg.pop();
      return res;
  }
  
  int peek() {
      if(neg.empty()) pos2neg();
      return neg.top();
  }
  
  bool empty() {
      return pos.empty() && neg.empty();
  }
  };

  ---

  复杂度分析

• TC:O(1)
• SC:O(N)

[aswrise]

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 len(self.stack2)==0:
        while self.stack1:
            self.stack2.append(self.stack1.pop())
    return self.stack2.pop()

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

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

[dorapocket]

class MyQueue {
public:
        stack<int> rev;
        stack<int> q;
        bool isRev=true;
    MyQueue() {

    }
    void _q2rev(){
        while(!q.empty()){
            rev.push(q.top());
            q.pop();
        }
        isRev=true;
    }
    void _rev2q(){
        while(!rev.empty()){
            q.push(rev.top());
            rev.pop();
        }
        isRev=false;
    }

    void push(int x) {
        if(!isRev) _q2rev();
        rev.push(x);
    }

    int pop() {
        if(isRev) _rev2q();
        int i=q.top();
        q.pop();
        return i; 
    }

    int peek() {
        if(isRev) _rev2q();
        return q.top(); 
    }

    bool empty() {
        return rev.empty()&&q.empty();
    }
};

[duke-github]

思路

双栈 head存栈 tail出栈 当tail为空的时候 将head依次出栈 tail入栈 
每个元素最多只会执行两次入栈 两次出栈的操作 

复杂度

时间复杂度 平均O(1) 空间复杂度O(n)

代码

 class MyQueue {
        Deque<Integer> head;
        Deque<Integer> tail;

        public MyQueue() {
            head = new LinkedList<>();
            tail = new LinkedList<>();
        }

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

        public int pop() {
            if (tail.isEmpty()) {
                switchStack();
            }
            return tail.pop();
        }

        public int peek() {
            if (tail.isEmpty()) {
                switchStack();
            }
            return tail.peek();
        }

        private void switchStack() {
            while (!head.isEmpty()) {
                tail.push(head.pop());
            }
        }

        public boolean empty() {
            return tail.isEmpty() && head.isEmpty();
        }
    }

[harperz24]

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

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

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

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

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

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

    # Two stacks, one for enqueueing and another for dequeueing
    # time: 
    # - push, empty: O(1)
    # - pop, peek  amortized O(1)

[Jetery]

class MyQueue {
public:
    stack<int> input;
    stack<int> output;
    MyQueue() {

    }

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

    int pop() {
        int ret = 0;
        if (output.size() > 0) {
            ret = output.top();
            output.pop();
        } else {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
            ret = output.top();
            output.pop();
        }
        return ret;
    }

    int peek() {
        int ret = 0;
        if (output.size() > 0) {
            ret = output.top();
        } else {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
            ret = output.top();
        }
        return ret;
    }

    bool empty() {
        return input.empty() && output.empty();
    }
};

[luckyoneday]

代码

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

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

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    const temStack = [];
    const len = this.stack.length;
    for (let i = 0; i < len; i++) {
        temStack.push(this.stack.pop());
    }
    const res = temStack.pop();
    const len2 = temStack.length;
    for (let j = 0; j < len2; j++) {
        this.stack.push(temStack.pop());
    }

    return res;
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    const temStack = [];
    const len = this.stack.length;
    for (let i = 0; i < len; i++) {
        temStack.push(this.stack.pop());
    }
    const res = temStack[len - 1];
    for (let j = 0; j < len; j++) {
        this.stack.push(temStack.pop());
    }

    return res;
};

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

[FireHaoSky]

class MyQueue:

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

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

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

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

def empty(self) -> bool:
    """
    Returns whether the queue is empty.
    """
    return self.s1 == [] and self.s2 == []

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()

[AstrKing]

思路

1、栈的特性是先进后出，队列的特性是先进先出，我们根据这些特性来做此道题目
2、知道两者特性之后，我们需要用两个栈来模拟队列的特性，一个栈为入队栈，一个栈为出对栈。当出队栈存在内容时，出队栈的栈顶，即为第一个出队的元素。若出队栈无元素，我们的需求又是出队的话，我们就需要将入队栈的内容反序导入出队栈，然后弹出栈顶即可。

代码

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

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

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

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

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

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

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

[RestlessBreeze]

code

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

[jiujingxukong]

解题思路

此题结合实际——使用两个栈来替代一个队列的实现是为了在多进程中分开对同一个队列对读写操作——来看确实经典，而且解法上官方题解更趋近于现实情况，即分为读栈和写栈。
下面这段话还怎么理解。

实际上现实中也有使用两个栈来实现队列的情况，那么为什么我们要用两个 stack 来实现 一个 queue？
其实使用两个栈来替代一个队列的实现是为了在多进程中分开对同一个队列对读写操作。一 个栈是用来读的，另一个是用来写的。当且仅当读栈满时或者写栈为空时，读写操作才会发 生冲突。
当只有一个线程对栈进行读写操作的时候，总有一个栈是空的。在多线程应用中，如果我们 只有一个队列，为了线程安全，我们在读或者写队列的时候都需要锁住整个队列。而在两个 栈的实现中，只要写入栈不为空，那么push操作的锁就不会影响到pop。

解题代码

1. 我自己的实现

   
   var MyQueue = function() {
   this.stack1=[]
   this.stack2=[]

};

/**

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

/**

• @return {number} */ MyQueue.prototype.pop = function() { const length=this.stack1.length if(length!==0){ for(let i=0;i<length;i++){ this.stack2.push(this.stack1.pop()) } const del=this.stack2.pop() for(let i=0;i<length-1;i++){ this.stack1.push(this.stack2.pop()) } return del }

  };

/**

• @return {number} */ MyQueue.prototype.peek = function() {

  const length=this.stack1.length
  if(length!==0){
  for(let i=0;i<length;i++){
      this.stack2.push(this.stack1.pop())
  }
  top=this.stack2.pop()
  this.stack1.push(top)
  for(let i=0;i<length-1;i++){
      this.stack1.push(this.stack2.pop())
  }

  return top }

};

/**

• @return {boolean} */ MyQueue.prototype.empty = function() { return this.stack1.length===0?true:false

};

2. 官方题解（更好更贴近现实情况）
```javascript
var MyQueue = function () {
  this.inStack = [];
  this.outStack = [];
};

MyQueue.prototype.push = function (x) {
  this.inStack.push(x);
};

MyQueue.prototype.pop = function () {
  if (!this.outStack.length) {
    this.in2out();
  }
  return this.outStack.pop();
};

MyQueue.prototype.peek = function () {
  if (!this.outStack.length) {
    this.in2out();
  }
  return this.outStack[this.outStack.length - 1];
};

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

MyQueue.prototype.in2out = function () {
  while (this.inStack.length) {
    this.outStack.push(this.inStack.pop());
  }
};

复杂度分析（只分析官方思路代码）

1. 时间复杂度 push和empty操作都是O（1） peek和pop操作都是O（N），其中 N 为 栈中元素个数。
2. 空间复杂度 空间复杂度：O(N)，其中 N 为 栈中元素个数，多使用了一个辅助栈，这 个辅助栈的大小和原栈的大小一样。

[franciszq]

思路

两个栈，一个做入栈，一个做出栈

出栈的数据来自于入栈，当出栈为空时，将入栈的数据全部塞进出栈。

代码

class MyQueue
{
public:
    MyQueue()
    {

    }

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

    int pop()
    {
        if (stk_in.empty() && stk_out.empty()) {
            return -1;
        }
        if (stk_out.empty()) {
            while (!stk_in.empty()) {

                stk_out.push(stk_in.top());
                stk_in.pop();
            }
        }
        int tmp = stk_out.top();
        stk_out.pop();
        return tmp;
    }

    int peek()
    {
        if (stk_out.empty()) {
            while (!stk_in.empty()) {
                int nub = stk_in.top();
                stk_in.pop();
                stk_out.push(nub);
            }
        }
        return stk_out.top();
    }

    bool empty()
    {
        if (stk_in.empty() && stk_out.empty()) {
            return true;
        }
        return false;
    }

private:
    std::stack<int> stk_in;
    std::stack<int> stk_out;
};

复杂度

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

[WL678]

思路：

栈的特点是"先进后出"，而队列的特点是"先进先出"；形象点，可以把栈看作只有一个开口的盒子，而队列则是双向开口的盒子，因此，直观的想法是用两个只有一个开口但是开口方向相反的盒子（栈）来模拟双向开口的盒子（队列）。

入栈和入列的操作基本上相同，区别主要在出栈操作上，队列是先进去的元素先出来，所以需要将stkIn已经入栈元素全部出栈，然后依次在另一个栈stkOut中入栈，此时，stkOut中元素的顺序已经反过来（原来在stkIn栈底的元素在stkOut栈顶），然后执行出栈，就完成了先进的元素先出。

代码：C++

class MyQueue {
public:
    stack<int> stkIn;
    stack<int> stkOut;
    MyQueue() {

    }

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

    int pop() {
        if(stkOut.empty()){
            while(!stkIn.empty()) {
            stkOut.push(stkIn.top());
            stkIn.pop();
            }
        }
        int temp = stkOut.top();
        stkOut.pop();
        return temp;

    }

    int peek() {
        if(stkOut.empty()){
                    while(!stkIn.empty()) {
                    stkOut.push(stkIn.top());
                    stkIn.pop();
                    }
                }
                int temp = stkOut.top();
                return temp;
        //int res = this->pop(); // 直接使用已有的pop函数
        //stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
        //return res;
    }

    bool empty() {
        if(stkOut.empty() && stkIn.empty())
            return true;
        else
            return false;
        //(stkOut.empty() && stkIn.empty()) ? return true : return false;
        //return stkOut.empty() && stkIn.empty();
    }
};

复杂度分析：

​ 时间复杂度：

​ push（）：O(1)

​ pop（）：O (4k) ,k为已经进入队列的元素数。

​ peek（）：O (4k) ,k为已经进入队列的元素数。

​ empty（）：O(1)

​ 空间复杂度：

​ 记队列的元素总数为k，O（2k）= O(k)

[joemonkeylee]

思路

in and out stack

代码

  public class MyQueue {
    private Stack inStack = new Stack();
    private Stack outStack = new Stack();
    public MyQueue()
    {

    }

    public void Push(int x)
    {
        this.inStack.Push(x);
    }

    public int Pop()
    {
        this.outStack.Clear();
        while (this.inStack.Count>0&&this.inStack.Peek()!=null)
        {
            this.outStack.Push(this.inStack.Pop());
        }

        int res = Convert.ToInt32(this.outStack.Pop());

        while (this.outStack.Count>0&&this.outStack.Peek()!=null)
        {
            this.inStack.Push(this.outStack.Pop());
        }

        return res;
    }

    public int Peek()
    {
        this.outStack.Clear();
        while (this.inStack.Count > 0 && this.inStack.Peek() != null)
        {
            this.outStack.Push(this.inStack.Pop());
        }

        int res = Convert.ToInt32(this.outStack.Peek());

        while (this.outStack.Count > 0 && this.outStack.Peek() != null)
        {
            this.inStack.Push(this.outStack.Pop());
        }

        return res;
    }

    public bool Empty()
    {
        return this.inStack.Count==0;
    }
}

复杂度分析

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

[liuajingliu]

解题思路

定义两个栈，

• 一个是pushStack, 执行push操作时，将元素入pushStack栈
• 另一个是popStack,执行pop操作时，在popStack取元素；当popStack栈为空时，依次将pushStack元素pop取出，push进pushStack栈

代码实现

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

复杂度分析

• 时间复杂度 $O(1)$
• 空间复杂度 $O(N)$, N为队列元素个数

[linlizzz]

思路

1. 初始化一个列表作为栈

2.push直接append；pop时另新建一个列表，倒序存放原列表元素，.pop()出后再重新倒序放入原列表；peek取第一个元素，empty查看列表是否为空

代码

class MyQueue:

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

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

    def pop(self) -> int:
        self.stack_inv = []
        for i in self.stack[::-1]:
            self.stack_inv.append(i)
        res = self.stack_inv.pop()
        self.stack = []
        for j in self.stack_inv[::-1]:
            self.stack.append(j)
        return res

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

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

复杂度分析

T(n)=O(n) n为栈的大小

S(n)=O(n)

[DrinkMorekaik]

class MyQueue {
    constructor() {
        this.stackPush = []
        this.stackPop = []
    }
    push(val) {
        this.stackPush.push(val)
    }
    pop() {
        if (this.stackPop.length) return this.stackPop.pop()
        while(this.stackPush.length) {
            this.stackPop.push(this.stackPush.pop())
        }
        return this.stackPop.pop()
    }
    peek() {
        return this.stackPop.length ? this.stackPop.at(-1) : this.stackPush.at(0)
    }
    empty() {
        return !this.stackPop.length && !this.stackPush.length
    }
}

[sye9286]

额 写完了发现好像不允许用数组，只能用栈，怪不得写起来这么简单。。。 我重新思考一下

思路

JS中没有stack，用数组代替。新建队列时，初始化头指针 head 和尾指针 tail 均为 0

1. push : 添加到尾指针处，然后尾指针 +1

2. pop : 返回头指针处的元素，然后头指针后移一位，元素仍在数组中不需要删除。 另外题目中说明所有操作保证有效，不会对空队列执行 pop，所以不用验证是否队列为空（head 不应该大于 tail）

3. peek : 返回头指针处的元素，但不移动头指针位置

4. empty : 头指针等于尾指针时，表示队列是空的。

代码

var MyQueue = function() {
    this.stack = new Array()
    this.head = 0;
    this.tail = 0;
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.stack[this.tail++] = x;
    // console.log("aft push tail = "+this.tail)
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    // no need to check if empty operation always valide
    return this.stack[this.head++];
}; 

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    return this.stack[this.head];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return (this.head === this.tail);
};

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

复杂度分析

• 时间复杂度：O(1)，不需要遍历数组
• 空间复杂度：O(1)，没有使用额外空间

[839781960]

//思路2个栈 模拟队列
public class _232用栈实现队列 {
        private Stack<Integer> inStack;
        private Stack<Integer> outStack;
        public _232用栈实现队列() {
                inStack = new Stack<>();
                outStack= new Stack<>();
        }

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

        public int pop() {
                if(outStack.isEmpty()){
                        while (!inStack.isEmpty()){
                                outStack.push(inStack.pop());
                        }
                }
                return  outStack.pop();
        }

        public int peek() {
                int rt = this.pop();
                outStack.push(rt);
                return rt;
        }

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

[texamc2]

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) in2out() {
    for len(q.inStack) > 0 {
        q.outStack = append(q.outStack, q.inStack[len(q.inStack)-1])
        q.inStack = q.inStack[:len(q.inStack)-1]
    }
}

func (q *MyQueue) Pop() int {
    if len(q.outStack) == 0 {
        q.in2out()
    }
    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 {
        q.in2out()
    }
    return q.outStack[len(q.outStack)-1]
}

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

[ccslience]

class MyQueue {
public:
    stack<int> s1,s2;
    MyQueue() {

    }

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

    int pop() {
       while(!s1.empty()){
       s2.push(s1.top());
       s1.pop();
       }
       return(s2.top());
       s2.pop();
    }

    int peek() {
        int p=s2.top();
        return p;
    }

    bool empty() {
        if(!s1.empty()||!s2.empty())
        return false;
        else return true;
    }
};

[Aneureka]

#include <stack>

class MyQueue {
public:
    MyQueue() {
    }

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

    int pop() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        int peek = out.top();
        out.pop();
        return peek;
    }

    int peek() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        return out.top();
    }

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

[RichardTaoK]

思路

这个题目上说的是用两个栈实现队列，但是在js中栈也是数组模拟的。所以当我们直接用一个数组也就能模拟出队列 push：就是入，放到数组最后 pop：返回就是数组第一个值，然后删除数组第一个值。 peek：就是数组第一个

代码

var MyQueue = function() {
    this.stack = []
    this.head = 0;
    this.tail = 0
};

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

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    return this.stack[this.head++]
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    return this.stack[this.head]
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.head === this.tail
};

复杂度分析

T(n)=O(1) S(n)=O(1)