Interview question 03.04. Make stacks into teams

  1. Two stacks (S1 and S2) are used to simulate the queue. When entering the queue, S2 is used to save, and when exiting the queue, S2 stacks are successively exited from the stack.
  2. The outgoing elements are pushed to S1 in turn, and then S1 is the first element that should be queued in the correct queue mode.
  3. The principle is that s1 can be used to reverse the order of s2 stack queued elements, so that the operation of the queue can be correctly simulated externally, first-in, first-out.
var MyQueue = function() {
  this.s1 = []; // Exit the queue storage area
  this.s2 = []; // Enter the queue storage area
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}* /
MyQueue.prototype.push = function(x) {
  this.s2.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}* /
MyQueue.prototype.pop = function() {
  this.transfer(); // Transfer stack elements
  const ret = this.s1.pop(); / / out of the team
  return ret;
};

/**
 * Get the front element.
 * @return {number}* /
MyQueue.prototype.peek = function() {
  this.transfer();
  return this.s1[this.s1.length - 1];
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}* /
MyQueue.prototype.empty = function() {
  return this.s1.length === 0 && this.s2.length === 0;
};

MyQueue.prototype.transfer = function() { // Add elements from S2 to S1
  if (this.s1.length > 0) return; // If s1 contains elements, you can queue them in sequence
  while (this.s2.length > 0) {this.s1.push(this.s2.pop()); }};/** * 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() * /
Copy the code