用队列实现栈 (opens new window)

• 难度：Easy
• 标签：栈、队列

刷题思路

• [x] 数组模拟栈(hack)
• [x] 双队列模拟栈

方法 1 数组模拟队列

/**
 * Initialize your data structure here.
 */
var MyStack = function() {
    this.arr = []
};

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.arr.push(x)
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
    const val = this.top()
    this.arr.length -= 1
    return val
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {
    return this.arr[this.arr.length-1]
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return this.arr.length === 0
};

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

方法 2 双队列模拟栈

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

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.mQueue.push(x)
    while (this.queue.length > 0) this.mQueue.push(this.queue.shift())
    while (this.mQueue.length > 0) this.queue.push(this.mQueue.shift())
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
    return this.queue.shift()
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {
    const ele = this.queue.shift()
    this.push(ele)
    return ele
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return this.top() === undefined
};

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~