Day 3: Stacks & Queues

What You'll Learn Today

• How stacks (LIFO) work and how to implement them
• How queues (FIFO) work and how to implement them
• The concept of double-ended queues (Deque)
• Practical applications of stacks and queues

---

Stacks

A stack is a LIFO (Last In, First Out) data structure. The last element added is the first one removed.

flowchart TB
    subgraph Stack["Stack"]
        direction TB
        TOP["← Top"]
        E3["30"]
        E2["20"]
        E1["10"]
    end
    PUSH["push(30)"] --> TOP
    TOP --> POP["pop() → 30"]
    style Stack fill:#3b82f6,color:#fff
    style PUSH fill:#22c55e,color:#fff
    style POP fill:#ef4444,color:#fff

Stack Implementation

class Stack {
  constructor() {
    this.items = [];
  }

  push(value) {
    this.items.push(value);
  }

  pop() {
    if (this.isEmpty()) return undefined;
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) return undefined;
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  get size() {
    return this.items.length;
  }
}

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.pop());  // 30
console.log(stack.peek()); // 20

Stack Time Complexities

Operation	Complexity
push	O(1)
pop	O(1)
peek	O(1)
isEmpty	O(1)
search	O(n)

---

Stack Applications

1. Balanced Parentheses Check

function isValidParentheses(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else if (')]}'.includes(char)) {
      if (stack.pop() !== pairs[char]) return false;
    }
  }
  return stack.length === 0;
}

console.log(isValidParentheses("({[]})")); // true
console.log(isValidParentheses("({[)]}"));  // false

2. Reverse Polish Notation Evaluation

function evalRPN(tokens) {
  const stack = [];

  for (const token of tokens) {
    if (['+', '-', '*', '/'].includes(token)) {
      const b = stack.pop();
      const a = stack.pop();
      switch (token) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(a - b); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(Math.trunc(a / b)); break;
      }
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop();
}

console.log(evalRPN(["3", "4", "+"]));              // 7
console.log(evalRPN(["2", "3", "+", "4", "*"]));    // 20

3. Browser Back/Forward Navigation

class BrowserHistory {
  constructor(homepage) {
    this.backStack = [];
    this.forwardStack = [];
    this.current = homepage;
  }

  visit(url) {
    this.backStack.push(this.current);
    this.current = url;
    this.forwardStack = [];
  }

  back() {
    if (this.backStack.length === 0) return this.current;
    this.forwardStack.push(this.current);
    this.current = this.backStack.pop();
    return this.current;
  }

  forward() {
    if (this.forwardStack.length === 0) return this.current;
    this.backStack.push(this.current);
    this.current = this.forwardStack.pop();
    return this.current;
  }
}

---

Queues

A queue is a FIFO (First In, First Out) data structure. The first element added is the first one removed.

flowchart LR
    ENQ["enqueue(30)"] --> BACK["Back"]
    subgraph Queue["Queue"]
        direction LR
        E1["10"]
        E2["20"]
        E3["30"]
    end
    FRONT["Front"] --> DEQ["dequeue() → 10"]
    style Queue fill:#8b5cf6,color:#fff
    style ENQ fill:#22c55e,color:#fff
    style DEQ fill:#ef4444,color:#fff

Queue Implementation (Linked List)

Using shift() on an array is O(n), so a linked list implementation is more efficient.

class QueueNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  enqueue(value) {
    const node = new QueueNode(value);
    if (this.tail) {
      this.tail.next = node;
    } else {
      this.head = node;
    }
    this.tail = node;
    this.length++;
  }

  dequeue() {
    if (!this.head) return undefined;
    const value = this.head.value;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    this.length--;
    return value;
  }

  peek() {
    return this.head ? this.head.value : undefined;
  }

  isEmpty() {
    return this.length === 0;
  }

  get size() {
    return this.length;
  }
}

const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue()); // 10
console.log(queue.peek());    // 20

Queue Time Complexities

Operation	Complexity
enqueue	O(1)
dequeue	O(1)
peek	O(1)
isEmpty	O(1)
search	O(n)

---

Queue Applications

1. Task Scheduler

class TaskScheduler {
  constructor() {
    this.queue = new Queue();
  }

  addTask(task) {
    this.queue.enqueue(task);
    console.log(`Task added: ${task.name}`);
  }

  processNext() {
    if (this.queue.isEmpty()) {
      console.log("No tasks to process");
      return;
    }
    const task = this.queue.dequeue();
    console.log(`Processing: ${task.name}`);
    task.execute();
  }

  processAll() {
    while (!this.queue.isEmpty()) {
      this.processNext();
    }
  }
}

2. Breadth-First Search (BFS)

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'E'],
  D: ['B'],
  E: ['C'],
};

console.log(bfs(graph, 'A')); // ['A', 'B', 'C', 'D', 'E']

---

Double-Ended Queue (Deque)

A Deque allows adding and removing elements from both ends.

flowchart LR
    AFL["addFront()"] --> FRONT["Front"]
    subgraph Deque["Deque"]
        direction LR
        E1["10"]
        E2["20"]
        E3["30"]
    end
    BACK["Back"] --> ABL["addBack()"]
    FRONT --> RFL["removeFront()"]
    BACK --> RBL["removeBack()"]
    style Deque fill:#f59e0b,color:#fff

class Deque {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }

  addFront(value) {
    this.frontIndex--;
    this.items[this.frontIndex] = value;
  }

  addBack(value) {
    this.items[this.backIndex] = value;
    this.backIndex++;
  }

  removeFront() {
    if (this.isEmpty()) return undefined;
    const value = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return value;
  }

  removeBack() {
    if (this.isEmpty()) return undefined;
    this.backIndex--;
    const value = this.items[this.backIndex];
    delete this.items[this.backIndex];
    return value;
  }

  peekFront() {
    return this.items[this.frontIndex];
  }

  peekBack() {
    return this.items[this.backIndex - 1];
  }

  isEmpty() {
    return this.backIndex - this.frontIndex === 0;
  }

  get size() {
    return this.backIndex - this.frontIndex;
  }
}

---

Stack vs. Queue vs. Deque

Feature	Stack	Queue	Deque
Order	LIFO	FIFO	Both ends
Add	top	back	front/back
Remove	top	front	front/back
Use cases	Function calls, Undo	Task processing, BFS	Sliding window

---

Summary

Concept	Description
Stack	LIFO structure with push/pop operations
Queue	FIFO structure with enqueue/dequeue operations
Deque	General-purpose structure with operations from both ends
Call Stack	Uses a stack to manage function invocations

Key Takeaways

1. Both stacks and queues provide O(1) for their primary operations
2. JavaScript arrays work well as stacks but poorly as queues (shift is O(n))
3. Use a linked list for an efficient queue implementation
4. BFS uses queues; DFS uses stacks

---

Practice Problems

Problem 1: Basic

Implement a queue using two stacks.

class QueueUsingStacks {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];
  }
  enqueue(value) { /* implement */ }
  dequeue() { /* implement */ }
}

Problem 2: Intermediate

Implement a stack that supports a min() method in O(1).

Challenge

Implement a function that finds the maximum value in a sliding window using a Deque in O(n).

---

References

• MDN - Array.prototype.push
• Wikipedia - Stack
• Wikipedia - Queue

---

Next up: In Day 4, we'll explore "Hash Tables" — how to achieve O(1) lookups.