Learn how to create a queue when the only data structure you have access to is a stack.
Instructions
Write a function that creates a queue using two stacks. Besides these twD stacks, you may not use any additional data structures in your implementation. It should have the methods enqueue , dequeue , and s ize .
Feel free to change the code provided below when you start. It’s meant to be a guide.
Solution
1 class Queue {
2 constructor() {
3 this._enqueueStorage[];
4 this._dequeueStorage[];
5 }
6
7 enqueue(1tem) (
8 this. enqueuestorage.push(item); 9 }
10
11 dequeue( ) (
12 if(this. dequeueStorage.length) (
13 return this. dequeueStorage.pop();
14 }
15
16 1f(th1s ._enqueue5torage . 1ength) (
17 while(this. enqueue5torage.length) {
18 this. dequeuestorage.push(this. enqueue5torage.pop()); 19
20
21 return this. dequeueStorage.pop();
22
23
24 console.warn('Attempting to dequeue from an empty queue');
25 return undefined; 26
How it Works
We have two storage stacks, this ._enqueueStorage and
this . dequeuestorage . To see how they interact, let’s go thrDugh an example.
Enqueuing
We want to put 5 elements onto the queue: 1, 2, 3, 4, and s . We enqueue
all of these, and they all go into enqueuestorage .
enqueuestorage: [1, 2, 3, 4, 5] dequeuestorage: []
We now want to dequeue an item. Let’s dive into our dequeue function.
Dequeuing
We skip the if-statement on line 12 since dequeuestorage is empty. We move
on to line 16.
Inside that if-statement (line 16), we pop every item off of enqueuestorage and put them into dequeuestorage . When the while-loop (lines 17 - 19) is finished, enqueuestorage is empty and dequeuestorage has the five items, but in reverse.
enqueuestorage: [) dequeuestorage: [5, 4, 3, 2, 1]
On line 21, we pop dequeuestorage and return the item, i.
enqueuestorage: [] dequeuestorage: [5, 4, 3, 2]
If we want to dequeue again, we can enter the dequeue method once more. This time we go into the first if-statement and pop an item off of dequeuestorage and return it.
enqueuestorage: [] dequeuestorage: [5, 4, 3]
We can keep dequeuing if we like. As long as dequeuestorage has items in it, the last item will be popped off and returned to us.
Summary
These steps together make it so our queue functions properly. Enqueuing pushes items onto one stack. Dequeuing pops them from the second stack. When the second stack is empty and we want to dequeue, we empty the first stack onto the second, reversing the order of items.
Enqueue Time
Every enqueue event is a simple push onto a stack. This means that each enqueue has a time complexity of:
0(1)
Dequeue Time
So, for most cases, we have o(1) , and for a few rare cases, we have o(n) We can merge these into a single time complexity.
Queue Lifecycle
Let’s track the life of three items in our queue. Starting with an empty queue, let’s enqueue i , 2, and 3 . This puts them on our first stack.
enqueuestorage: [1, 2, 3] dequeuestorage: []
So far, we’ve performed 3 operations: inserting each of those items onto the stack.
Let’s dequeue all three items. First, all items from enqueuestorage get
transferred to dequeuestorage .
enqueuestorage: [] dequeuestorage: [1, 2, 3]
We’ll say that a transference is 1 Dperation. This is another 3 operatiDns total, bringing us up to 6.
Top comments (0)