代码随想录刷题记录 Day10

To Do List

• DAY 9 回顾
• 栈与队列的浅显理解
• LeetCode 232. 用栈实现队列
• LeetCode 225. 用队列实现栈
• DAY 10 总结

DAY 9 回顾

（）

栈与队列的浅显理解

栈与队列也是两个基本的数据结构。

在以往的数据结构的教材中提到，栈是单侧进出，队列是双侧单向进出

由于栈的数据结构的特性，栈的所有元素都必须遵循先进后出原则，故栈结构只提供尾插和尾删 (pop 和 push)，不提供遍历功能。也正因为这种特性，栈实际上并不是一个容器，而是容器适配器。

队列的数据结构也是如此，队列的所有元素都必须遵循先进先出、后进后出原则，故队列结构只提供头插和尾删 (unshift 和 pop)，不提供遍历功能。

LeetCode 232. 用栈实现队列 / Implement Queue Using Stacks

Difficulty: Easy

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

Translated by zh-CN

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All the calls to pop and peek are valid.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Translated by zh-CN

最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

---

解法：

(JavaScript)

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

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

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

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    let result = this.pop()
    this.stOut.push(result)
    return result
};

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

PS: 带补充

---

LeetCode 225. 用队列实现栈 / Implement Stack using Queues

Difficulty: Easy

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Translated by zh-CN

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list（列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

Follow-up: Can you implement the stack using only one queue?

Translated by zh-CN

最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空
你能否仅用一个队列来实现栈。

---

解法：

(JavaScript)

var MyStack = function() {
    this.q = []
};

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

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    let len = this.q.length
    while(len-- > 1){
        this.q.push(this.q.shift())
    }
    return this.q.shift()
};

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
    const x = this.q.pop()
    this.q.push(x)
    return x
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return !this.q.length
};

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

PS: 带补充

---

DAY 10 总结