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 ধারণা, চিত্র	LIFO বনাম FIFO
2	Valid Parentheses	unmatched bracket শনাক্ত করা
3	Decode String	nested frame বন্ধ হলে আগের context ফেরত আনা
4	Queue via Stacks	মাঝে মাঝে transfer করেও amortized cost কম রাখা
5	Sliding Window Maximum	পুরনো ও অপ্রয়োজনীয় 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]
# }

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 যোগ করো।

শেষ window-তে নতুন duration 4 আসে

1. Duration 3, 1, 3, 1, 4; window [2,5)

   03

   11

   চিহ্নিত ঘর: 23↑ left

   চিহ্নিত ঘর: 31

   চিহ্নিত ঘর: 44↑ right

   Index 1 এবং তার আগের সব candidate expired।

2. Candidate index শুধু 4

   04

   নতুন 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 · Unit tests

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))।