17.1 stack และ queue สำเร็จรูป

ในบทที่ 14 น้องเขียน stack กับ queue เองด้วยอาเรย์ ต้องเลือกขนาดอาเรย์ ต้องมีตัวแปร size หรือ head กับ tail และต้องเขียนฟังก์ชัน push pop ทุกครั้งที่เริ่มโจทย์ใหม่ C++ มีของพวกนี้ทำไว้ให้แล้วใน STL ชุดเดียวกับ vector ที่ใช้ในบทที่ 16 ของที่ใช้เก็บข้อมูลหลายตัวแบบนี้เรียกรวมว่า container (ภาชนะ) หน้านี้ใช้ container สองตัวแรก คือ stack กับ queue แล้วดูว่าโค้ดสั้นลงแค่ไหน และมีอะไรที่ยังต้องระวังเองเหมือนเดิม

stack

ประกาศ stack ด้วย stack<ชนิด> ชื่อ; เหมือนประกาศ vector ได้ stack ว่างที่ยังไม่มีของ โปรแกรมนี้ใช้ลำดับคำสั่งเดียวกับโปรแกรม plates ในหน้า 14.4 ทุกบรรทัด

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

int main()
{
    stack<int> plates; // (1)!
    plates.push(11);
    plates.push(12);
    plates.push(13);
    cout << "top = " << plates.top() << '\n';
    cout << "pop = " << plates.top() << '\n'; // (2)!
    plates.pop();
    cout << "pop = " << plates.top() << '\n';
    plates.pop();
    plates.push(14);
    cout << "size = " << plates.size() << '\n';
    while (!plates.empty()) { // (3)!
        cout << "pop = " << plates.top() << '\n';
        plates.pop();
    }
    return 0;
}

1. ไม่ต้องบอกขนาด stack ยืดออกเองตามจำนวนของที่ใส่ ของในวงเล็บ <> คือชนิดของที่เก็บ
2. pop() ของ C++ ไม่คืนค่า มันแค่ทิ้งตัวบนสุด ถ้าอยากรู้ว่าทิ้งอะไรไป ต้องดูด้วย top() ก่อนแล้วค่อย pop() เสมอ
3. empty() คืน true เมื่อไม่มีของเหลือ ใช้แทน size == 0 ในบทที่ 14

top = 13
pop = 13
pop = 12
size = 2
pop = 14
pop = 11

ผลตรงกับโปรแกรมในหน้า 14.4 ทุกบรรทัด คำสั่งของ stack มีห้าตัว ตรงกับห้างานที่เขียนเองในบทที่ 14

สิ่งที่ stack ไม่มีให้ คือการดูตัวที่อยู่ข้างล่าง ไม่มี s[0] และวนดูทุกตัวด้วย for ไม่ได้ เพราะ stack ตั้งใจให้แตะได้แค่ด้านบน ถ้างานไหนต้องดูของข้างล่างด้วย ให้ใช้ vector แทน ซึ่งใช้เป็น stack ได้ด้วย push_back pop_back และ back หรือใช้ deque ในหน้าถัดไป

queue

queue ใช้คำว่า push กับ pop เหมือน stack แต่ push ต่อท้ายคิว และ pop เอาหัวคิวออก ดูหัวคิวด้วย front() และดูท้ายคิวด้วย back() โปรแกรมนี้ใช้ลำดับคำสั่งเดียวกับโปรแกรม queue-basics ในหน้า 14.5 และเพิ่มการดูท้ายคิวอีกหนึ่งบรรทัด

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

int main()
{
    queue<int> line;
    line.push(11); // (1)!
    line.push(12);
    line.push(13);
    cout << "front = " << line.front() << '\n';
    cout << "back = " << line.back() << '\n';
    cout << "dequeue = " << line.front() << '\n';
    line.pop(); // (2)!
    cout << "dequeue = " << line.front() << '\n';
    line.pop();
    line.push(14);
    cout << "size = " << line.size() << '\n';
    while (!line.empty()) {
        cout << "dequeue = " << line.front() << '\n';
        line.pop();
    }
    return 0;
}

1. push ของ queue คือ enqueue ในบทที่ 14 ต่อท้ายคิว
2. pop ของ queue คือ dequeue เอาหัวคิวออก และไม่คืนค่าเหมือน stack ต้องดู front() ก่อน

front = 11
back = 13
dequeue = 11
dequeue = 12
size = 2
dequeue = 13
dequeue = 14

ระวังชื่อที่สับสนง่าย stack ใช้ top() ส่วน queue ใช้ front() เขียน line.top() กับ queue จะคอมไพล์ไม่ผ่าน และ queue ก็ไม่มี line[0] หรือวนดูทุกตัวเหมือน stack

เก็บอะไรก็ได้

stack ในบทที่ 14 เก็บ int ได้อย่างเดียว ถ้าอยากได้ stack ของ char ต้องเขียนใหม่ทั้งชุดแบบโปรแกรม brackets ของ C++ แค่เปลี่ยนชนิดในวงเล็บ <> จะเป็น string หรือ pair จากบทที่ 16 ก็ได้

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

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

int main()
{
    int n;
    cin >> n;
    queue<pair<string, int>> jobs; // (1)!
    for (int i = 0; i < n; i++) {
        string name;
        int pages;
        cin >> name >> pages;
        jobs.push({name, pages}); // (2)!
    }
    int minute = 0;
    while (!jobs.empty()) {
        auto job = jobs.front(); // (3)!
        jobs.pop();
        minute += job.second;
        cout << job.first << " done at minute " << minute << '\n';
    }
    return 0;
}

1. คิวที่แต่ละช่องเป็นคู่ของชื่อกับจำนวนหน้า
2. สร้าง pair ด้วยวงเล็บปีกกา เขียน make_pair(name, pages) ก็ได้ผลเหมือนกัน
3. คัดลอกหัวคิวเก็บไว้ก่อน แล้วค่อย pop ถ้า pop ก่อนจะไม่มีอะไรให้ดูแล้ว

4
Ploy 12
Krit 3
Mint 30
Tan 5

Ploy done at minute 12
Krit done at minute 15
Mint done at minute 45
Tan done at minute 50

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

ทุกคำสั่งใช้เวลาคงที่

คำสั่งทุกตัวในสองตารางข้างบนทำงานไม่กี่ขั้น ไม่ว่าในนั้นจะมีของ 10 ชิ้นหรือ 10 ล้านชิ้น เวลาที่ไม่ขึ้นกับจำนวนของแบบนี้เขียนย่อว่า O(1) อ่านว่า โอวัน ส่วนงานที่ต้องไล่ดูของทุกชิ้นใช้เวลาโตตามจำนวนของ และ sort แบบลูปซ้อนในหน้า 13.3 ยิ่งโตเร็วกว่านั้นอีก สัญลักษณ์นี้มีชื่อว่า Big O จะเรียนอย่างเป็นระบบในบทที่ 18 ตอนนี้จำแค่ว่า O(1) คือเร็วเท่ากันเสมอ

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

เทียบกับที่เขียนเองในบทที่ 14

แถวสุดท้ายสำคัญที่สุด STL ไม่ได้ป้องกันการ pop ตอนว่างให้ ดูผลได้ในส่วนลองทำให้พัง

ความเร็วต่างกันไหม ลองวัดด้วย clock() แบบหน้า 4.5 ให้ทั้งสองแบบ push 10 ล้านตัวแล้ว pop จนหมด

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

int arr[10000000];

int main()
{
    int n = 10000000;
    clock_t start = clock();
    int size = 0;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        arr[size] = i;
        size++;
    }
    while (size > 0) {
        size--;
        sum += arr[size];
    }
    clock_t middle = clock();
    stack<int> st;
    for (int i = 0; i < n; i++) {
        st.push(i);
    }
    while (!st.empty()) {
        sum += st.top();
        st.pop();
    }
    clock_t end = clock();
    cout << "sum = " << sum << '\n';
    cout << fixed << setprecision(3);
    cout << "array: " << (double)(middle - start) / CLOCKS_PER_SEC << " seconds\n";
    cout << "stack: " << (double)(end - middle) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

วัดบนเครื่องที่เขียนเอกสารนี้ โน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 กับ GCC 14.2 ของ Code::Blocks รันแบบละ 5 ครั้ง ตารางเป็นค่ากลาง

แบบ Code::Blocks ที่ไม่ได้เปิด -O2 stack ช้ากว่าราว 8 เท่า เพราะทุกคำสั่งเป็นการเรียกฟังก์ชันหลายชั้นข้างใน แต่พอเปิด -O2 แบบที่ grader ใช้ ต่างกันแค่ราวสองเท่า และ 20 ล้านคำสั่งยังใช้ไม่ถึงหนึ่งในสามสิบวินาที โจทย์ระดับค่าย 1 ไม่มีข้อไหนตกเพราะใช้ stack แทนอาเรย์ ใช้ของสำเร็จรูปได้เลย

ลองทำให้พัง

แบบที่ 1 รับค่าจาก pop

คนที่เคยเขียน int x = pop(); ในบทที่ 14 จะเขียนแบบนี้โดยไม่คิด

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

int main()
{
    stack<int> plates;
    plates.push(11);
    plates.push(12);
    int x = plates.pop();
    cout << x << '\n';
    return 0;
}

plates.cpp:9:23: error: void value not ignored as it ought to be
    9 |     int x = plates.pop();
      |             ~~~~~~~~~~^~

void คือไม่มีค่า pop() ไม่คืนอะไรออกมา จึงเอาไปใส่ x ไม่ได้ แก้เป็นสองบรรทัด int x = plates.top(); แล้ว plates.pop();

แบบที่ 2 ดูตัวบนสุดตอน stack ว่าง

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

int main()
{
    stack<int> plates;
    cout << plates.top() << '\n';
    return 0;
}

คอมไพล์ผ่านโดยไม่มีคำเตือน พอรัน หน้าต่างไม่พิมพ์อะไรเลย แล้ว Code::Blocks ขึ้นว่า

Process returned -1073741819 (0xC0000005)

0xC0000005 คือรหัสของ Windows ที่แปลว่าโปรแกรมไปอ่านหน่วยความจำที่ไม่ใช่ของมัน top() ไม่ได้ตรวจว่ามีของหรือเปล่า มันแค่ไปอ่านช่องที่ควรเป็นตัวบนสุด ซึ่งไม่มีอยู่จริง ส่งให้ grader จะได้ผล runtime error

queue ว่างก็ผิดแบบเดียวกัน แต่อาการไม่เหมือนกันทุกครั้ง บนเครื่องที่เขียนเอกสารนี้ เรียก back() ของ queue ว่างพังด้วยรหัส 0xC0000005 เกือบทุกครั้ง ส่วน front() ไม่พัง แต่พิมพ์ค่าขยะที่เปลี่ยนทุกครั้งที่รัน เช่น -845817440 แล้วจบด้วย Process returned 0 (0x0) เหมือนไม่มีอะไรผิด ผลแบบนี้ขึ้นกับเครื่อง เครื่องอื่นอาจพังหรือไม่พังก็ได้ แบบที่ไม่พังอันตรายกว่า เพราะคำตอบผิดเงียบๆ

แบบที่ 3 pop ตอน stack ว่าง

แบบนี้อันตรายกว่า เพราะโปรแกรมไม่พังให้เห็น

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

int main()
{
    stack<int> plates;
    plates.push(11);
    plates.pop();
    cout << "size = " << plates.size() << '\n';
    plates.pop();
    cout << "size = " << plates.size() << '\n';
    cout << "empty = " << plates.empty() << '\n';
    return 0;
}

size = 0
size = 18446744073709551615
empty = 0

นี่คือผลบนเครื่องที่เขียนเอกสารนี้ ทั้งแบบ Code::Blocks และแบบ -O2 pop ครั้งที่สองไม่มีของให้ทิ้ง แต่ตัวนับข้างในก็ยังลดลงจาก 0 size() เป็น unsigned ติดลบไม่ได้ เหมือน size() ของ vector ในหน้า 16.1 ลบหนึ่งจาก 0 จึงวนไปเป็นค่ามากสุดของมัน คือ 2⁶⁴ - 1 แบบเดียวกับ overflow ในหน้า 1.3 หลังจากนี้ empty() ตอบว่าไม่ว่าง ลูป while (!plates.empty()) จะเรียก top() กับ stack ที่ไม่มีของจริง ผลเป็นได้ทุกแบบ มาตรฐานภาษาไม่ได้กำหนดว่าต้องเกิดอะไร เครื่องอื่นอาจพังทันทีก็ได้ เช่นเดียวกับ pop ของ queue ว่าง

ทางแก้มีทางเดียวเหมือนบทที่ 14 คือเช็กก่อนทุกครั้ง

if (plates.empty()) {
    cout << "EMPTY\n";
} else {
    cout << plates.top() << '\n';
    plates.pop();
}

แบบที่ 4 ดูตัวล่างด้วยวงเล็บเหลี่ยม

ในโปรแกรมแบบที่ 1 เปลี่ยนสองบรรทัดก่อน return เป็น cout << plates[0] << '\n'; เพื่อดูจานใบล่างสุด

plates.cpp:9:19: error: no match for 'operator[]' (operand types are 'std::stack<int>' and 'int')
    9 |     cout << plates[0] << '\n';
      |                   ^

no match for 'operator[]' แปลว่าชนิดนี้ไม่มีวงเล็บเหลี่ยมให้ใช้ ถ้าลองวนด้วย for (int x : plates) จะได้ error ยาวกว่าร้อยบรรทัด (114 บรรทัดเมื่อคอมไพล์ด้วย -Wall บนเครื่องที่เขียนเอกสารนี้) บรรทัดแรกคือ no matching function for call to 'begin(std::stack<int>&)' ซึ่งแปลว่าวนไม่ได้เหมือนกัน ถ้าต้องดูของข้างล่าง ให้เปลี่ยนไปใช้ vector หรือ deque

สรุป

• stack<int> s; ใช้ push pop top empty size
• queue<int> q; ใช้ push pop front back empty size
• pop() ไม่คืนค่า ดูด้วย top() หรือ front() ก่อนแล้วค่อย pop
• ทุกคำสั่งใช้เวลาคงที่ O(1) ไม่ต้องเลือกขนาด และเก็บชนิดไหนก็ได้
• ดูหรือ pop ตอนว่างยังผิดเหมือนเดิม อาจพังหรือได้ค่าเพี้ยนเงียบๆ เช็ก empty() ก่อนเสมอ