Original link: leetcode-cn.com/problems/im…

Answer:

Refer to the official solution method one (two queues, press -O(1)O(1), pop -o (n)O(n)).

When I push, I put the element directly into queue Q1, and when I unload, I put the non-tail element of Q1 into queue Q2, and the remaining element of Q1 is the top of the stack.

  1. Use two columns, q1 to store the stack and Q2 to keep empty.
  2. At this time, the element at the top of the stack is at the end of Q1 and cannot be viewed. A variable should be used to cache the value at the top of the stack for the top method to obtain.
  3. The non-tail element of Q1 is stored in queue Q2 when it is removed from the stack. The remaining element in Q1 is the top of the stack.
/** * Initialize your data structure here. */
var MyStack = function () {
  this.q1 = []; / / save the stack
  this.q2 = []; // Cache queue elements other than the top of the stack when pop is used
  this.tail = null; // Save the top element of the stack
};

/**
 * Push element x onto stack.
 * @param {number} x
 * @return {void}* /
MyStack.prototype.push = function (x) {
  this.q1.push(x); // The elements are queued directly when pushed
  this.tail = x; // Since the queued element cannot be viewed as the top of the stack, we need to store the top of the stack element in a variable
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}* /
MyStack.prototype.pop = function() {
  // If the queue length <=1, the top of the stack is empty
  if (this.q1.length <= 1) {
    this.tail = null;
  }

  // Move all queue elements except the end to Q2. The remaining element in Q1 is the top element of the stack
  while (this.q1.length > 1) {
    this.tail = this.q1.shift();
    this.q2.push(this.tail);
  }

  // There is only one element left in the queue, which is the top of the stack
  const top = this.q1.shift();

  // Switch Q1 and Q2 to ensure that the queue for each operation is Q1.
  const temp = this.q1;
  this.q1 = this.q2;
  this.q2 = temp;

  // Return the stack element
  return top;
};

/**
 * Get the top element.
 * @return {number}* /
MyStack.prototype.top = function () {
  return this.tail;
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}* /
MyStack.prototype.empty = function () {
  return !this.q1.length;
};
Copy the code