Create a Queue Using One Stack

Recently, Google revealed that they have asked applicants to construct a queue using only a single stack.
This might seem impossible, but it’s doable, using some trickery. Feel free to try it yourself.

Hints
This won’t have nice time complexities.
Think about how you might be able to store information without using an array or an object.

class Queue {   
  constructor() {   
  this._storage = [];
    // Your code    here

  enqueue(Item)  (  
      // Your  code here
  } 

  dequeue() (   
    // Your code    here
  } 

  get  size()  (    
    // Your  code   here
  } 
}

Solution

class Queue {
  constructor() {
    this._storage = [];
  }

  enqueue(...items) {
    this._storage.push(...items);
  }

  dequeue() {
    if(this._storage.length > 1) {
      const lastltem = this._storage.pop();
      const firstItem = this.dequeue();
      this.enqueue(lastltem);
      return firstItem;
    } else if(this._storage.length === 1) {
      return this._storage.pop();
    } else {
      console.warn('Attempt1ng to dequeue from an  empty  queue');
    }
  }
}

Note that in the constructor, we create only a single array. This Will be our stack.
The enqueue() function passes the items it receives into storage.

How dequeue() Works

This recursive method is the fun part. We’ll start by discussing the base cases. Lines 16 onward state that if the queue is empty, print a warning and do nothing. If there’s a single item, pop it off and return it.

For the cases where there is more than one item present in storage, we can look at lines 11 - 15.

Assume that our storage stack has values 1, 2, 3, in that order, present inside.

In the First Call

Once we hit line 12, lastItem is equal to 3 and our queue has had 3
removed:
[1, 2]

Since we know more items are present (since this is the case in which there were multiple items in storage), we recursively call the dequeue() method.

Entering the Second Call

We enter the function again. Length is now 2, so we enter the same case, lines 11 - 15. Again, we dequeue. In this Call, lastItem is equal to 2 . Our queue loses another value:
[1]

We again call the function.

Entering the Third Call

This time, there is only one item, 1 . We pop it off and return it, ending up back in the second call. Our queue is empty.
[]

Back to the Second Call

We go back to the 2nd call, now on line 14. lastItem is 2 and firstItem is 1.

On line 14, we enqueue lastItem, or 2.
[2]

We return 1 and go back to the first call.

Back to the First Call

We’re back at the beginning. 1astItem is 3 and firstItem İs 1. We enqueue 3:
[2, 3]

and return 1.

Dequeue Time

The time complexity of dequeue() is:

O(n)

because we need to pop and re-insert every item except one.

Dequeue Space

The space complexity of dequeue() is:

0(n)

because we need to call the func

tion one more time for every item.