REACTO - Queues via Stacks

3.4_queues_via_stacks.md

Queues via Stacks

---

Question

Implement a MyQueue class which implements a queue using two stacks.

---

Hints

• #98: The major difference between a queue and a stack is the order of elements. A queue removes the oldest item and a stack removes the newest item. How could you remove the oldest item from a stack if you only had access to the newest item?
• #114: We can remove the oldest item from a stack by repeatedly removing the newest item (inserting those into the temporary stack) until we get down to one element. Then, after we've retrieved the newest item, putting all the elements back. The issue with this is that doing several pops in a row will require O ( N) work each time. Can we optimize for scenarios where we might do several pops in a row?

---

Solution and Explanation

Approach

• Class uses two stacks (LIFO, insert at tail, remove from tail) to simulate the behavior of a queue (FIFO, insert at tail, remove from head).
• To grab the "head" value, we'll need the last element of the stack.
• Insert into queue via a MyQueue.queue
• When "popping", read from MyQueue.dequeue
  • If MyQueue.dequeue is empty, push all values from queue to dequeue stack
  • Otherwise, pop last value off of dequeue

class MyQueue {
  constructor() {
    this.queue = new Stack();
    this.dequeue = new Stack();
  }
  
  push(value) {
    const newNode = new Node(value);
    this.queue.push(newNode);
  }
  
  shift() {
    while (this.queue.tail !== null) {
      const node = this.queue.pop();
      this.dequeue.push(node);
    }
    const firstInNode = this.dequeue.pop();
    
    return firstInNode.value;
  }
}

class Stack {
  constructor() {
    this.tail = null;
  }
  
  push(node) {
    this.tail.next = node;
    node.prev = this.tail;
    this.tail = node;
  }
  
  pop(val) {
    const removeNode = this.tail;
    if (this.tail) {
      this.tail = this.tail.prev;
      this.tail.next = null;
      removeNode.prev = null;
    }
    return removeNode;
  }
 }

class Node {
  constructor(value) {
    this.value;
    this.prev;
    this.next;
  }

---

Summary

Key Patterns

• Queue - FIFO
• Stack - LIFO