Queue আর deque — সারির নিয়ম

১ · Queue কী — আগে এলে আগে সেবা

সকাল দশটায় মতিঝিলের একটি ব্যাংকে টাকা জমা দিতে গেছেন। কাউন্টারের সামনে লম্বা সারি। নিয়মটা সবাই জানেন: নতুন কেউ এলে দাঁড়ান সারির শেষে, আর ক্যাশিয়ার সেবা দেন সারির একেবারে সামনের জনকে। কেউ মাঝখানে ঢুকতে পারেন না, আর পেছনের জন আগে সেবা পান না। যিনি আগে এসেছেন, তিনি আগে যাবেন। কমলাপুরের টিকিট কাউন্টার, মেট্রোরেলের কার্ড রিচার্জের লাইন, পরীক্ষার হলে খাতা জমার সারি — সবখানে একই নিয়ম।

কম্পিউটারে এই নিয়মে চলা ডেটা স্ট্রাকচারের নাম queue (কিউ)। এর নিয়মের নাম FIFO — First In, First Out: যে আগে ঢোকে, সে আগে বের হয়। আগের পর্বে দেখা stack ঠিক উল্টো — সেখানে LIFO, শেষে ঢোকা থালাটিই আগে ওঠে।

লক্ষ করুন, এখানে আমরা বলিনি queue মেমরিতে কীভাবে রাখা হবে — শুধু বলেছি কোন অপারেশন আছে আর কী নিয়মে চলে। এটিই abstract data type (ADT): একটি চুক্তি। চুক্তিটি পূরণ করা যায় অনেকভাবে — সাধারণ অ্যারে, circular buffer, linked list, এমনকি দুটি stack দিয়ে। এই পর্বের বড় অংশ জুড়ে আমরা এই বাস্তবায়নগুলো তুলনা করব, কারণ প্রতিটির খরচ আলাদা।

২ · সরল অ্যারে-queue — কেন জায়গা নষ্ট হয়

প্রথম চেষ্টা হিসেবে সবচেয়ে সোজা পথ: ৬ ঘরের একটি অ্যারে, আর দুটি index — front (সামনের উপাদান কোথায়) আর rear (পরের উপাদান কোথায় বসবে). enqueue মানে a[rear] = x; rear++, dequeue মানে front++. দুটিই O(1) — শুনতে চমৎকার। কিন্তু কয়েকটি অপারেশন চালিয়ে দেখুন কী ঘটে:

ব্যাংকে কিন্তু মানুষ সরে না — ক্যাশিয়ারই এক কাউন্টার থেকে পরের দিকে তাকান। আমাদের দরকার ঠিক এই চিন্তা: উপাদানগুলো যেখানে আছে সেখানেই থাকুক, শুধু “সামনে কে” আর “পেছনে কোথায়” — এই দুটি চিহ্ন ঘুরে ঘুরে এগোক। অ্যারের শেষে পৌঁছালে চিহ্ন আবার শুরুতে ফিরে যাক, যেন অ্যারের দুই প্রান্ত জোড়া দিয়ে একটি আংটি বানানো হয়েছে।

৩ · Circular buffer — শেষ ঘরের পরে আবার প্রথম ঘর

এই আংটির মতো অ্যারের নাম circular buffer বা ring buffer. কৌশল একটিই — index বাড়ানোর সময় modulo নেওয়া:

cap = 4 হলে index চলে 0 → 1 → 2 → 3 → 0 → 1 … — শেষ ঘরের পরে আবার প্রথম ঘর। একে বলে wrap-around. আমরা রাখব তিনটি সংখ্যা: head (সামনের উপাদানের ঘর), tail (পরের উপাদান যে ঘরে বসবে) আর size (কতজন আছে). নিয়মগুলো:

Pseudocode (0-based index, cap = array length)

ENQUEUE(x):
    if size == cap: report FULL          // overflow
    buf[tail] = x
    tail = (tail + 1) % cap               // wrap around
    size = size + 1

DEQUEUE():
    if size == 0: report EMPTY            // underflow
    x = buf[head]
    head = (head + 1) % cap
    size = size - 1
    return x

// invariant: tail == (head + size) % cap,
// the queue is buf[head], buf[head+1], ... (size items, all mod cap)

এবার cap = 4-এর একটি buffer-এ নিচের ক্রমটি ধাপে ধাপে দেখুন — বিশেষ করে ধাপ ৬-এ tail কীভাবে শেষ থেকে শুরুতে ফেরে, আর ধাপ ৩ ও ৯-এ head আর tail একই ঘরে থাকলেও অর্থ কীভাবে সম্পূর্ণ আলাদা। এই ক্রমটিই নিচের প্রোগ্রাম চালায়।

Full আর empty আলাদা করার তিনটি উপায়

সময়ের হিসাব সহজ: প্রতিটি অপারেশনে কয়েকটি তুলনা, একটি লেখা বা পড়া আর একটি modulo — কোনো লুপ নেই। তাই enqueue, dequeue, front তিনটিই worst case O(1), amortized নয়, সত্যিকারের প্রতিবার। জায়গা Θ(cap), আগে থেকে নির্দিষ্ট। এবার পুরো class চালিয়ে দেখুন — আউটপুটের প্রতিটি লাইন ওপরের ডায়াগ্রামের একটি অবস্থা:

#include <cstdio>
#include <initializer_list>
#include <string>
#include <vector>
using namespace std;
class CircularQueue {
    vector<int> buf;
    int head = 0, tail = 0, sz = 0;       // head: front, tail: next free slot
    int cap() const { return (int)buf.size(); }
public:
    explicit CircularQueue(int c) : buf(c) {}
    int size() const { return sz; }
    bool enqueue(int x) {
        if (sz == cap()) return false;    // full: size == capacity
        buf[tail] = x; tail = (tail + 1) % cap();   // wrap around
        ++sz; return true;
    }
    // dequeue: the caller must check size() > 0 first
    int dequeue() { int x = buf[head]; head = (head + 1) % cap(); --sz; return x; }
    void show(const string& op) const {
        printf("%-12s [", op.c_str());
        for (int i = 0; i < cap(); ++i)
            if ((i - head + cap()) % cap() < sz) printf(i ? " %2d" : "%2d", buf[i]);
            else printf(i ? "  ." : " .");
        printf("]  head=%d tail=%d size=%d\n", head, tail, sz);
    }
};
int main() {
    CircularQueue q(4);
    auto add = [&](int x) { q.show((q.enqueue(x) ? "enqueue " : "FULL ") + to_string(x)); };
    for (int x : {10, 20, 30, 40, 50}) add(x);
    for (int t = 0; t < 2; ++t) q.show("dequeue " + to_string(q.dequeue()));
    for (int x : {50, 60}) add(x);
    while (q.size() > 0) q.show("dequeue " + to_string(q.dequeue()));
}

enqueue 10   [10  .  .  .]  head=0 tail=1 size=1
enqueue 20   [10 20  .  .]  head=0 tail=2 size=2
enqueue 30   [10 20 30  .]  head=0 tail=3 size=3
enqueue 40   [10 20 30 40]  head=0 tail=0 size=4
FULL 50      [10 20 30 40]  head=0 tail=0 size=4
dequeue 10   [ . 20 30 40]  head=1 tail=0 size=3
dequeue 20   [ .  . 30 40]  head=2 tail=0 size=2
enqueue 50   [50  . 30 40]  head=2 tail=1 size=3
enqueue 60   [50 60 30 40]  head=2 tail=2 size=4
dequeue 30   [50 60  . 40]  head=3 tail=2 size=3
dequeue 40   [50 60  .  .]  head=0 tail=2 size=2
dequeue 50   [ . 60  .  .]  head=1 tail=2 size=1
dequeue 60   [ .  .  .  .]  head=2 tail=2 size=0

class CircularQueue:
    def __init__(self, cap):
        self.buf = [None] * cap
        self.head = self.tail = self.size = 0   # head: front, tail: next free slot

    def enqueue(self, x):
        if self.size == len(self.buf):           # full: size == capacity
            return False
        self.buf[self.tail] = x
        self.tail = (self.tail + 1) % len(self.buf)   # wrap around
        self.size += 1
        return True

    def dequeue(self):                           # caller checks size > 0
        x = self.buf[self.head]
        self.head = (self.head + 1) % len(self.buf)
        self.size -= 1
        return x

    def show(self, op):
        cap = len(self.buf)
        cells = [str(self.buf[i]) if (i - self.head) % cap < self.size else "."
                 for i in range(cap)]
        print(f"{op:<12} [{' '.join(f'{c:>2}' for c in cells)}]  "
              f"head={self.head} tail={self.tail} size={self.size}")

q = CircularQueue(4)
for x in [10, 20, 30, 40, 50]:
    q.show(f"enqueue {x}" if q.enqueue(x) else f"FULL {x}")
for _ in range(2):
    q.show(f"dequeue {q.dequeue()}")
for x in [50, 60]:
    q.show(f"enqueue {x}" if q.enqueue(x) else f"FULL {x}")
while q.size > 0:
    q.show(f"dequeue {q.dequeue()}")

enqueue 10   [10  .  .  .]  head=0 tail=1 size=1
enqueue 20   [10 20  .  .]  head=0 tail=2 size=2
enqueue 30   [10 20 30  .]  head=0 tail=3 size=3
enqueue 40   [10 20 30 40]  head=0 tail=0 size=4
FULL 50      [10 20 30 40]  head=0 tail=0 size=4
dequeue 10   [ . 20 30 40]  head=1 tail=0 size=3
dequeue 20   [ .  . 30 40]  head=2 tail=0 size=2
enqueue 50   [50  . 30 40]  head=2 tail=1 size=3
enqueue 60   [50 60 30 40]  head=2 tail=2 size=4
dequeue 30   [50 60  . 40]  head=3 tail=2 size=3
dequeue 40   [50 60  .  .]  head=0 tail=2 size=2
dequeue 50   [ . 60  .  .]  head=1 tail=2 size=1
dequeue 60   [ .  .  .  .]  head=2 tail=2 size=0

৪ · Linked list দিয়ে queue — সীমাহীন সারি

Circular buffer-এর একটিই সীমাবদ্ধতা: cap আগে থেকে ঠিক করতে হয়। কতজন আসবেন জানা না থাকলে কী করবেন? একটি পথ হলো ভর্তি হলে দ্বিগুণ মাপের নতুন অ্যারে বানিয়ে উপাদানগুলো head থেকে ক্রমানুসারে কপি করা — ঠিক পর্ব ১০-এর dynamic array-এর মতো, amortized O(1). আরেকটি পথ linked list (পর্ব ১২): প্রতিটি উপাদান একটি node, যে পরের node-এর ঠিকানা রাখে। দুটি pointer রাখি — head (সামনের node, এখান থেকে বের হয়) আর tail (শেষ node, এর পরে নতুন node জোড়া লাগে).

struct Node { int val; Node* next = nullptr; };

struct ListQueue {
    Node* head = nullptr;   // front: remove here
    Node* tail = nullptr;   // back: insert after this
    void enqueue(int x) {
        Node* n = new Node{x};
        if (tail) tail->next = n; else head = n;   // empty queue: n is also the front
        tail = n;
    }
    int dequeue() {                                // caller checks head != nullptr
        Node* n = head;
        int x = n->val;
        head = n->next;
        if (!head) tail = nullptr;                 // queue became empty: fix tail too!
        delete n;
        return x;
    }
};

দুটি অপারেশনই worst case O(1) — শুধু কয়েকটি pointer বদলায়। কিন্তু দুটি সূক্ষ্ম প্রশ্ন আছে, যা পরীক্ষা আর ইন্টারভিউতে প্রায়ই আসে:

• কেন head-এ বের, tail-এ ঢোকানো — উল্টোটা কেন নয়? Singly linked list-এ শেষ node সরাতে হলে তার আগের node-টি জানা দরকার (তার next null করতে হবে) — সেটি পেতে শুরু থেকে হাঁটতে হয়, O(n). শুরুর node সরানো কিন্তু O(1). তাই সরানোর কাজ head-এ, যোগের কাজ tail-এ।
• শেষ উপাদান বের হলে tail-ও ঠিক করতে হয়। if (!head) tail = nullptr; লাইনটি বাদ দিলে tail মুছে ফেলা node-কে নির্দেশ করে থাকবে (dangling pointer), আর পরের enqueue সেই মৃত node-এ লিখবে — নিঃশব্দে memory নষ্ট। এই ভুলটি AI-এর লেখা কোডেও দেখা যায়।

বাস্তবে অ্যারে-ভিত্তিক queue প্রায় সবসময় দ্রুত চলে, কারণ আধুনিক CPU পাশাপাশি থাকা ডেটা খুব দ্রুত পড়ে (পর্ব ১০)। Linked list queue-এর আসল সুবিধা আসে যখন প্রতিটি উপাদান নিজেই বড় বা আগে থেকে তৈরি node — যেমন operating system-এর ভেতরে প্রসেসের তালিকা, যেখানে node-টি প্রসেসের নিজের কাঠামোর ভেতরেই থাকে।

৫ · দুটি stack দিয়ে queue — amortized O(1)

ইন্টারভিউর একটি অতি প্রিয় প্রশ্ন: “শুধু দুটি stack ব্যবহার করে একটি queue বানান।” প্রথমে অসম্ভব মনে হয় — stack উল্টো ক্রমে বের করে, queue সোজা ক্রমে। কিন্তু উল্টোকে আবার উল্টালে সোজা হয়! একটি থালার স্তূপ আরেক টেবিলে একটি একটি করে সরালে নিচের থালাটি ওপরে চলে আসে।

• in stack: enqueue মানে শুধু in.push(x).
• out stack: dequeue মানে out.pop() — তবে out খালি থাকলে আগে in-এর সব উপাদান একে একে pop করে out-এ push করুন। তাতে সবচেয়ে পুরোনো উপাদানটি out-এর ওপরে চলে আসে।

মূল শর্ত: স্থানান্তর হবে শুধু তখন, যখন out খালি। out-এ কিছু থাকা অবস্থায় in থেকে ঢাললে নতুন উপাদান পুরোনোদের ওপরে বসে ক্রম ভেঙে যাবে। নিচে ৪টি enqueue আর ৪টি dequeue দেখুন। “মোট stack-অপারেশন” সারিতে নজর রাখুন:

Pseudocode (queue from two stacks)

ENQUEUE(x):  in.push(x)

DEQUEUE():
    if out is empty:
        while in is not empty:            // pour: reverses the order
            out.push(in.pop())
    if out is empty: report EMPTY
    return out.pop()

এই “বেশিরভাগ সস্তা, মাঝে মাঝে দামি, কিন্তু গড়ে সস্তা” হিসাবটি এখানে আমরা সরল গণনা দিয়ে করলাম, যাকে বলে aggregate method. পর্ব ৬০-এ একই সমস্যা accounting আর potential method দিয়েও প্রমাণ করব — প্রতিটি enqueue-কে ৪ টাকা দিয়ে ভবিষ্যতের খরচের জন্য জমা রাখার মতো করে। সতর্কতা: amortized মানে “গড়”, তবে এলোমেলো ইনপুটের গড় নয় — এটি যেকোনো ক্রমের জন্য নিশ্চিত গড়। কিন্তু যে সিস্টেমে প্রতিটি অপারেশন সময়মতো শেষ হতেই হবে (যেমন অডিও বা নিয়ন্ত্রণ যন্ত্র), সেখানে মাঝে মাঝের Θ(n) ঝাঁকুনিও বিপদ।

৬ · Deque — দুই মাথা খোলা সারি, আর লাইব্রেরির queue

বাসের দুই দরজার কথা ভাবুন — সামনে দিয়েও ওঠা-নামা যায়, পেছন দিয়েও। deque (উচ্চারণ “ডেক”, double-ended queue) ঠিক এমন: দুই প্রান্তেই ঢোকানো ও বের করা O(1). তাই একই deque দিয়ে queue (পেছনে ঢোকানো, সামনে বের করা) আর stack (একই প্রান্তে ঢোকানো-বের করা) দুটিই বানানো যায়। Circular buffer-এ deque বানানোও সহজ: সামনে ঢোকাতে head = (head - 1 + cap) % cap, পেছন থেকে বের করতে tail = (tail - 1 + cap) % cap.

C++: std::queue একটি adapter, ভেতরে std::deque

std::queue নিজে কোনো ডেটা রাখে না। এটি একটি container adapter — ভেতরে ডিফল্টভাবে একটি std::deque রাখে, আর বাইরে শুধু push, pop, front, back, empty, size খোলা রাখে। এর ওপর লুপ চালানো বা q[i] লেখা যায় না — ইচ্ছাকৃতভাবেই, যাতে কেউ FIFO নিয়ম ভাঙতে না পারে। আর মনে রাখুন, q.pop() কিছু ফেরত দেয় না; মান চাইলে আগে q.front() পড়ুন।

std::deque ভেতরে একটি লম্বা অ্যারে নয়, আবার linked list-ও নয়। এটি অনেকগুলো নির্দিষ্ট মাপের ছোট ব্লক (libstdc++-এ প্রতিটি ৫১২ বাইটের মতো), আর ব্লকগুলোর ঠিকানার একটি তালিকা (map) রাখে। সামনে জায়গা ফুরোলে সামনে নতুন ব্লক, পেছনে ফুরোলে পেছনে — পুরোনো উপাদান কখনো সরাতে হয় না। তাই d[i] O(1) (কোন ব্লক, ব্লকের কোন ঘর — দুটি ভাগ-হিসাব), আর প্রান্তে ঢোকানো O(1). বিনিময়ে প্রতিটি index-এ একটি বাড়তি ধাপ লাগে, তাই সাধারণ ঘোরাঘুরিতে এটি std::vector-এর চেয়ে কিছুটা ধীর।

Python: list.pop(0) কেন ফাঁদ

Python-এর list ভেতরে একটি dynamic array (পর্ব ১০). শেষে append আর pop() amortized O(1), কিন্তু pop(0) প্রথম ঘর খালি করে বাকি সব উপাদানকে এক ঘর বাঁয়ে সরায় — ঠিক অংশ ২-এর ধাপ ৬. n উপাদানের list-এ খরচ Θ(n). পুরো list এভাবে খালি করলে মোট প্রায় n²/2 টি সরানো: n = 10⁵ হলে প্রায় ৫০০ কোটি পয়েন্টার-কপি। BFS-এ queue.pop(0) লিখে কনটেস্টে Time Limit Exceeded পাওয়া খুব পরিচিত অভিজ্ঞতা। একই কারণে list.insert(0, x)-ও Θ(n).

from collections import deque

q = deque()
q.append(1); q.append(2); q.append(3)     # enqueue: O(1)
print(q.popleft())                         # dequeue: O(1) -> 1
q.appendleft(0)                            # deque: push at the front, O(1)
print(list(q))                             # [0, 2, 3]

last3 = deque(maxlen=3)                    # fixed-size ring: old items fall off
for x in range(1, 6):
    last3.append(x)
print(list(last3))                         # [3, 4, 5]

collections.deque ভেতরে ছোট ছোট ব্লকের একটি doubly linked list, তাই দুই প্রান্তেই O(1). maxlen দিলে এটি নির্দিষ্ট মাপের ring buffer — “শেষ ১০০টি লগ লাইন” বা “শেষ ৫ মিনিটের রিডিং” রাখার সহজ উপায়। তবে মাঝখানের d[i] O(n), তাই ঘন ঘন index দরকার হলে list-ই ভালো। একাধিক thread-এর মধ্যে কাজ ভাগাভাগির জন্য আছে queue.Queue — অংশ ৭ দেখুন।

৭ · Queue কোথায় কাজ করে — BFS থেকে প্রিন্টার

“অপেক্ষা করো, পালা এলে কাজ হবে” — এই ধারণা কম্পিউটারের প্রায় সব স্তরে আছে। কয়েকটি গুরুত্বপূর্ণ উদাহরণ:

BFS-এর মূল লুপটি দেখতে কেমন, একটি ছোট আভাস (পুরো ব্যাখ্যা পর্ব ৪০-এ):

// dist[v] = number of edges from s to v (-1 = not reached yet)
queue<int> q;
dist[s] = 0; q.push(s);
while (!q.empty()) {
    int u = q.front(); q.pop();          // oldest discovered node first (FIFO)
    for (int v : adj[u])
        if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
}

এখানে queue-এর বদলে stack দিলে খোঁজার ক্রম বদলে যায় — এক দিকে গভীরে চলে যায় (DFS-এর মতো, পর্ব ৪১), আর dist আর সবচেয়ে ছোট পথ থাকে না। একটি ডেটা স্ট্রাকচার বদলালেই অ্যালগরিদমের অর্থ বদলে যায় — এটিই DSA-র সৌন্দর্য।

Priority queue — সারিতে যখন “জরুরি” আগে

হাসপাতালের জরুরি বিভাগে কিন্তু FIFO চলে না: হৃদরোগী পরে এলেও আগে দেখা হয়। এমন সারির নাম priority queue — প্রতিটি উপাদানের একটি অগ্রাধিকার থাকে, আর সবসময় সবচেয়ে বেশি অগ্রাধিকারেরটি আগে বের হয়। নাম “queue” হলেও ভেতরের কাঠামো সম্পূর্ণ আলাদা: সাধারণত একটি binary heap, যেখানে ঢোকানো আর বের করা O(log n). C++-এ std::priority_queue, Python-এ heapq. পর্ব ২৩-এ heap তৈরি থেকে শুরু করে পুরোটা দেখব; পর্ব ৪৩-এ Dijkstra-র অ্যালগরিদম এর ওপরেই দাঁড়িয়ে।

৮ · Monotonic deque — sliding window maximum O(n)-এ

এবার deque-এর সবচেয়ে চমকপ্রদ ব্যবহার। সমস্যা: n টি সংখ্যার একটি অ্যারে আর একটি সংখ্যা k. দৈর্ঘ্য k-এর প্রতিটি পরপর অংশের (sliding window) সর্বোচ্চ মান বের করুন। যেমন গত ৭ দিনের প্রতিটি ৭-দিনের জানালায় সর্বোচ্চ তাপমাত্রা, বা শেয়ারবাজারে প্রতিটি ৩০ মিনিটের সর্বোচ্চ দাম।

সরল সমাধান: প্রতিটি জানালায় k টি সংখ্যা দেখা — মোট O(n·k). n = 10⁶ আর k = 10⁵ হলে প্রায় 10¹¹ তুলনা, কয়েক মিনিটের কাজ। আমরা চাই O(n), অর্থাৎ k যত বড়ই হোক।

অ্যালগরিদম, প্রতিটি নতুন index i-এর জন্য তিনটি কাজ (deque-এ মান নয়, index রাখি — যাতে বোঝা যায় কে জানালা থেকে বেরিয়ে গেছে):

1. মেয়াদ শেষ: সামনের index যদি ≤ i − k হয়, সেটি জানালার বাইরে — pop_front.
2. দুর্বলদের বিদায়: পেছনের index-এর মান যতক্ষণ ≤ a[i], pop_back — এরা আর কখনো সর্বোচ্চ হবে না।
3. যোগ: i-কে পেছনে push_back. জানালা পূর্ণ হলে (i ≥ k − 1) উত্তর = a[সামনের index].

a = [5, 3, 4, 1, 2, 6, 2, 1, 0], k = 3-এর ওপর ধাপে ধাপে দেখুন। ওপরের সারি index, “win” লাইনের = চিহ্ন বর্তমান জানালা, “dq” লাইনের * চিহ্ন deque-এ থাকা index:

শুদ্ধতা। প্রতিটি ধাপের শেষে দুটি invariant সত্য: (ক) deque-এ শুধু বর্তমান জানালার index, বাঁ থেকে ডানে বাড়তে থাকা ক্রমে, আর তাদের মান কঠোরভাবে কমতে থাকা ক্রমে; (খ) জানালার যে index deque-এ নেই, তাকে বাদ দিয়েছে তার পরের কোনো index j, যার মান অন্তত সমান — আর j এখনো জানালায় (j পরে এসেছে, তাই পরে বেরোবে)। (খ) থেকে, জানালার সর্বোচ্চ মানের অন্তত একটি index deque-এ আছে; (ক) থেকে, deque-এর সবচেয়ে বড় মান সামনে। তাই সামনের মানই জানালার সর্বোচ্চ।

খরচ। একটি ধাপে while লুপ অনেকবার ঘুরতে পারে (ধাপ ৬-এ দুবার সরানো হলো), তাই এক ধাপের worst case O(k). কিন্তু পুরো রানে প্রতিটি index ঠিক একবার push হয় আর সর্বোচ্চ একবার pop — মোট deque-অপারেশন ≤ 2n. তাই মোট সময় Θ(n), k-এর ওপর নির্ভর করে না। জায়গা O(k) (deque-এ কখনো k-এর বেশি index থাকে না), আর উত্তরের জন্য n − k + 1. এটি অংশ ৫-এর মতোই amortized যুক্তি।

#include <deque>
#include <iostream>
#include <vector>
using namespace std;

template <class C> void put(const C& c) {          // prints like a Python list
    cout << '[';
    for (bool first = true; auto x : c) { cout << (first ? "" : ", ") << x; first = false; }
    cout << ']';
}

void window_max(const vector<int>& a, int k) {
    deque<int> dq;               // indices; their values decrease front to back
    vector<int> res;
    int pops = 0;
    for (int i = 0; i < (int)a.size(); ++i) {
        if (!dq.empty() && dq.front() <= i - k) { dq.pop_front(); ++pops; }  // slid out
        while (!dq.empty() && a[dq.back()] <= a[i]) { dq.pop_back(); ++pops; }
        dq.push_back(i);
        if (i >= k - 1) {
            res.push_back(a[dq.front()]);
            cout << "i=" << i << " window=";
            put(vector<int>(a.begin() + i - k + 1, a.begin() + i + 1));
            cout << " deque(idx)="; put(dq);
            cout << " max=" << a[dq.front()] << '\n';
        }
    }
    cout << "answer: "; put(res); cout << '\n';
    cout << "pushes=" << a.size() << " pops=" << pops
         << " (each index enters and leaves at most once)\n";
}

int main() { window_max({5, 3, 4, 1, 2, 6, 2, 1, 0}, 3); }

i=2 window=[5, 3, 4] deque(idx)=[0, 2] max=5
i=3 window=[3, 4, 1] deque(idx)=[2, 3] max=4
i=4 window=[4, 1, 2] deque(idx)=[2, 4] max=4
i=5 window=[1, 2, 6] deque(idx)=[5] max=6
i=6 window=[2, 6, 2] deque(idx)=[5, 6] max=6
i=7 window=[6, 2, 1] deque(idx)=[5, 6, 7] max=6
i=8 window=[2, 1, 0] deque(idx)=[6, 7, 8] max=2
answer: [5, 4, 4, 6, 6, 6, 2]
pushes=9 pops=6 (each index enters and leaves at most once)

from collections import deque

def window_max(a, k):
    dq = deque()                 # indices; their values decrease front to back
    res, pops = [], 0
    for i, x in enumerate(a):
        if dq and dq[0] <= i - k:      # front index slid out of the window
            dq.popleft(); pops += 1
        while dq and a[dq[-1]] <= x:   # smaller ones can never be a max again
            dq.pop(); pops += 1
        dq.append(i)
        if i >= k - 1:
            res.append(a[dq[0]])
            print(f"i={i} window={a[i-k+1:i+1]} deque(idx)={list(dq)} max={a[dq[0]]}")
    print(f"answer: {res}")
    print(f"pushes={len(a)} pops={pops} (each index enters and leaves at most once)")

window_max([5, 3, 4, 1, 2, 6, 2, 1, 0], 3)

i=2 window=[5, 3, 4] deque(idx)=[0, 2] max=5
i=3 window=[3, 4, 1] deque(idx)=[2, 3] max=4
i=4 window=[4, 1, 2] deque(idx)=[2, 4] max=4
i=5 window=[1, 2, 6] deque(idx)=[5] max=6
i=6 window=[2, 6, 2] deque(idx)=[5, 6] max=6
i=7 window=[6, 2, 1] deque(idx)=[5, 6, 7] max=6
i=8 window=[2, 1, 0] deque(idx)=[6, 7, 8] max=2
answer: [5, 4, 4, 6, 6, 6, 2]
pushes=9 pops=6 (each index enters and leaves at most once)

এই ধাঁচটি অনেক রূপে আসে: sliding window minimum, “প্রতিটি দিনের পরে প্রথম বেশি তাপমাত্রার দিন” (monotonic stack), আর dynamic programming-এ “গত k ঘরের মধ্যে সেরা মান” দরকার হলে প্রতিটি ঘর O(1)-এ। পর্ব ১৬-এ two pointer আর sliding window-এর সাধারণ কৌশল দেখবেন; সেখানেও এই deque বারবার ফিরে আসবে।

৯ · কোন queue কখন — এক নজরে তুলনা

১০ · AI-এর যুগে queue আর deque — ছোট ভুল, বড় ফল

“একটি circular queue লিখে দাও” বা “sliding window maximum সমাধান করো” — AI কয়েক সেকেন্ডে পরিপাটি কোড দেয়, আর ছোট উদাহরণে তা প্রায়ই চলে। কিন্তু queue-এর ভুলগুলো থাকে কিনারায়: ঠিক ভর্তি হওয়ার মুহূর্তে, শেষ উপাদান বের হওয়ার মুহূর্তে, wrap-around-এর ঘরে। আর complexity-র দাবিতে — বিশেষ করে Python-এ।

Queue-তে AI সাধারণত যেসব ভুল করে

Queue-কোড যাচাইয়ের চেকলিস্ট

• খালি queue-তে dequeue/front আর ভর্তি queue-তে enqueue — দুটি edge case-ই চালিয়ে দেখেছি
• cap = 1 আর cap = 2-এ head ও tail অন্তত দুবার wrap-around করিয়ে হাতে dry run করেছি
• শেষ উপাদান বের হওয়ার পর আবার enqueue করে দেখেছি সব pointer/index ঠিক আছে
• Python-এ কোথাও pop(0) বা insert(0, x) নেই, queue মানে deque
• অপারেশন গুনে amortized দাবি মিলিয়েছি (দুটি stack-এ ≤ 4n, monotonic deque-এ ≤ 2n)
• সরল O(n·k) brute force-এর সাথে হাজারখানেক এলোমেলো ছোট ইনপুটে stress testing করেছি — পুনরাবৃত্ত মান আর k = 1, k = n সহ