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

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#13. Implement a Queue by using Stack

Look at the interface

/* 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 {
  enqueue(element) { 
    // add new element to the rare
  }
  peek() { 
    // get the head element
  }
  size() { 
    // return count of element
  }
  dequeue() {
    // remove the head element
  }
}

To dequeue an element from a Stack, we need obviously pop all the element except the last one, while we are popping, where do we keep the popped elements?

We cannot use Array, so we need to push them into a new Stack, like below.

// initially
[1,2,3,4],  [ ]

// to get 1, we need to pop the rest elements
[1], [4,3,2]

// now we can get 1
[ ], [4,3,2]

After dequeueing 1, we could push the elements back into the first stack. But it reminds us that the whole process would be triggered again if 2 is to be popped.

Rather than pushing them back, why not we just keep them there, so we have 2 stacks for different purpose, one for push, one for pop.

pushStack [ ], popStack [4,3,2]

// dequeue 2 could be achieved by popping from pop stack 
pushStack [ ], popStack [4,3]

// to enqueue a new element, just push to pushStack
pushStack [5], popStack [4,3]

When popStack is empty and pushStack is not, then it is time to push all elements from pushStack into popStack.

This is the solution, let's write some code

Start coding

It is pretty straightforward from above analysis. Be aware of the internal _transfer method.

class Queue {
  constructor() {
    this.pushStack = new Stack()
    this.popStack = new Stack()
  }
  _transfer() {
    while(this.pushStack.size() > 0) {
      this.popStack.push(this.pushStack.pop())
    }
  }
  enqueue(element) { 
    this.pushStack.push(element)
  }
  peek() { 
    if (this.size() === 0) return undefined

    if (this.popStack.size() === 0) {
      this._transfer()
    }

    return this.popStack.peek()
  }
  size() { 
    return this.pushStack.size() + this.popStack.size()
  }
  dequeue() {
      if (this.size() === 0) return undefined

    if (this.popStack.size() === 0) {
      this._transfer()
    }

    return this.popStack.pop()
  }
}

Passed!

This is an interesting problem. Maybe you can also have a try at https://bfe.dev

Hope it helps, see you next time.