17.4 งานที่ใช้ queue และ deque

queue ใช้เมื่องานต้องทำตามลำดับที่มาถึง ใครมาก่อนได้ก่อน หน้านี้มีสองงาน งานแรกคือจำลองคิวที่แต่ละคนได้ใช้ของทีละนิดแล้ววนกลับไปต่อท้าย เรียกว่า round robin งานที่สองใช้ deque หาค่ามากสุดของทุกช่วงยาว k ติดกัน ซึ่งเป็นเทคนิคคู่แฝดของ monotonic stack ในหน้าที่แล้ว และเปลี่ยนลูปซ้อนที่ไม่ทันเวลาให้เหลือรอบเดียวเหมือนกัน

ผลัดกันเล่นทีละรอบ

ร้านเกมมีเครื่องเล่นเครื่องเดียว เพื่อน N คนมาต่อแถวตามลำดับ คนที่ i อยากเล่นรวม t_i นาที แต่ร้านให้เล่นได้ครั้งละไม่เกิน Q นาที ใครเล่นไม่ครบต้องกลับไปต่อท้ายแถว เครื่องว่างเมื่อไรคนหัวแถวได้เล่นต่อทันที ให้บอกว่าใครเล่นครบตอนนาทีที่เท่าไร เรียงตามลำดับที่เล่นครบ

การแบ่งเวลาให้ทุกคนได้ใช้ทีละช่วงสั้นๆ วนไปเรื่อยๆ แบบนี้ชื่อว่า round robin ระบบปฏิบัติการใช้วิธีนี้แบ่งเวลาของซีพียูให้โปรแกรมหลายตัวที่เปิดพร้อมกัน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, quantum;
    cin >> n >> quantum;
    queue<pair<string, int>> line;
    for (int i = 0; i < n; i++) {
        string name;
        int need;
        cin >> name >> need;
        line.push({name, need});
    }
    long long minute = 0;
    while (!line.empty()) {
        auto player = line.front();
        line.pop();
        int play = min(player.second, quantum); // (1)!
        minute += play;
        player.second -= play;
        if (player.second > 0) {
            line.push(player); // (2)!
        } else {
            cout << player.first << " finishes at minute " << minute << '\n';
        }
    }
    return 0;
}

1. เล่นเต็มรอบ Q นาที หรือเท่าที่เหลือถ้าเหลือน้อยกว่า
2. ยังไม่ครบ กลับไปต่อท้ายพร้อมเวลาที่เหลือ งานแบบนี้คือเหตุผลที่ต้องมี queue ลูปธรรมดาที่อ่านไปทีละคนทำไม่ได้

4 3
Ploy 5
Krit 2
Mint 7
Tan 3

Krit finishes at minute 5
Tan finishes at minute 11
Ploy finishes at minute 13
Mint finishes at minute 17

ทุกรอบของ while ทำงานกับ queue ไม่กี่คำสั่ง ซึ่งเป็น O(1) ทั้งหมด เวลารวมจึงขึ้นกับจำนวนรอบที่มีคนได้เล่น ถ้า Q เป็น 1 และทุกคนอยากเล่นพันล้านนาที จำนวนรอบจะมากเกินไป ก่อนเขียนให้คำนวณจากขอบเขตโจทย์ว่าจะวนกี่รอบเสมอ ตัวแปร minute เป็น long long ด้วยเหตุผลเดียวกัน เวลารวมของทุกคนอาจเกิน int

ค่ามากสุดในทุกช่วงยาว k

เครื่องวัดฝุ่น PM2.5 บันทึกค่าทุกชั่วโมง รวม N ชั่วโมง ป้ายเตือนแสดงค่าสูงสุดของ k ชั่วโมงล่าสุด ให้หาค่าสูงสุดของทุกช่วง k ชั่วโมงติดกัน ตั้งแต่ช่วงชั่วโมงที่ 0 ถึง k - 1 ไปจนถึงช่วงที่จบที่ชั่วโมงสุดท้าย ได้ทั้งหมด N - k + 1 ค่า ช่วงที่เลื่อนไปทีละช่องแบบนี้เรียกว่า sliding window (หน้าต่างเลื่อน)

วิธีตรงไปตรงมาคือ ทุกช่วงไล่หาค่ามากสุดใหม่

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> pm(n);
    for (int i = 0; i < n; i++) {
        cin >> pm[i];
    }
    for (int start = 0; start + k <= n; start++) {
        int best = pm[start];
        for (int j = start + 1; j < start + k; j++) {
            best = max(best, pm[j]);
        }
        cout << best << (start + k < n ? ' ' : '\n');
    }
    return 0;
}

10 3
35 42 38 51 47 40 33 36 58 44

42 51 51 51 47 40 58 58

มี N - k + 1 ช่วง แต่ละช่วงดู k ตัว ถ้า N เป็นแสนและ k เป็นห้าหมื่น ก็ราว 2.5 × 10⁹ ครั้ง ไม่ทัน

เก็บเฉพาะตัวที่ยังมีโอกาสเป็นค่ามากสุด

สังเกตว่าถ้าชั่วโมงที่ j มาก่อนชั่วโมงที่ i และค่าของ j ไม่มากกว่าค่าของ i ชั่วโมง j จะไม่มีวันเป็นค่ามากสุดของช่วงไหนอีกเลย เพราะทุกช่วงต่อจากนี้ที่มี j ก็มี i อยู่ด้วย และ i ยังอยู่ในหน้าต่างได้นานกว่าเพราะมาทีหลัง ทิ้ง j ได้ทันที

ถ้าทิ้งแบบนี้ไปเรื่อยๆ ของที่เหลือเก็บไว้จะมีค่าลดลงจากเก่าไปใหม่เสมอ ตัวเก่าสุดจึงเป็นค่ามากสุดของหน้าต่าง เก็บ เลขชั่วโมง ไว้ใน deque แล้วทำสามอย่างทุกชั่วโมงใหม่ i

1. ท้าย deque ทิ้งทุกตัวที่ค่าไม่มากกว่า pm[i] แล้ว push_back i
2. หัว deque ถ้าเป็นชั่วโมงที่หลุดออกจากหน้าต่างแล้ว คือไม่เกิน i - k ให้ pop_front
3. ถ้า i ถึง k - 1 แล้ว หน้าต่างครบ k ชั่วโมง คำตอบคือค่าของหัว deque

งานนี้ต้องใช้ทั้งสองหัว ท้ายใช้ทิ้งตัวที่หมดโอกาส หัวใช้ทิ้งตัวที่หมดเวลา stack หรือ queue อย่างเดียวจึงไม่พอ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> pm(n);
    for (int i = 0; i < n; i++) {
        cin >> pm[i];
    }
    deque<int> window; // (1)!
    for (int i = 0; i < n; i++) {
        while (!window.empty() && pm[window.back()] <= pm[i]) { // (2)!
            window.pop_back();
        }
        window.push_back(i);
        if (window.front() <= i - k) { // (3)!
            window.pop_front();
        }
        if (i >= k - 1) {
            cout << pm[window.front()] << (i + 1 < n ? ' ' : '\n');
        }
    }
    return 0;
}

1. เก็บเลขชั่วโมง เพราะต้องรู้ว่าตัวหัวหลุดออกจากหน้าต่างหรือยัง ถ้าเก็บแต่ค่า PM2.5 จะไม่รู้เลยว่ามันมาจากชั่วโมงไหน
2. ตัวที่ค่าเท่ากันก็ทิ้งได้ เพราะตัวใหม่อยู่ได้นานกว่าและค่าเท่ากัน ใช้ < ก็ได้คำตอบถูกเหมือนกัน แต่ deque จะยาวกว่า
3. หน้าต่างที่จบที่ i คือชั่วโมง i - k + 1 ถึง i ชั่วโมงที่ไม่เกิน i - k จึงหลุดแล้ว แต่ละรอบหลุดได้อย่างมากหนึ่งตัว เพราะหน้าต่างเลื่อนไปทีละช่อง if จึงพอ ไม่ต้องใช้ while

10 3
35 42 38 51 47 40 33 36 58 44

42 51 51 51 47 40 58 58

ไล่ดูทีละชั่วโมง ตารางเขียนค่า PM2.5 ใน deque ให้อ่านง่าย ซ้ายคือหัว ของจริงคือเลขชั่วโมง

ทุกชั่วโมงถูก push_back ครั้งเดียว และออกไม่เกินครั้งเดียว จะออกทางท้ายหรือทางหัวก็ตาม งานรวมจึงไม่เกิน 2N ครั้ง เป็น O(N) ไม่ขึ้นกับ k เลย ส่วนวิธีแรกเป็น O(N × k) เหตุผลเดียวกับ monotonic stack ในหน้า 17.3 ทุกประการ deque แบบนี้จึงมีชื่อว่า monotonic deque

เร็วขึ้นแค่ไหน

โปรแกรมวัดสร้างค่าสุ่มด้วย rand() แล้วรันทั้งสองวิธี ตรวจว่าได้คำตอบตรงกัน

#include <bits/stdc++.h>
using namespace std;

int pm[200000];
int answer_slow[200000];
int answer_fast[200000];

int main()
{
    int n, k;
    cin >> n >> k;
    srand(2569);
    for (int i = 0; i < n; i++) {
        pm[i] = rand() % 500;
    }

    clock_t start = clock();
    for (int i = 0; i + k <= n; i++) {
        int best = pm[i];
        for (int j = i + 1; j < i + k; j++) {
            best = max(best, pm[j]);
        }
        answer_slow[i] = best;
    }
    clock_t middle = clock();
    deque<int> window;
    for (int i = 0; i < n; i++) {
        while (!window.empty() && pm[window.back()] <= pm[i]) {
            window.pop_back();
        }
        window.push_back(i);
        if (window.front() <= i - k) {
            window.pop_front();
        }
        if (i >= k - 1) {
            answer_fast[i - k + 1] = pm[window.front()];
        }
    }
    clock_t end = clock();

    int same = 1;
    for (int i = 0; i + k <= n; i++) {
        if (answer_slow[i] != answer_fast[i]) {
            same = 0;
        }
    }
    cout << "same answers: " << same << '\n';
    cout << fixed << setprecision(3);
    cout << "nested loops: " << (double)(middle - start) / CLOCKS_PER_SEC << " seconds\n";
    cout << "deque: " << (double)(end - middle) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

วัดบนเครื่องเดียวกับหน้า 17.1 ที่ N = 100,000 ทุกครั้งได้ same answers: 1 รันแบบละ 5 ครั้ง ตารางเป็นค่ากลาง

k ใหญ่ขึ้น ลูปซ้อนช้าลงตาม แต่ deque ใช้เวลาเท่าเดิม เพราะงานของมันไม่ขึ้นกับ k โจทย์ที่ให้ k เล็กเสมอ วิธีแรกอาจผ่าน แต่ถ้าขอบเขตบอกว่า k ใหญ่ได้เท่า N ต้องใช้ deque

ลองทำให้พัง

แบบที่ 1 ลืมทิ้งตัวที่หมดเวลา

ในโปรแกรม window-deque ตัด if ที่ pop_front ออก

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> pm(n);
    for (int i = 0; i < n; i++) {
        cin >> pm[i];
    }
    deque<int> window;
    for (int i = 0; i < n; i++) {
        while (!window.empty() && pm[window.back()] <= pm[i]) {
            window.pop_back();
        }
        window.push_back(i);
        if (i >= k - 1) {
            cout << pm[window.front()] << (i + 1 < n ? ' ' : '\n');
        }
    }
    return 0;
}

10 3
35 42 38 51 47 40 33 36 58 44

42 51 51 51 51 51 58 58

ช่วงที่ 5 กับ 6 ได้ 51 ซึ่งหลุดหน้าต่างไปแล้ว โปรแกรมนี้กลายเป็นหาค่ามากสุดตั้งแต่ต้นจนถึงตอนนี้ ไม่ใช่ใน k ชั่วโมงล่าสุด ข้อมูลที่ค่าเพิ่มขึ้นตลอดจะได้คำตอบถูกทุกช่วงเพราะท้ายดันหัวออกเองหมด ทดสอบด้วยข้อมูลที่ค่าลดลงด้วยเสมอ

แบบที่ 2 ทิ้งหัวช้าไปหนึ่งชั่วโมง

เขียนเงื่อนไขเป็น window.front() < i - k ซึ่งดูเผินๆ ก็ถูก กับข้อมูลชุดเดิมได้

42 51 51 51 51 47 58 58

ช่วงที่ 5 กับ 6 ได้ 51 กับ 47 ที่ถูกคือ 47 กับ 40 เพราะชั่วโมงที่หลุดไปแล้วยังค้างอยู่ในหัวอีกหนึ่งรอบ หน้าต่างจริงของโปรแกรมนี้ยาว k + 1 ชั่วโมง เขียนช่วงของหน้าต่างออกมาให้ชัดก่อนว่าคือ i - k + 1 ถึง i แล้วค่อยหาว่าตัวไหนหลุด อย่าเดาเครื่องหมาย

สรุป

• queue ใช้จำลองงานที่ทำตามลำดับที่มาถึง งานที่ทำไม่เสร็จต่อท้ายใหม่ได้ เช่น round robin
• คำนวณจำนวนรอบของการจำลองจากขอบเขตโจทย์ก่อนเขียน และใช้ long long กับเวลารวม
• BFS ในบทที่ 27 ใช้ queue สำรวจทีละชั้น
• ค่ามากสุดของทุกหน้าต่างยาว k ใช้ monotonic deque ท้ายทิ้งตัวที่หมดโอกาส หัวทิ้งตัวที่หมดเวลา เก็บ index
• ทุกตัวเข้าครั้งเดียวออกไม่เกินครั้งเดียว งานรวม O(N) ไม่ขึ้นกับ k

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด