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

Answer:

It refers to the second method of official problem solving (two queues, press -O (n)O(n), pop -o (1)O(1)).

The elements of the queue are arranged in the order in which they are removed from the stack, and can be removed from the stack in the order when they are removed from the stack.

  1. Use two columns, q1 to store the stack and Q2 to keep empty.
  2. Every time you push, you put q1 in q2, and then you move all q1 into Q2, and the order of q2 is reversed, and then you switch q1 and Q2.
  3. At the end of the push, Q1 stores all elements in the order of the stack, which is last in first out.
/** * Initialize your data structure here. */
var MyStack = function () {
  this.q1 = []; // Used to store stacks
  this.q2 = []; // It is used to store the elements on the stack and keep the stack order
};

/**
 * Push element x onto stack.
 * @param {number} x
 * @return {void}* /
MyStack.prototype.push = function (x) {
  // Each pushed element is stored in Q2 to ensure that it is the first element, i.e. the first pop
  this.q2.push(x);

  // Add elements from Q1 to Q2
  while (this.q1.length) {
    this.q2.push(this.q1.shift());
  }

  // Switch Q1 and Q2 to ensure the same column for each stack operation
  const temp = this.q1;
  this.q1 = this.q2;
  this.q2 = temp;
};

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

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

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