Topic describes

232. Implementing queues with stacks (Easy)

You can implement a first-in, first-out queue using only two stacks. Queues should support all operations supported by normal queues (push, POP, peek, empty) :

Implement MyQueue class:

  • Void push(int x) pushes element X to the end of the queue
  • Int pop() removes and returns the element from the beginning of the queue
  • Int peek() returns the element at the beginning of the queue
  • Boolean empty() Returns true if the queue is empty; Otherwise, return false

Description:

  • You can only use standard stack operations — that is, only push to Top, peek/ Pop from Top, size, and is empty are legal.
  • Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it’s standard stack operations.

Advanced:

  • Can you implement queues with O(1) amortized time per operation? In other words, the total time complexity of performing n operations is O(n), even though one of them may take a long time.

Example:

Input:"MyQueue"."push"."push"."peek"."pop"."empty"[[]], [1], [2[], [], [], [] output: [null.null.null.1.1.false] 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
Copy the code

Tip:

  • 1 <= x <= 9
  • Push, POP, peek, and Empty are called up to 100 times
  • Assume that all operations are valid (for example, an empty queue does not call pop or PEEK)

JavaScript template:

/** * Initialize your data structure here. */
var MyQueue = function() {};/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}* /
MyQueue.prototype.push = function(x) {};/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}* /
MyQueue.prototype.pop = function() {};/**
 * Get the front element.
 * @return {number}* /
MyQueue.prototype.peek = function() {};/**
 * Returns whether the queue is empty.
 * @return {boolean}* /
MyQueue.prototype.empty = function() {};/** * 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

Thought analysis

Ho-ho, today’s question of the day I can play again! I tried JavaScript push and Shift, and it was pretty quick, three lines of code, faster than 99+, but not very martial. So let’s get started.

They want to use two stacks to simulate a queue queue. My idea is to use one stackIn stack to receive data pushed in and another stackOut stack to shift (pop) data out of the queue.

Pushing into the queue is simple, using the array’s own push method, and the bulk of the code is focused on the Shift part.

Shift determines if stackOut is empty, and if it is empty, the values of the stackIn sections are passed into stackOut one by one, and the order of stackOut is reversed. In this case, stackOut is like a queue in reverse, and we only need to pop the last value.

  1. Initialize two stacks:
var MyQueue = function() {
  this.stackIn = [];
  this.stackOut = [];
};
Copy the code
  1. Push method:
MyQueue.prototype.push = function (x) {
  this.stackIn.push(x);
};
Copy the code
  1. The shift method:
MyQueue.prototype.pop = function () {
  if (!this.stackOut.length) {
    while (this.stackIn.length) {
      this.stackOut.push(this.stackIn.pop()); }}return this.stackOut.pop();
};
Copy the code
  1. Peek method:
MyQueue.prototype.peek = function () {
  if (!this.stackOut.length) {
    while (this.stackIn.length) {
      this.stackOut.push(this.stackIn.pop()); }}return this.stackOut[this.stackOut.length - 1];
};
Copy the code

The time complexity is O(1), although at first glance there is a while loop, but in reality each element only comes in and out of the stack twice at most;

The space complexity is O(n) and two stacks are maintained

To optimize the

We can actually see that the peek and POP sections share a lot of the same code to convert stackIn elements into stackOut. So we can extract this part and reduce the amount of duplicate code:

MyQueue.prototype.move = function() {
  if (!this.stackOut.length) {
    while (this.stackIn.length) {
      this.stackOut.push(this.stackIn.pop()); }}}Copy the code

This makes the code in Peek and POP much simpler:

MyQueue.prototype.pop = function () {
  this.move();
  return this.stackOut.pop();
};

MyQueue.prototype.peek = function () {
  this.move();
  return this.stackOut[this.stackOut.length - 1];
};
Copy the code

The complete code

/** * Initialize your data structure here. */
var MyQueue = function () {
  this.stackIn = [];
  this.stackOut = [];
};

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

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}* /
MyQueue.prototype.pop = function () {
  this.move();
  return this.stackOut.pop();
};

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

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

MyQueue.prototype.move = function () {
  if (!this.stackOut.length) {
    while (this.stackIn.length) {
      this.stackOut.push(this.stackIn.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

To summarize

2) ω •́)✧ can relax a little in today’s LeetCode of the day

Let’s use JavaScript to brush algorithms: LeetCode-JavaScript

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign