# Queues & Deques — Part 2: Interview Problems

Six problems: queue design (two stacks, circular buffer), time-window eviction, simulation with queues, scheduling, and the monotonic deque for Sliding Window Maximum.

## 1. Implement Queue using Stacks (LeetCode 232)

**🟢 Easy.** Implement a FIFO queue with only stack operations: `push`, `pop`, `peek`, `empty`.

```text
push(1), push(2), peek() → 1, pop() → 1, empty() → false
```

**Approach.** Two stacks: `inbox` receives pushes; `outbox` serves pops. When `outbox` is empty, move everything from `inbox` (this reverses the order). Each element moves at most once.

**Complexity.** Amortized O(1) per operation.

```typescript
class MyQueue {
  private inbox: number[] = [];
  private outbox: number[] = [];
  push(x: number): void { this.inbox.push(x); }
  private shift(): void {
    if (!this.outbox.length) while (this.inbox.length) this.outbox.push(this.inbox.pop()!);
  }
  pop(): number { this.shift(); return this.outbox.pop()!; }
  peek(): number { this.shift(); return this.outbox[this.outbox.length - 1]; }
  empty(): boolean { return !this.inbox.length && !this.outbox.length; }
}
```

```python
class MyQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def _shift(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._shift()
        return self.outbox.pop()

    def peek(self):
        self._shift()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox
```

## 2. Number of Recent Calls (LeetCode 933)

**🟢 Easy.** `ping(t)` records a request at time t (strictly increasing) and returns how many requests happened in `[t − 3000, t]`.

```text
ping(1) → 1, ping(100) → 2, ping(3001) → 3, ping(3002) → 3
```

**Approach.** Keep a queue of timestamps; on each ping, append t and evict from the front while the oldest is older than `t − 3000`. The queue length is the answer. This is the core of a sliding-window rate limiter.

**Complexity.** Amortized O(1) per ping.

```typescript
class RecentCounter {
  private q: number[] = [];
  private head = 0;
  ping(t: number): number {
    this.q.push(t);
    while (this.q[this.head] < t - 3000) this.head++;
    return this.q.length - this.head;
  }
}
```

```python
from collections import deque

class RecentCounter:
    def __init__(self):
        self.q = deque()

    def ping(self, t):
        self.q.append(t)
        while self.q[0] < t - 3000:
            self.q.popleft()
        return len(self.q)
```

## 3. Sliding Window Maximum (LeetCode 239)

**🔴 Hard.** Return the maximum of every contiguous window of size `k`.

```text
nums = [1,3,-1,-3,5,3,6,7], k = 3 → [3,3,5,5,6,7]
```

**Approach.** Monotonic decreasing deque of indices: pop the front when it leaves the window, pop smaller values from the back before pushing the new index, and read the maximum at the front.

**Complexity.** O(n) time, O(k) space.

```typescript
function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  let head = 0;
  const out: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    if (head < dq.length && dq[head] <= i - k) head++;
    while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[head]]);
  }
  return out;
}
```

```python
from collections import deque

def max_sliding_window(nums, k):
    dq, out = deque(), []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out
```

## 4. Design Circular Queue (LeetCode 622)

**🟠 Medium.** Implement a fixed-capacity circular queue: `enQueue`, `deQueue`, `Front`, `Rear`, `isEmpty`, `isFull`.

```text
k=3: enQueue 1,2,3 → true; enQueue 4 → false; Rear → 3; deQueue; enQueue 4; Rear → 4
```

**Approach.** A fixed array plus `head` and `size`. The tail slot is `(head + size) % k`; the rear element is at `(head + size − 1) % k`.

**Complexity.** O(1) per operation, O(k) space.

```typescript
class MyCircularQueue {
  private buf: number[];
  private head = 0;
  private size = 0;
  constructor(k: number) { this.buf = new Array(k).fill(0); }
  enQueue(value: number): boolean {
    if (this.isFull()) return false;
    this.buf[(this.head + this.size) % this.buf.length] = value;
    this.size++;
    return true;
  }
  deQueue(): boolean {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.buf.length;
    this.size--;
    return true;
  }
  Front(): number { return this.isEmpty() ? -1 : this.buf[this.head]; }
  Rear(): number { return this.isEmpty() ? -1 : this.buf[(this.head + this.size - 1) % this.buf.length]; }
  isEmpty(): boolean { return this.size === 0; }
  isFull(): boolean { return this.size === this.buf.length; }
}
```

```python
class MyCircularQueue:
    def __init__(self, k):
        self.buf = [0] * k
        self.head = self.size = 0

    def enqueue(self, value):
        if self.is_full():
            return False
        self.buf[(self.head + self.size) % len(self.buf)] = value
        self.size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return False
        self.head = (self.head + 1) % len(self.buf)
        self.size -= 1
        return True

    def front(self):
        return -1 if self.is_empty() else self.buf[self.head]

    def rear(self):
        return -1 if self.is_empty() else self.buf[(self.head + self.size - 1) % len(self.buf)]

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == len(self.buf)
```

## 5. Dota2 Senate (LeetCode 649)

**🟠 Medium.** Senators from parties R and D vote in rounds; each can ban one opposing senator's future votes. Predict the winning party.

```text
"RDD" → "Dire"
```

**Approach.** Two queues of indices. Repeatedly compare the fronts: the earlier senator bans the other and re-enters at the back with index `+ n` (next round). The party whose queue empties first loses.

**Complexity.** O(n) time (each round removes one senator), O(n) space.

```typescript
function predictPartyVictory(senate: string): string {
  const n = senate.length, r: number[] = [], d: number[] = [];
  for (let i = 0; i < n; i++) (senate[i] === "R" ? r : d).push(i);
  let hr = 0, hd = 0;
  while (hr < r.length && hd < d.length) {
    const a = r[hr++], b = d[hd++];
    if (a < b) r.push(a + n); else d.push(b + n);
  }
  return hr < r.length ? "Radiant" : "Dire";
}
```

```python
from collections import deque

def predict_party_victory(senate):
    n = len(senate)
    r = deque(i for i, c in enumerate(senate) if c == "R")
    d = deque(i for i, c in enumerate(senate) if c == "D")
    while r and d:
        a, b = r.popleft(), d.popleft()
        if a < b:
            r.append(a + n)          # R acts first, bans D, votes again next round
        else:
            d.append(b + n)
    return "Radiant" if r else "Dire"
```

## 6. Task Scheduler (LeetCode 621)

**🟠 Medium.** CPU tasks (letters) each take one unit; identical tasks need `n` idle units between them. Return the minimum total time.

```text
tasks = [A,A,A,B,B,B], n = 2 → 8   (A B _ A B _ A B)
```

**Approach.** The most frequent task forms the skeleton: `(maxFreq − 1)` full blocks of length `n + 1`, plus one final slot per task tied for the max frequency. If there are enough other tasks to fill every gap, no idling is needed and the answer is just the task count.

**Complexity.** O(T) time, O(26) space.

```typescript
function leastInterval(tasks: string[], n: number): number {
  const counts = new Map<string, number>();
  for (const t of tasks) counts.set(t, (counts.get(t) ?? 0) + 1);
  const maxFreq = Math.max(...counts.values());
  const tied = [...counts.values()].filter((c) => c === maxFreq).length;
  return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + tied);
}
```

```python
def least_interval(tasks, n):
    counts = {}
    for t in tasks:
        counts[t] = counts.get(t, 0) + 1
    max_freq = max(counts.values())
    tied = sum(1 for c in counts.values() if c == max_freq)
    return max(len(tasks), (max_freq - 1) * (n + 1) + tied)
```