# Stack ও Queue — nested job batch runner

একটি ছোট print server একই কাজের batch বারবার চালায়। Command-এ nested repetition থাকে। সেটিকে খুলে job-গুলো আসার ক্রমে চালাতে হবে; তারপর শেষ `k`টি job-এর মধ্যে দীর্ঘতম job-এর duration report করতে হবে। Parser-এর stack, execution-এর queue, আর rolling maximum-এর monotonic deque—তিনটিই এই একই pipeline-এর অংশ।

**কোর্স-সংযোগ:** Microsoft Module 1-এর stack, queue ও operation cost-এর অনুশীলন। Monotonic deque হলো এই ভিত্তির ওপর বাড়তি pattern; এটি কোর্সের নির্দিষ্ট assignment দাবি করা হচ্ছে না।

## ১. আগে পড়বে

| ক্রম | পড়া | কী শিখবে |
| --- | --- | --- |
| 1 | [Stack/Queue ধারণা](../04-stack-and-queue/concept.md), [চিত্র](../04-stack-and-queue/visual-explanation.md) | LIFO বনাম FIFO |
| 2 | [Valid Parentheses](../04-stack-and-queue/problems/001-valid-parentheses.md) | unmatched bracket শনাক্ত করা |
| 3 | [Decode String](../04-stack-and-queue/problems/010-decode-string.md) | nested frame বন্ধ হলে আগের context ফেরত আনা |
| 4 | [Queue via Stacks](../04-stack-and-queue/problems/004-queue-via-stacks.md) | মাঝে মাঝে transfer করেও amortized cost কম রাখা |
| 5 | [Sliding Window Maximum](../04-stack-and-queue/problems/019-sliding-window-maximum.md) | পুরনো ও অপ্রয়োজনীয় candidate সরানো |

## ২. সমস্যার চুক্তি ও grammar

`run_batch(program, window=3, limit=10000)` লিখো। job-এর format `LABEL:duration`; LABEL-এ শুধু ইংরেজি letter, duration একটি positive integer। `count[sequence]` ভেতরের sequence-কে count বার চালায়। nesting বৈধ। token-এর মাঝে whitespace থাকতে পারে; comma নেই।

- `A:3 B:1` মানে A job-এর duration 3, তারপর B-এর duration 1।
- `2[A:3 B:1]` মানে `A,B,A,B`; প্রতিটি job নিজের duration বহন করে।
- repetition count positive; bracket-এর ভেতর অন্তত একটি job থাকতে হবে। root-এর খালি program বৈধ।
- nesting সর্বোচ্চ 100; যেকোনো frame expand করার পর job সংখ্যা `limit` ছাড়ালে `ValueError`। `limit ≥ 1`, `window ≥ 1`। শেখার input-এ source সর্বোচ্চ 100000 character রাখো।
- একটি worker একবারে একটি job চালায়, time 0 থেকে, কোনো gap নেই। output `completed`-এ `(label, finish_time)` থাকবে। একই label একাধিকবার আসতে পারে।
- `rolling_max`-এ **পূর্ণ window**-এর duration maximum থাকবে; completion time-এর maximum নয়। job সংখ্যা window-এর চেয়ে ছোট হলে `[]`।

### উদাহরণ

```python
run_batch("2[A:3 B:1] C:4", window=3)
# {
#   "completed": [("A", 3), ("B", 4), ("A", 7), ("B", 8), ("C", 12)],
#   "rolling_max": [3, 3, 4]
# }
```

```mermaid
flowchart TD
    P["2[A:3 B:1] C:4"] --> S["Stack দিয়ে repetition খুলে দাও"]
    S --> Q["FIFO: A3 → B1 → A3 → B1 → C4"]
    Q --> W["এক worker: finish 3, 4, 7, 8, 12"]
    W --> D["Duration window: 3,1,3 / 1,3,1 / 3,1,4"]
    D --> R["Rolling maximum: 3, 3, 4"]
```

## ৩. চারটি guided milestone

### ধাপ A — token পড়া ও frame stack

`decode_jobs(program, limit)` বানাও। আগে letter, integer, `[`, `]`, `:` token আলাদা করো। অচেনা character দেখলে ignore করবে না; `ValueError` দেবে। Job-এ `LABEL`, `:`, positive duration—তিন token চাই।

`count[` পেলে `(আগের job list, count)` stack-এ রেখে নতুন খালি frame শুরু করো। `]` পেলে বর্তমান frame count বার আগের frame-এ যোগ করো। শেষে stack খালি না হলে bracket বন্ধ হয়নি।

**Invariant:** stack-এ প্রতিটি খোলা batch-এর বাইরের context আছে; `jobs` কেবল বর্তমান frame। Hint: repeated list তৈরির **আগে** `len(outer) + count * len(jobs) <= limit` যাচাই করো। নয়তো খুব বড় expansion memory খেয়ে ফেলবে।

**Checkpoint:** `2[A:2 2[B:1]]` খুলে `[A2,B1,B1,A2,B1,B1]`। `2[]`, `A:0`, `A:1]`, `2[A:1` reject হবে।

### ধাপ B — দুই stack-এ FIFO

`TwoStackQueue`-তে `incoming` ও `outgoing` রাখো। push শুধু incoming-এ। pop-এর সময় outgoing খালি হলে incoming-এর সব item pop করে outgoing-এ রাখো। তারপর outgoing থেকে pop করো।

**Invariant:** outgoing-এর top হলো সবচেয়ে পুরনো waiting item। Hint: outgoing-এ item থাকা অবস্থায় transfer করলে FIFO ভেঙে যাবে।

**Checkpoint:** push 1, push 2, pop → 1, push 3, pop → 2, pop → 3। খালি queue থেকে pop করলে `IndexError`। সব job enqueue করে ক্রমে dequeue করো; `clock += duration` দিয়ে finish time লেখো।

### ধাপ C — monotonic deque-এ rolling maximum

`rolling_maximum(values, window)`-এ value নয়, **index** রাখো। নতুন index `i` এলে প্রথমে `i-window` বা তার আগের index সামনে থেকে বাদ দাও। তারপর পেছনের value নতুনটির চেয়ে ছোট বা সমান হলে সরাও। শেষে `i` যোগ করো।

```dsa
kind: array
title: "শেষ window-তে নতুন duration 4 আসে"
steps:
  - label: "Duration 3, 1, 3, 1, 4; window [2,5)"
    values: [3, 1, 3, 1, 4]
    active: [2, 3, 4]
    pointers: {left: 2, right: 4}
    note: "Index 1 এবং তার আগের সব candidate expired।"
  - label: "Candidate index শুধু 4"
    values: [4]
    note: "নতুন 4 আগের 1 ও 3-এর চেয়ে বড় এবং পরে এসেছে; ওরা আর কোনো পরবর্তী window-র maximum হতে পারবে না।"
```

**Invariant:** deque-এর index বাড়তে থাকে, value কমতে থাকে; front বর্তমান window-এর maximum। সমান value-তে পুরনো index বাদ দেওয়া নিরাপদ, কারণ নতুনটি বেশি দিন window-তে থাকবে।

**Checkpoint:** `[2,2,1], k=2 → [2,2]`; `k=1`-এ input-এর মানই ফেরে। প্রতিবার `max(window)` চালাবে না।

### ধাপ D — pipeline ও error boundary

`run_batch`-এ আগে window যাচাই, তারপর decode, queue execution, তারপর rolling report করো। decode ব্যর্থ হলে আংশিক job চালানো যাবে না। এই toy runner কোনো বাহ্যিক printer-এ কাজ পাঠায় না; শুধু result তৈরি করে।

**Checkpoint:** sample-এর finish times ও rolling maxima দুটোই মেলাও। Empty program-এ দুই output list-ই খালি। malformed input-এর test আলাদা করে চালাও।

## ৪. Unit tests ও reference

[Python implementation](../practice/stack_queue_lab.py) · [Unit tests](../practice/test_stack_queue_lab.py)

```bash
python -m unittest discover -s practice -p 'test_stack_queue_lab.py' -v
```

১০টি test-এ nested parsing, invalid grammar, expansion/depth limit, interleaved FIFO, duplicate duration, window edge ও known output আছে। ১৫০ random duration stream-এর maximum সরাসরি window scan-এর সঙ্গে মেলে। নিজের solution-এ dictionary বা array ব্যবহার করা নিষিদ্ধ নয়; কিন্তু FIFO-এর জন্য `pop(0)` ব্যবহার করলে এই lab-এর queue milestone পূরণ হবে না।

Reference-এর decoder-এ `outer.extend(...)` লক্ষ্য করো। প্রতিটি ছোট batch-এর জন্য আগের পুরো outer list আবার কপি করলে flat input-ও অপ্রয়োজনীয়ভাবে ধীর হবে।

## ৫. Coverage ও complexity

| Pattern | কাজ |
| --- | --- |
| Stack/context restoration | nested batch expansion ও bracket error |
| Two-stack queue | FIFO execution; প্রতি item সর্বোচ্চ এক transfer |
| Monotonic deque | fixed window-এর maximum |
| আলাদা অনুশীলন | BFS, expression calculator, histogram area, min stack ও shortest subarray এই lab-এ নেই |

Source length `m`, expanded job সংখ্যা `J`, nesting depth `d` হলে decoder-এর সময় `O(m + dJ)`; nested expansion-এ একই job একাধিক level-এ copy হতে পারে। Queue ও rolling report-এর সময় `O(J)`। Queue-র একটি pop worst-case `O(J)`, কিন্তু সব operation মিলিয়ে প্রতি job amortized `O(1)`। Parser/token/output-সহ memory `O(m + J + d)`; monotonic deque আলাদাভাবে `O(min(window,J))`।