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

[zhiyuanpeng]

class MyQueue:

    def __init__(self):
        self.forward = []
        self.backward = []

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

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

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

    def empty(self) -> bool:
        if len(self.forward) or len(self.backward):
            return False
        else:
            return True

space O(N) time O(1)

[coderXiaowq]

Java 时间复杂度O(1) 因为是返回队列头部元素,因此需要将整个队列反转后放在另一个队列中 定义两个队列保存数据

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

    public MyQueue() {
        in = new LinkedList();
        out = new LinkedList();
    }

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

    public int pop() {
        if (out.isEmpty()) {//将in中的数据给到out
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
        return out.pop();
    }

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

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

}

[xil324]

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 removeElement = this.stack.shift();
    return removeElement;
};

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

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

[Martina001]

// 思路：栈 先进后出，队列 先进先出 用两个队列可以实现栈 一个队列在offer的时候poll队列中其他元素再offer，即可实现栈 // 同理两个栈倒来倒去也可以实现队列 但是这样相当于在pop和peek的时候都要倒一遍 // 感觉可以想办法在push中实现

class MyQueue {

        LinkedList<Integer> stack;

        LinkedList<Integer> helpStack;
        public MyQueue() {
            stack = new LinkedList<>();
            helpStack = new LinkedList<>();
        }
        public void push(int x) {
            stack.push(x);
        }

        public int pop() {
            if(helpStack.isEmpty()){
                while(!stack.isEmpty()){
                    helpStack.push(stack.pop());
                }
            }
           return helpStack.pop();
        }

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

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

[hillsonziqiu]

思路

因为只能使用栈的操作，那么如果想用栈实现队列的话就需要两个栈相互倒蹬。

题解

var MyQueue = function () {
    this.inStack = [];
    this.outStack = [];

};

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

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

    return this.outStack.pop();
};

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

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

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

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

复杂度分析

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

[atom-set]

思路

• 先用数组实现 Stack，支持的 API 有 push、pop、empty、size，其中 push、pop 时间复杂度是 O(1)，empty、size 时间复杂度是 O(N)
• 队列的 push 操作调用栈的 push 操作即可
• 队列的 peek 和 pop 操作是栈底元素，可以利用中间栈，将元素出栈放到中间栈，操作完后再把中间栈元素移到栈即可
• 队列的 empty 操作调用栈的 empty 操作即可
• 队列的 size 操作调用栈的 size 操作即可

代码

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

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

/**
 * @return {number}
 */
Stack.prototype.pop = function () {
  if (this.stack.length > 0) {
    return this.stack.pop();
  }
  return -1;
};

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

/**
 * @return {number}
 */
Stack.prototype.size = function () {
  return this.stack.length;
};

var MyQueue = function () {
  this.stack = new Stack();
  this.queue = new Stack();
};

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

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
  if (this.queue.size() === 0) {
    return null;
  }

  while (this.queue.size() > 1) {
    this.stack.push(this.queue.pop());
  }

  var head = this.queue.pop();

  while (this.stack.size() > 0) {
    this.queue.push(this.stack.pop());
  }
  return head;
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
  if (this.queue.size() === 0) {
    return null;
  }

  while (this.queue.size() > 1) {
    this.stack.push(this.queue.pop());
  }

  var head = this.queue.pop();

  this.queue.push(head);

  while (this.stack.size() > 0) {
    this.queue.push(this.stack.pop());
  }

  return head;
};

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

复杂度分析

• 时间复杂度
  • push: O(1)
  • pop: O(N)，要把栈里元素都先遍历存起来
  • peek: O(N)，要把栈里元素都先遍历存起来
  • empty: O(N)，依赖于栈的 empty 时间复杂度
  • size: O(N)，依赖于栈的 size 时间复杂度
• 空间复杂度：O(N)

[lxy1108]

实现思路

通过两个栈来实现，一个栈用来读取，另一个栈用来做缓存。在push的时候将现有的内容先转移到缓存栈里，将新元素放到读取栈最底端后，再把缓存栈里的数据放回来。

python 3代码

class MyQueue:

def __init__(self):
    self.queue = collections.deque([])
    self.cache = collections.deque([])

def push(self, x: int) -> None:
    while self.queue:
        n = self.queue.pop()
        self.cache.append(n)
    self.queue.append(x)
    while self.cache:
        n = self.cache.pop()
        self.queue.append(n)

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

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

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

复杂度分析

空间复杂度为O(N)，时间复杂度push为O(N)，其他操作为O(1)

[franklinsworld666]

思路

用双端队列来实现栈。 用栈A 来保存队列push 进来的元素，用栈B来支持pop和peek操作。如果栈B为空，那么把栈A全部出栈并插入栈B，此时栈B中的元素出栈顺序刚好与队列一致，可以用来进行队列pop和peek操作；如果栈B不为空，则直接对栈B进行 pop和peek操作；

代码

class MyQueue:

    def __init__(self):
        self.stack1 = MyStack()
        self.stack2 = MyStack()

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

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

    def peek(self) -> int:
        if not self.stack1.empty():
            return self.stack1.peek()
        else:
            while not self.stack2.empty():
                self.stack1.push(self.stack2.pop())
            return self.stack1.peek()

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

class MyStack:
    def __init__(self):
        self.stack = deque()

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

    def pop(self) -> int:
        if not self.empty():
            return self.stack.pop()
        else:
            return None

    def peek(self) -> bool:
        if not self.empty():
            return self.stack[-1]
        else:
            return None

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

复杂度分析

• 时间复杂度

  • push: O(1)， 同双端队列的push操作
  • empty: O(1)
  • pop/peek: 最好O(1), 最坏O(N), 平均来讲O(1); 假设在栈A中存在X个元素时，进行pop/peek操作，那么要进行X次出栈入栈操作，也意味着接下来的 X-1 次pop/peek 操作只要常数时间，所以平均来讲时间复杂度是O(1)

• 空间复杂度: O(N)

[wwz223]

代码

class Stack {
  constructor() {
    this.stack = [];
  }
  push(x) {
    this.stack.push(x);
  }
  pop() {
    return this.stack.pop();
  }
  size() {
    return this.stack.length;
  }

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

class MyQueue {
  constructor() {
    this.stack = new Stack();
    this.queue = new Stack();
  }

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

  pop() {
    if (this.queue.size() === 0) return null;
    while (this.queue.size() > 1) {
      this.stack.push(this.queue.pop());
    }
    const head = this.queue.pop();
    while (this.stack.size() > 0) {
      this.queue.push(this.stack.pop());
    }
    return head;
  }
  peek() {
    if (this.queue.size() === 0) return null;
    while (this.queue.size() > 1) {
      this.stack.push(this.queue.pop());
    }
    const head = this.queue.pop();
    this.queue.push(head)
    while (this.stack.size() > 0) {
      this.queue.push(this.stack.pop());
    }
    return head;
  }
  empty() {
    return this.queue.size() === 0;
  }
}```

时间复杂度
push：O(1)
pop：O(2N) 两次循环
peek: O(2N) 两次循环

空间复杂度  O（1）

[GReyQT]

题解思路：

（1）创建一个存储数据的栈，和一个过渡处理的栈 代码：

class MyQueue {
private:
    stack<int> store,deal;
public:
    MyQueue() {
        while (!store.empty())
        {
            store.pop();
        }
        while (!deal.empty()) 
        {
            deal.pop();
        }
    }

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

    int pop() {
        int res = 0;
        while(!store.empty())
        {
            deal.push(store.top());
            store.pop();
        }
        res = deal.top();
        deal.pop();
        while(!deal.empty())
        {
            store.push(deal.top());
            deal.pop();
        }
        return res;
    }

    int peek() {
        int res = 0;
        while(!store.empty())
        {
            deal.push(store.top());
            store.pop();
        }
        res = deal.top();
        while(!deal.empty())
        {
            store.push(deal.top());
            deal.pop();
        }
        return res;
    }

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

复杂度分析：

• 时间复杂度：取决队列中的元素个数，因此时间复杂度为O(n)
• 空间复杂度：使用了两个栈来实现，复杂度取决队列中的元素个数，因此空间复杂度为O(n)

[CathyShang]

思路：

• 栈与队列的区别：栈Last in, First out, LIFO; 队列 First in, First out, FIFO；
• 发展仅元素输出顺序不同，一头一尾，那么用2个栈进行维护，在输出时，让先入栈的为栈的top()，就像把瓶子倒过来一样。
• 当然，在输入的时候，需要查看stk2是否还有元素，若有得让它回到stk1，保持输入的顺序不发生改变。

代码

class MyQueue {
public:
    // 通过
    stack<int> stk1;
    stack<int> stk2;

    MyQueue() {}

    void push(int x) {
        if(!stk2.empty()){
            // stk2中元素移到stk1
            while(!stk2.empty()){
                stk1.push(stk2.top());
                stk2.pop();            
            }
        }
        stk1.push(x);
    }

    int pop() {
        if(!stk1.empty()){
            while(!stk1.empty()){
                stk2.push(stk1.top());
                stk1.pop();
            }
        }
        int res = stk2.top();
        stk2.pop();
        return res;
    }

    int peek() {
        if(!stk1.empty()){
            while(!stk1.empty()){
                stk2.push(stk1.top());
                stk1.pop();
            }
        }
        int res = stk2.top();
        return res;
    }

    bool empty() {
        if(stk1.empty()&&stk2.empty()){
            return true;
        }
        else{return false;}
    }
};

复杂度

• 时间复杂度 push(), pop(), peek() $O(N)$; empty() $O(1)$;
• 空间复杂度 $O(N)$ 调用2个栈，栈内存放长度为N的元素。

[Dtjk]

class MyQueue {
private:
    std::stack<int> q1,q2;
public:
    MyQueue() {}

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

    int pop() {
       if(!q2.empty()){
           int t = q2.top();
           q2.pop();
           return t;
       } 
       else {
           while(!q1.empty()){
               int x = q1.top();
               q1.pop();
               q2.push(x);
           }
           int t = q2.top();
           q2.pop();
           return t;
       }
    }

    int peek() {
        if(!q2.empty()) return q2.top();
        else {
           while(!q1.empty()){
               int x = q1.top();
               q1.pop();
               q2.push(x);
           }
           return q2.top();
       }
    }

    bool empty() {
        if(q1.size() || q2.size()) return false;
        return true;
    }
}

[rao-qianlin]

class MyQueue {
    private Stack<Integer> s1, s2;

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

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

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

[jinzhepro]

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());
        }
    }
    return this.stack2[this.stack2.length - 1];
};

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

时间复杂度 push, pop, peek, O(N); empty O(1) 空间复杂度 O(N)

[Alexzhang-Mini]

class MyQueue: def init(self): self.input_stack = [] # 用于入队操作 self.output_stack = [] # 用于出队操作

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

def pop(self) -> int: self._transfer_if_needed() return self.output_stack.pop()

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

def empty(self) -> bool: return not self.input_stack and not self.output_stack

def _transfer_if_needed(self): if not self.output_stack: while self.input_stack: self.output_stack.append(self.input_stack.pop())

[YANGLimbo]

思路：用两个相反的栈，时间复杂度O(n)

class MyQueue {

protected:
    std::stack<int> stack;
    std::stack<int> revStack;

public:
    MyQueue() {
    }

    void push(int x) {
        stack.push(x); // stack的栈顶即队列末尾
    }

    int pop() {
        while(!stack.empty()){
            revStack.push(stack.top());
            stack.pop();
        }// 弹出stack中的元素，进入revstack

        int ans = revStack.top(); // revstack的栈顶即队列开头
        revStack.pop(); 

        while(!revStack.empty()){
            stack.push(revStack.top());
            revStack.pop();
        }// 重新进入stack
        return ans;
    }

    int peek() {
        while(!stack.empty()){
            revStack.push(stack.top());
            stack.pop();
        }// 弹出stack中的元素，进入revstack

        int ans = revStack.top(); // revstack的栈顶即队列开头

        while(!revStack.empty()){
            stack.push(revStack.top());
            revStack.pop();
        }// 重新进入stack
        return ans;
    }

    bool empty() {
        return stack.empty();
    }
};

[pandapls]

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

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 操作）。

思路

使用辅助栈

代码

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

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

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    if (this.viceStack.length === 0) {
        while(this.mainStack.length) {
            this.viceStack.push(this.mainStack.pop())
        }
    }

    return this.viceStack.pop()
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if (this.viceStack.length === 0) {
        while(this.mainStack.length) {
            this.viceStack.push(this.mainStack.pop())
        }
    }

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

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

复杂度分析

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