13.Implement-a-Queue-by-using-Stack.md

13. Implement a Queue by using Stack

Problem

https://bigfrontend.dev/problem/implement-a-queue-by-using-stack

Problem Description

In JavaScript, we could use array to work as both a Stack or a queue.

const arr = [1, 2, 3, 4];

arr.push(5); // now array is [1, 2, 3, 4, 5]
arr.pop(); // 5, now the array is [1, 2, 3, 4]

Above code is a Stack, while below is a Queue

const arr = [1, 2, 3, 4];

arr.push(5); // now the array is [1, 2, 3, 4, 5]
arr.shift(); // 1, now the array is [2, 3, 4, 5]

now suppose you have a stack, which has only follow interface:

class Stack {
  push(element) {
    /* add element to stack */
  }
  peek() {
    /* get the top element */
  }
  pop() {
    /* remove the top element */
  }
  size() {
    /* count of elements */
  }
}

Could you implement a Queue by using only above Stack? A Queue must have following interface

class Queue {
  enqueue(element) {
    /* add element to queue, similar to Array.prototype.push */
  }
  peek() {
    /* get the head element */
  }
  dequeue() {
    /* remove the head element, similar to Array.prototype.pop */
  }
  size() {
    /* count of elements */
  }
}

notes

you can only use Stack as provided, Array should be avoided for the purpose of practicing.

Solution 1 (O(1) enqueue, O(n) dequeue and peek)

/* you can use this Class which is bundled together with your code

class Stack {
  push(element) { // add element to stack }
  peek() { // get the top element }
  pop() { // remove the top element}
  size() { // count of element }
}
*/

/* Array is disabled in your code */

// you need to complete the following Class
class Queue {
  constructor() {
    this.content = new Stack();
  }

  enqueue(element) {
    this.content.push(element);
  }
  peek() {
    const reversedQueue = this._reverse(this.content);
    return reversedQueue.peek();
  }
  size() {
    return this.content.size();
  }
  dequeue() {
    const reversedQueue = this._reverse(this.content);
    const poppedItem = reversedQueue.pop();
    this.content = this._reverse(reversedQueue);
    return poppedItem;
  }
  _reverse(queue) {
    const reversedQueue = new Stack();
    while (queue.size() > 0) {
      const lastItem = queue.pop();
      reversedQueue.push(lastItem);
    }

    return reversedQueue;
  }
}

Solution 2 (O(n) enqueue, O(1) dequeue and peek)

/* you can use this Class which is bundled together with your code

class Stack {
  push(element) { // add element to stack }
  peek() { // get the top element }
  pop() { // remove the top element}
  size() { // count of element }
}
*/

/* Array is disabled in your code */

// you need to complete the following Class
class Queue {
  constructor() {
    this.content = new Stack();
    this.reversedContent = new Stack();
  }

  enqueue(element) {
    while (this.content.size() > 0) {
      const poppedItem = this.content.pop();
      this.reversedContent.push(poppedItem);
    }

    this.reversedContent.push(element);

    while (this.reversedContent.size() > 0) {
      const poppedItem = this.reversedContent.pop();
      this.content.push(poppedItem);
    }
  }
  peek() {
    return this.content.peek();
  }
  size() {
    return this.content.size();
  }
  dequeue() {
    return this.content.pop();
  }
}