[0]zero-index clytie0x/zero-index

17.3 งานที่ใช้ stack

หน้า 14.4 สรุปไว้ว่า stack ใช้เมื่อต้องจับคู่กับ "ตัวล่าสุดที่ยังค้างอยู่" หรือเมื่อต้องย้อนลำดับ หน้านี้เขียนงานเดิมสองงานใหม่ด้วย stack ของ STL คือตรวจวงเล็บกับคำนวณ postfix เพิ่มงานย้อนกลับแบบปุ่ม back ของเว็บเบราว์เซอร์ และปิดท้ายด้วยเทคนิคที่ใช้บ่อยมากในโจทย์แข่งขัน คือ monotonic stack ที่เปลี่ยนวิธีลูปซ้อนซึ่งไม่ทันเวลา ให้เหลือการเดินรอบเดียว

ตรวจวงเล็บ

กฎเดิมจากหน้า 14.4 เจอวงเล็บเปิด push เจอวงเล็บปิดต้องคู่กับตัวบนสุด และจบแล้ว stack ต้องว่าง

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

char opening_of(char c)
{
    if (c == ')') {
        return '(';
    } else if (c == ']') {
        return '[';
    }
    return '{';
}

bool is_balanced(string s)
{
    stack<char> open; // (1)!
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            open.push(c);
        } else {
            if (open.empty() || open.top() != opening_of(c)) { // (2)!
                return false;
            }
            open.pop();
        }
    }
    return open.empty();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    while (cin >> s) {
        if (is_balanced(s)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}
  1. stack ประกาศในฟังก์ชัน จึงเกิดใหม่ว่างๆ ทุกครั้งที่เรียก บั๊ก "ลืมเริ่ม stack ว่างใหม่" ในหน้า 14.4 จึงเกิดไม่ได้อีก
  2. || หยุดตรวจทันทีที่ด้านซ้ายเป็นจริงตามหน้า 3.3 ถ้า stack ว่างจะไม่ไปเรียก open.top() เลย ลำดับนี้สลับไม่ได้
{[()()]}
([)]
(()
())
)(

YES
NO
NO
NO
NO

ผลเหมือนหน้า 14.4 ทั้งห้าบรรทัด โปรแกรมบทที่ 14 ยาว 48 บรรทัด อันนี้ 41 บรรทัด สั้นลงไม่มาก เพราะส่วนที่ยาวคือกฎของวงเล็บซึ่งต้องเขียนเองอยู่ดี สิ่งที่ได้จริงคือไม่ต้องคิดว่าอาเรย์ต้องมีกี่ช่อง และ stack ว่างเองทุกครั้งที่เริ่มสูตรใหม่

ย้อนกลับด้วยปุ่ม back

เว็บเบราว์เซอร์จำหน้าที่เคยเปิด กด back แล้วกลับไปหน้าล่าสุดก่อนหน้านี้ กด back อีกครั้งก็ถอยไปอีกหน้า หน้าที่ต้องกลับไปคือหน้าที่เข้ามาล่าสุด จึงเป็นงานของ stack ทุกครั้งที่เปิดหน้าใหม่ ให้ push หน้าปัจจุบันเก็บไว้ก่อนย้าย พอกด back ก็ pop ออกมาเป็นหน้าปัจจุบัน

โปรแกรมเริ่มที่หน้า home คำสั่ง VISIT x คือเปิดหน้า x และ BACK คือกดปุ่ม back หลังทุกคำสั่งให้พิมพ์ว่าอยู่หน้าไหน

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

int main()
{
    int q;
    cin >> q;
    stack<string> history;
    string current = "home";
    for (int i = 0; i < q; i++) {
        string command;
        cin >> command;
        if (command == "VISIT") {
            string page;
            cin >> page;
            history.push(current); // (1)!
            current = page;
            cout << "at " << current << '\n';
        } else if (history.empty()) {
            cout << "no page to go back\n";
        } else {
            current = history.top(); // (2)!
            history.pop();
            cout << "at " << current << '\n';
        }
    }
    return 0;
}
  1. เก็บหน้าที่กำลังจะจากไป ไม่ใช่หน้าที่จะไป
  2. หน้าที่จากมาล่าสุดอยู่บนสุดพอดี
9
VISIT news
VISIT sport
VISIT football
BACK
BACK
VISIT weather
BACK
BACK
BACK

at news
at sport
at football
at sport
at news
at weather
at news
at home
no page to go back

ดูบรรทัดที่ 6 ถึง 7 ของผลลัพธ์ ตอนเปิด weather หน้าปัจจุบันคือ news จึงถูก push ไว้ back จาก weather จึงกลับไป news ไม่ใช่ sport ซึ่งตรงกับเบราว์เซอร์จริง

ปุ่ม undo ของโปรแกรมพิมพ์งานหรือโปรแกรมวาดรูปใช้หลักเดียวกัน ทุกครั้งที่ผู้ใช้แก้อะไร ให้ push สิ่งที่ต้องรู้เพื่อย้อนการแก้นั้น กด undo คือ pop ตัวบนสุดแล้วย้อนมัน ส่วนปุ่ม forward หรือ redo ต้องใช้ stack ตัวที่สองเก็บสิ่งที่เพิ่งย้อนไป undo อยู่ในแบบฝึกหัดข้อ 4 และปุ่ม forward อยู่ในข้อ 5 ส่วน redo ไม่มีในแบบฝึกหัด แต่เขียนด้วยหลักเดียวกับ forward ทุกอย่าง

คำนวณ postfix

กฎเดิมจากหน้า 14.4 เจอตัวเลข push เจอเครื่องหมาย pop สองครั้ง ตัวแรกที่ออกมาคือตัวขวา คำนวณแล้ว push ผลกลับ

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    stack<long long> values;
    string token;
    while (cin >> token) {
        if (isdigit(token[0])) {
            long long number = 0;
            for (char c : token) {
                number = number * 10 + (c - '0');
            }
            values.push(number);
        } else {
            long long right = values.top(); // (1)!
            values.pop();
            long long left = values.top();
            values.pop();
            if (token == "+") { // (2)!
                values.push(left + right);
            } else if (token == "-") {
                values.push(left - right);
            } else if (token == "*") {
                values.push(left * right);
            } else {
                values.push(left / right);
            }
        }
    }
    cout << values.top() << '\n';
    return 0;
}
  1. เพราะ pop() ไม่คืนค่า หนึ่งครั้งของ pop() ในหน้า 14.4 จึงกลายเป็นสองบรรทัด ดูก่อนแล้วค่อยทิ้ง
  2. string เทียบกับข้อความด้วย == ได้ตรงๆ ไม่ต้องดูแค่ตัวแรกแบบภาษา C
8 2 5 * + 1 3 2 * + 4 - /

6

โปรแกรมบทที่ 14 ยาว 44 บรรทัด อันนี้ 33 บรรทัด และไม่มีอาเรย์พันช่องที่จะล้นเมื่อนิพจน์ยาว กฎเรื่องตัวซ้ายตัวขวาและการเช็กว่างก่อน pop ยังเหมือนเดิมทุกอย่าง

วันแรกที่ร้อนกว่า

สถานีอากาศบันทึกอุณหภูมิสูงสุดของ N วันติดกัน สำหรับแต่ละวัน อยากรู้ว่าวันแรกหลังจากนั้นที่ร้อนกว่าวันนี้อย่างเคร่งครัดร้อนกี่องศา ถ้าไม่มีวันไหนร้อนกว่าเลยให้ตอบ -1 โจทย์แบบนี้มีชื่อเรียกว่า next greater element (ตัวถัดไปที่มากกว่า) และมีอีกหลายแบบ เช่น ตัวก่อนหน้าที่มากกว่า หรือตัวถัดไปที่น้อยกว่า

วิธีตรงไปตรงมาคือ ทุกวันเดินไปทางขวาจนเจอวันที่ร้อนกว่า

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> temp(n), answer(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> temp[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (temp[j] > temp[i]) {
                answer[i] = temp[j];
                break;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << answer[i] << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

8
31 29 30 34 33 33 35 32

34 30 34 35 35 35 -1 -1

บรรทัดสุดท้ายพิมพ์ช่องว่างหลังทุกตัวยกเว้นตัวสุดท้าย ซึ่งพิมพ์ขึ้นบรรทัดใหม่แทน จะได้ไม่มีช่องว่างเกินท้ายบรรทัด

ถ้าอุณหภูมิลดลงทุกวัน ไม่มีวันไหนเจอคำตอบเลย วันแรกต้องเดินดูอีก n - 1 วัน วันที่สองอีก n - 2 วัน รวมราว n2 / 2 ครั้ง เมื่อ n เป็นแสน ก็คือ 5 × 109 ครั้ง ไม่ทันแน่นอนตามหลักในหน้า 4.5

กลับมุมมอง ให้วันที่ยังไม่มีคำตอบรอ

แทนที่แต่ละวันจะเดินไปหาคำตอบเอง ให้เดินจากซ้ายไปขวารอบเดียว แล้วเก็บวันที่ยังรอคำตอบอยู่ไว้ใน stack พอเจอวันใหม่ วันที่รออยู่ซึ่งเย็นกว่าวันใหม่ ได้คำตอบเป็นวันใหม่นี้ทั้งหมด

สิ่งที่ทำให้วิธีนี้เร็วคือข้อสังเกตนี้ อุณหภูมิของวันที่รออยู่ ไล่จากก้น stack ขึ้นมา ไม่เคยเพิ่มขึ้น เพราะถ้ามีวันที่ร้อนกว่ามาทีหลัง วันที่เย็นกว่าที่รออยู่ก่อนก็ได้คำตอบแล้วถูก pop ออกไปตั้งแต่ตอนนั้น ตัวบนสุดจึงเป็นวันที่เย็นที่สุดในบรรดาวันที่รอเสมอ ถ้าตัวบนสุดไม่เย็นกว่าวันใหม่ ตัวที่อยู่ข้างล่างก็ไม่เย็นกว่าแน่นอน หยุดดูได้ทันที stack ที่ของข้างในเรียงทางเดียวตลอดแบบนี้เรียกว่า monotonic stack (monotonic แปลว่าเปลี่ยนไปทางเดียว)

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> temp(n), answer(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> temp[i];
    }
    stack<int> waiting; // (1)!
    for (int i = 0; i < n; i++) {
        while (!waiting.empty() && temp[waiting.top()] < temp[i]) { // (2)!
            answer[waiting.top()] = temp[i];
            waiting.pop();
        }
        waiting.push(i);
    }
    for (int i = 0; i < n; i++) {
        cout << answer[i] << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}
  1. เก็บเลขวัน ไม่ใช่อุณหภูมิ เพราะตอนได้คำตอบต้องรู้ว่าจะเขียนลง answer ช่องไหน อุณหภูมิหาได้จาก temp[เลขวัน] อยู่แล้ว
  2. pop ไปเรื่อยๆ ตราบใดที่ตัวบนสุดเย็นกว่าวันใหม่ วันที่เหลือใน stack ตอนจบไม่มีวันที่ร้อนกว่า คำตอบจึงเป็น -1 ตามค่าเริ่มต้น
8
31 29 30 34 33 33 35 32

34 30 34 35 35 35 -1 -1

ไล่ดูทีละวัน ตาราง stack เขียนเป็นอุณหภูมิของวันที่รออยู่ให้อ่านง่าย ซ้ายคือก้น ของจริงใน stack คือเลขวัน

วันอุณหภูมิpop และได้คำตอบstack หลัง push
031ไม่มี stack ว่าง31
129ไม่มี 31 ไม่เย็นกว่า31 29
230วัน 1 ได้ 3031 30
334วัน 2 ได้ 34 วัน 0 ได้ 3434
433ไม่มี34 33
533ไม่มี 33 ไม่เย็นกว่า 3334 33 33
635วัน 5 วัน 4 และวัน 3 ได้ 3535
732ไม่มี35 32

คอลัมน์สุดท้ายไม่เคยมีตัวเลขที่เพิ่มขึ้นจากซ้ายไปขวาเลย ตรงกับข้อสังเกตข้างบน

ลูป while ข้างในไม่ทำให้ช้า

ดูเผินๆ โปรแกรมมีลูปซ้อนเหมือนวิธีแรก แต่ให้นับจากอีกมุมหนึ่ง ทุกวันถูก push ครั้งเดียว และถูก pop ไม่เกินครั้งเดียว เพราะ pop แล้วไม่เคยกลับเข้าไปอีก ทั้งโปรแกรมจึงมี push n ครั้ง และ pop ไม่เกิน n ครั้ง รวมไม่เกิน 2n ครั้ง ถึงบางรอบของ for จะ pop หลายตัว อย่างวันที่ 6 ที่ pop สามตัว รอบอื่นก็ pop น้อยลงชดเชยกัน งานรวมจึงโตตาม n ตรงๆ เรียกว่า O(n) ส่วนวิธีแรกเป็น O(n2)

วัดด้วยโปรแกรมที่สร้างข้อมูลเอง มีสองแบบ แบบ random ใช้ rand() แบบหน้า 13.3 และแบบ falling ที่อุณหภูมิลดลงทุกวัน ซึ่งเป็นกรณีแย่ที่สุดของวิธีแรก ทั้งสองวิธีอยู่ในโปรแกรมเดียวกัน และตรวจว่าได้คำตอบตรงกัน

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

int temp[200000];
int answer_slow[200000];
int answer_fast[200000];

int main()
{
    int n;
    string pattern;
    cin >> n >> pattern;
    srand(2569);
    for (int i = 0; i < n; i++) {
        if (pattern == "falling") {
            temp[i] = n - i;
        } else {
            temp[i] = rand() % 1000;
        }
    }

    clock_t start = clock();
    for (int i = 0; i < n; i++) {
        answer_slow[i] = -1;
        for (int j = i + 1; j < n; j++) {
            if (temp[j] > temp[i]) {
                answer_slow[i] = temp[j];
                break;
            }
        }
    }
    clock_t middle = clock();
    stack<int> waiting;
    for (int i = 0; i < n; i++) {
        answer_fast[i] = -1;
        while (!waiting.empty() && temp[waiting.top()] < temp[i]) {
            answer_fast[waiting.top()] = temp[i];
            waiting.pop();
        }
        waiting.push(i);
    }
    clock_t end = clock();

    int same = 1;
    for (int i = 0; i < 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 << "stack: " << (double)(end - middle) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

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

ข้อมูลnลูปซ้อน แบบ Code::Blocksลูปซ้อน แบบ -O2stack แบบ Code::Blocksstack แบบ -O2
random100,0000.004 วินาที0.002 วินาที0.005 วินาที0.001 วินาที
falling10,0000.028 วินาที0.012 วินาที0.000 วินาที0.000 วินาที
falling100,0003.438 วินาที1.173 วินาที0.003 วินาที0.001 วินาที

แถวแรกน่าสนใจที่สุด ข้อมูลสุ่มทำให้ลูปซ้อนเร็วพอๆ กับ stack เพราะส่วนใหญ่เดินไม่กี่วันก็เจอวันที่ร้อนกว่า ถ้าน้องทดสอบด้วยข้อมูลสุ่มอย่างเดียว จะคิดว่าวิธีแรกผ่าน แต่ชุดทดสอบจริงมีกรณีแบบ falling เสมอ ลูปซ้อนโตตาม n กำลังสอง n เพิ่ม 10 เท่าใช้เวลาเพิ่มราว 100 เท่า เกิน 1 วินาทีแม้เปิด -O2 ส่วน stack ยังไม่ถึงหนึ่งในร้อยวินาที

ลองทำให้พัง

แบบที่ 1 ใช้ <= แทน <

ในโปรแกรม warmer-stack เปลี่ยนเงื่อนไขเป็น temp[waiting.top()] <= temp[i]

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> temp(n), answer(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> temp[i];
    }
    stack<int> waiting;
    for (int i = 0; i < n; i++) {
        while (!waiting.empty() && temp[waiting.top()] <= temp[i]) {
            answer[waiting.top()] = temp[i];
            waiting.pop();
        }
        waiting.push(i);
    }
    for (int i = 0; i < n; i++) {
        cout << answer[i] << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

8
31 29 30 34 33 33 35 32

34 30 34 35 33 35 -1 -1

วันที่ 4 ได้ 33 ซึ่งไม่ได้ร้อนกว่าตัวเอง เพราะพอเจอวันที่ 5 ที่ร้อนเท่ากัน เงื่อนไข <= ก็ pop วันที่ 4 ออกไปพร้อมคำตอบผิด ถ้าตัวอย่างในโจทย์ไม่มีค่าซ้ำ บั๊กนี้จะผ่านตัวอย่างแล้วไปตกชุดทดสอบที่ซ่อนไว้ ก่อนเขียนให้ถามตัวเองว่าโจทย์ต้องการ "มากกว่า" หรือ "มากกว่าหรือเท่ากับ" แล้วทดสอบด้วยค่าซ้ำเสมอ

แบบที่ 2 ลืมเช็กว่าง

ตัด !waiting.empty() && ออก เหลือ while (temp[waiting.top()] < temp[i]) คอมไพล์ผ่านโดยไม่มีคำเตือน แต่รันกับข้อมูลตัวอย่างแล้วไม่พิมพ์อะไรเลย Code::Blocks ขึ้นว่า

Process returned -1073741819 (0xC0000005)

วันแรก stack ยังว่าง waiting.top() จึงพังทันทีเหมือนแบบที่ 2 ของหน้า 17.1 ถ้าสลับเป็น temp[waiting.top()] < temp[i] && !waiting.empty() ก็พังเหมือนกัน เพราะ && ทำด้านซ้ายก่อน การเช็กว่างต้องอยู่ซ้ายสุดเสมอ

สรุป

  • stack ใช้กับงานที่ต้องจับคู่กับตัวล่าสุดที่ค้างอยู่ เช่น วงเล็บ และงานย้อนกลับ เช่น ปุ่ม back กับ undo
  • ประกาศ stack ในฟังก์ชันหรือในลูป จะได้ stack ว่างใหม่ทุกครั้งโดยไม่ต้องเริ่มเอง
  • monotonic stack หาตัวถัดไปที่มากกว่าของทุกตัวได้ในรอบเดียว เก็บ index ไม่ใช่ค่า
  • ทุกตัว push ครั้งเดียว pop ไม่เกินครั้งเดียว งานรวม O(n) ส่วนลูปซ้อนเป็น O(n2) และช้าจริงเฉพาะข้อมูลแบบที่แย่ที่สุด
  • ระวัง < กับ <= เมื่อมีค่าซ้ำ และเช็ก empty() ไว้ซ้ายสุดของเงื่อนไข