Queue & Stack Simulator

Part 1: Queues — FIFO and Its Variants

What Is a Queue?

A queue is an ordered collection with two access points. New elements join at the back (tail/rear); elements leave from the front (head). Once an element is behind another, it cannot overtake it. This mirrors everyday queues: a ticket counter, a print spooler, a network packet buffer, or a lineup for a roller coaster. The element that has been waiting the longest is always served first.

The three core operations are enqueue (add to back, O(1)), dequeue (remove from front, O(1)), and peek/front (inspect front without removing, O(1)). All three are constant-time in a correctly implemented queue. Searching for an arbitrary element takes O(n). There is no concept of random access — you cannot jump to position 5 without dequeuing positions 0–4 first.

Part 2: Stacks — LIFO and Its Variants

What Is a Stack?

A stack is a collection where all access happens at a single end — the top. You can only push to the top, pop from the top, or peek at the top. Think of a stack of plates: you can only take the plate on top, and you can only add a plate to the top. The paradox of the stack is that it naturally reverses order: push A, B, C in that sequence, and they come out C, B, A. This reversal property, combined with the "remember context and return to it" semantic, makes stacks the natural choice for recursive processes, expression evaluation, and state backtracking.

Every function call implicitly uses a stack — the call stack. When you invoke main → foo → bar, each frame is pushed. When bar returns, its frame is popped. Stack overflow occurs when recursion depth exceeds the allocated stack size — generally around 1–8 MB on most platforms.

Part 3: Queue vs Stack — When to Use Which

Implementing a Queue from Two Stacks

One of the classic computer science interview puzzles: implement a FIFO queue using only two LIFO stacks. The trick is to use one stack for enqueuing (inbox) and another for dequeuing (outbox). Enqueue always pushes to inbox. Dequeue pops from outbox; if outbox is empty, pour all elements from inbox to outbox (which reverses them, turning LIFO into FIFO for the next batch). Each element moves from inbox to outbox at most once, giving amortized O(1) dequeue. This pattern is used in lock-free queue implementations (Michael-Scott queue) and in functional languages where lists are immutable.

Implementing a Stack from Two Queues

Less practical but instructive: maintain two queues q1 and q2. To push value x: enqueue to q2, then enqueue all elements from q1 to q2, then swap names. q1 now has x at the front (LIFO). To pop: dequeue from q1. Push is O(n), pop is O(1). Alternatively, push is O(1) and pop is O(n) — you must dequeue n-1 elements to reach the bottom. This is O(n) overall and not used in practice; its value is pedagogical.

Part 4: Implementations in Common Languages

queue := []int{}}
// Enqueue — O(1) amortized
queue = append(queue, 42)
// Dequeue — O(1) with head pointer trick
// (simple slice: re-slice, underlying array sticks around)
front := queue[0]
queue = queue[1:]
// Better: use container/ring or a linked list
import "container/list"
q := list.New()
q.PushBack(42)          // enqueue
el := q.Front()         // peek
q.Remove(el)            // dequeue

stack := []int{}}
// Push — O(1) amortized
stack = append(stack, 42)
// Pop — O(1)
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// Peek — O(1)
peek := stack[len(stack)-1]

from collections import deque
q = deque()
q.append(42)        # enqueue back — O(1)
q.appendleft(1)     # enqueue front (deque only)
front = q[0]        # peek — O(1)
q.popleft()         # dequeue front — O(1)
q.pop()             # dequeue back (deque only)

# Priority Queue
import heapq
pq = []
heapq.heappush(pq, (1, 'task-A'))  # (priority, value)
pri, val = heapq.heappop(pq)       # lowest priority first

stack = []
stack.append(42)       # push — O(1) amortized
top = stack.pop()      # pop — O(1)
peek = stack[-1]       # peek — O(1)

# Min Stack O(1)
class MinStack:
    def __init__(self):
        self._s = []
        self._min = []
    def push(self, v):
        self._s.append(v)
        m = min(v, self._min[-1]) if self._min else v
        self._min.append(m)
    def pop(self):
        self._s.pop(); self._min.pop()
    def get_min(self):
        return self._min[-1]

// Queue (Array — shift is O(n)! Use a class)
class Queue {
  #data = []; #head = 0;
  enqueue(v) { this.#data.push(v); }
  dequeue() {
    if (this.isEmpty()) return undefined;
    const v = this.#data[this.#head++];
    if (this.#head > this.#data.length / 2) {
      this.#data = this.#data.slice(this.#head);
      this.#head = 0;
    }
    return v;
  }
  peek()    { return this.#data[this.#head]; }
  isEmpty() { return this.#head >= this.#data.length; }
}
// Stack
const stack = [];
stack.push(42);         // push
const top = stack.pop(); // pop

// Queue — prefer ArrayDeque over LinkedList
Queue<Integer> q = new ArrayDeque<>();
q.offer(42);       // enqueue (returns false if full)
int front = q.peek(); // peek (null if empty)
q.poll();          // dequeue (null if empty)

// Stack — prefer ArrayDeque over Stack class
Deque<Integer> stack = new ArrayDeque<>();
stack.push(42);    // push
int top = stack.peek();
stack.pop();

// Priority Queue (min-heap by default)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(3);
pq.poll(); // returns 1

Part 5: Common Pitfalls and Gotchas

Part 6: Complexity Summary — All Types

All structures listed have O(n) space complexity for n stored elements. Circular queue uses O(capacity). Min/Max stack uses O(2n) ≈ O(n).