Stack and Queue — কোন দিক দিয়ে ঢোকে, কোন দিক দিয়ে বের হয়

Stack-এ শেষের জিনিস আগে বের হয় (LIFO)। Queue-তে আগের জিনিস আগে বের হয় (FIFO)। এই পার্থক্য মনে রাখলে bracket মিলানো, BFS ও sliding window-তে কোনটি লাগবে বোঝা সহজ হয়।

1. Stack: একই প্রান্তে push ও pop

প্রতিটি stack-এর উপরের বাক্সটি top। নতুন মান সেখানেই বসে, pop-ও সেখান থেকেই হয়।

4, 9, 2 ঢোকালে প্রথমে বের হবে 2

1. শুরু

   খালি

2. push(4)

   ↑ top · এখানেই push / pop

   চিহ্নিত ঘর: 4

3. push(9)

   ↑ top · এখানেই push / pop

   চিহ্নিত ঘর: 9

   4

4. push(2)

   ↑ top · এখানেই push / pop

   চিহ্নিত ঘর: 2

   9

   4

5. pop() → 2

   ↑ top · এখানেই push / pop

   9

   4

   সবচেয়ে শেষে ঢোকা 2 বের হলো।

6. pop() → 9

   ↑ top · এখানেই push / pop

   4

   4 প্রথমে ঢুকেছিল; সেটি এখনও আছে।

2. Bracket মিলানো: খোলা কিন্তু বন্ধ হয়নি—এমনগুলো রাখো

Input ([])(। Closing bracket এলে stack-এর top-এর সঙ্গে মিলিয়ে pop করি।

শেষের খোলা bracket-এর জন্য input অবৈধ

1. ( পড়ে push

   ↑ top · এখানেই push / pop

   চিহ্নিত ঘর: (

2. [ পড়ে push

   ↑ top · এখানেই push / pop

   চিহ্নিত ঘর: [

   (

3. ] পড়ে [ মেলাও ও pop

   ↑ top · এখানেই push / pop

   (

4. ) পড়ে ( মেলাও ও pop

   খালি

   এ পর্যন্ত সব bracket মিলে গেছে।

5. শেষের ( পড়ে push

   ↑ top · এখানেই push / pop

   চিহ্নিত ঘর: (

   Input শেষ, stack খালি নয়: এই bracket আর বন্ধ হয়নি।

অবৈধ হওয়ার তিনটি কারণ: খালি stack-এ closing bracket, top-এর সঙ্গে না-মেলা closing bracket, অথবা শেষে কিছু opening bracket থেকে যাওয়া।

3. Queue: পেছনে যোগ, সামনে থেকে বের

A, B, C ঢোকালে বের হওয়ার ক্রমও A, B, C

1. শুরু

   খালি

2. enqueue A

   front → rear

   চিহ্নিত ঘর: A

3. enqueue B

   front → rear

   A

   চিহ্নিত ঘর: B

4. enqueue C

   front → rear

   A

   B

   চিহ্নিত ঘর: C

5. dequeue → A

   front → rear

   B

   C

6. dequeue → B

   front → rear

   C

Python-এ queue বানাতে collections.deque সুবিধাজনক। list.pop(0) করলে বাকি reference-গুলো বাঁয়ে সরাতে হয়।

Operation	[A, B, C, D] থেকে A বাদ দিতে কী হয়	খরচ
list.pop(0)	B, C, D-এর তিনটি reference সরাতে হয়	O(n)
deque.popleft()	সামনে থেকে একটি element বাদ যায়; বাকি সব element সরাতে হয় না	O(1)

List দিয়ে nটি dequeue করলে মোট খরচ O(n²) হতে পারে। Deque-এর এই operation-গুলোর মোট খরচ O(n)।

4. BFS: আগের দূরত্বের কাজ আগে শেষ হয়

S থেকে শুরু করি। প্রতিবেশীদের বর্ণানুক্রমে queue-তে ঢোকাই। ঢোকানোর সময়ই visited করি, যাতে একই node দুবার না ঢোকে।

flowchart TD
  S["S · দূরত্ব 0"] --> A["A · দূরত্ব 1"]
  S --> B["B · দূরত্ব 1"]
  A --> C["C · দূরত্ব 2"]
  A --> D["D · দূরত্ব 2"]
  B --> E["E · দূরত্ব 2"]

ধাপ	সামনে থেকে বের হলো	নতুন ঢুকল	queue: front → back
শুরু	—	S	[S]
1	S	A, B	[A, B]
2	A	C, D	[B, C, D]
3	B	E	[C, D, E]
4	C	কেউ নয়	[D, E]
5	D	কেউ নয়	[E]
6	E	কেউ নয়	[]

A ও B-এর পরে C, D, E বের হয়। সব edge-এর খরচ সমান হলে এই ক্রম shortest-path distance দেয়। ভিন্ন weight-এর ক্ষেত্রে সাধারণ BFS যথেষ্ট নয়।

একই ধারণা 3 × 3 খালি grid-এ

1. মাঝের cell থেকে চারদিকে চলার দূরত্ব

   2

   1

   2

   1

   চিহ্নিত ঘর: 0

   1

   2

   1

   2

   শুরুতে 0; পাশের চারটি cell 1; কোণগুলো 2 ধাপ দূরে। তির্যক চলা নেই।

বিস্তারিত: Graph অধ্যায়।

5. Monotonic stack: কার উত্তর এখনও বাকি?

[2, 1, 5, 3]-এর প্রতিটি মানের ডানদিকে প্রথম বড় মান চাই। Stack-এ উত্তর না-পাওয়া index রাখি; তাদের মান নিচ থেকে উপরে কমতে থাকে।

5 এলে অপেক্ষায় থাকা 1 ও 2—দুজনের উত্তর মেলে

1. i = 1 পর্যন্ত: দুই index অপেক্ষায়

   ↑ top · এখানেই push / pop

   1: 1

   0: 2

   প্রতি বাক্সে index: value। top-এ index 1।

2. i = 2, value = 5: দুজনকে pop করে 2 push

   ↑ top · এখানেই push / pop

   চিহ্নিত ঘর: 2: 5

   ans[1] = 5 এবং ans[0] = 5।

3. i = 3, value = 3: অপেক্ষায় যোগ

   ↑ top · এখানেই push / pop

   চিহ্নিত ঘর: 3: 3

   2: 5

   শেষ পর্যন্ত 5 ও 3-এর ডানে বড় মান নেই।

i	মান	stack-এ কাজ	index stack: bottom → top	নতুন উত্তর
0	2	0 push	[0]	—
1	1	1 push	[0,1]	—
2	5	1 pop, 0 pop, 2 push	[2]	ans[1]=5, ans[0]=5
3	3	3 push	[2,3]	—
শেষ	—	বাকি index-এর উত্তর নেই	[2,3]	ans[2]=ans[3]=-1

ফল [5, 5, -1, -1]। প্রতিটি index একবার push ও সর্বোচ্চ একবার pop হয়; nested while থাকলেও মোট O(n)।

6. Monotonic deque: window-র সবচেয়ে বড় মান

Array [1, 3, -1, -3, 5, 3, 6, 7], window size k = 3। Deque-এ index রাখি; তাদের value সামনে থেকে পেছনে কমতে থাকে। তাই front-এর value-ই maximum।

নতুন মান x নেওয়ার সময়:

1. Front-এর index window ছেড়ে গেলে সরাও।
2. পেছন থেকে x-এর চেয়ে ছোট বা সমান মানের index সরাও। নতুন x অন্তত ততটাই বড় এবং বেশি দিন window-তে থাকবে।
3. নতুন index পেছনে ঢোকাও; window পূর্ণ হলে front-এর মান লিখে রাখো।

i = 3 থেকে i = 4: deque-এর দুই প্রান্তের কাজ

1. i = 3 · window [3, −1, −3]

   front → rear

   চিহ্নিত ঘর: 1: 3

   2: −1

   3: −3

   প্রতি বাক্সে index: value। Front-এর 3-ই maximum।

2. i = 4 · index 1 window ছেড়েছে

   front → rear

   2: −1

   3: −3

   পুরনো maximum সামনে দিয়ে বের হলো।

3. নতুন 5 দুই ছোট মানকে সরায়

   front → rear

   চিহ্নিত ঘর: 4: 5

   পেছন থেকে −3, তারপর −1 বাদ। নতুন window [-1, -3, 5]-এর maximum 5।

পূর্ণ trace-এ deque-এর index ও value আলাদা রাখা হয়েছে, যাতে duplicate মান থাকলেও কোনটি বাদ যায় বোঝা যায়।

i	x	বাদ যাওয়া index	deque indices	deque values	window maximum
0	1	—	[0]	[1]	window পূর্ণ নয়
1	3	পেছনে 0	[1]	[3]	window পূর্ণ নয়
2	−1	—	[1,2]	[3,-1]	3
3	−3	—	[1,2,3]	[3,-1,-3]	3
4	5	সামনে 1; পেছনে 3, 2	[4]	[5]	5
5	3	—	[4,5]	[5,3]	5
6	6	পেছনে 5, 4	[6]	[6]	6
7	7	পেছনে 6	[7]	[7]	7

ফল [3, 3, 5, 5, 6, 7]। প্রতিটি index একবার ঢোকে ও সর্বোচ্চ একবার বের হয়: O(n) সময়, O(k) অতিরিক্ত জায়গা।

নিজে চেষ্টা করো: Next Greater-এর table-টি [4, 2, 6, 1] দিয়ে করো। তারপর sliding window-তে প্রতিটি বাদ যাওয়া index-এর কারণ বলো: মেয়াদ শেষ, নাকি আরও ভালো মান এসেছে? পরের পাঠ: operations ও patterns।