BFE.dev challenge #108. Implement a Stack by using Queue

#javascript

https://bfe.dev is like a LeetCode for FrontEnd developers. I’m using it to practice my skills.

This article is about the coding problem BFE.dev#108. Implement a Stack by using Queue

Look at the interface

/* you can use this Queue which is bundled together with your code
class Queue {
  enqueue(element) {
    // add new element to the queue
  }
  peek() { 
    // return the head element
  }
  dequeue() { 
    // remove head element from the queue
  }
  size() { 
    // return the queue size
  }
}
*/


// you need to complete the following Stack, using only Queue
class Stack {
  push(element) {
    // push an element into the stack
  }
  peek() { 
    // get the top element 
  }
  pop() { 
    // remove top element from stack
  }
  size() { 
    // return count of elements
  }
}

Let's say we have a queue

[1,2,3,4]

now we need to pop 4 , but since it is a queue, we could only dequeue 1 out, so in order to get 4, we need to dequeue all other 3 elements, and put them in another queue (because we are not permitted to use Array).

[4], [1,2,3]

now we could get 4 out

[ ] , [1,2,3]

We could enqueue the elements back, and repeat above process. But actually we cannot implement peek() with this, we cannot afford dequeueing all elements just for peek().

To solve this problem, we should always keep a queue of only one elements, so we could peek() and pop(), like below:

[ ], [ ]

when adding 1, just enqueue it

[1], [ ]

when adding 2, enqueue it, and then dequeue 1 to another queue.

[1,2], [ ]
[2], [1]

when adding 3, 4 just do the same

[2,3], [1]
[3], [1,2]
[3,4], [1,2]
[4], [1,2,3]

now we can just dequeue 4

[ ], [1,2,3]

since one queue is empty, let's try to set the other queue to 1 elements

[1,2], [3]

we now could just switch these 2 queues, we could see that this is the case we processed before.

[3], [1, 2]

Cool, so we just need to have 2 queues

queue1 which always have 1 element(or empty)
queueRest which is to hold other elements.

Let's write some code

The code is just an exact reflection of above process, so no more detailed explanation here.

class Stack {
  constructor() {
    this.queue1 = new Queue()
    this.queueRest = new Queue()
  }

  push(element) {
    this.queue1.enqueue(element)
    this._move()
  }

  _move() {
    while (this.queue1.size() > 1) {
      this.queueRest.enqueue(this.queue1.dequeue())
    }
  }

  peek() { 
    return this.queue1.peek()
  }
  pop() {
    if (this.queue1.size() === 0) {
      return undefined
    }

    const element = this.queue1.dequeue()

    // swap if the other queue is not empty
    if (this.queueRest.size() > 0) {
      ;[this.queue1, this.queueRest] = [this.queueRest, this.queue1]
      this._move()
    }

    return element
  }
  size() { 
    return this.queue1.size() + this.queueRest.size()
  }
}