BFE.dev challenge #108. Implement a Stack by using Queue
Tags: javascript
Published: 2020-09-12 15:20:00

> 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](https://bigfrontend.dev/problem/Implement-a-Stack-by-using-Queue)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/x7u392n1cj7xz4pyevzf.png)

## Look at the interface

```js
/* 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

```js
[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).

```js
[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:

```js
[ ], [ ] 
```

when adding 1, just enqueue it

```js
[1], [ ]
```

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

```js
[1,2], [ ]
[2], [1]
```

when adding 3, 4 just do the same

```js
[2,3], [1]
[3], [1,2]
[3,4], [1,2]
[4], [1,2,3]
```

now we can just dequeue 4

```js
[ ], [1,2,3]
```

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

```js
[1,2], [3]
```

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

```js
[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.

```js
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()
  }
}
```

## Passed! Yeah~

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/9rxk1rh1x3naiu9lh8pg.gif)

If you are interested, have a try at BFE.dev https://bigfrontend.dev/problem/Implement-a-Stack-by-using-Queue

Hope it helps, see you next time!