std::stack dan std::queue

Beberapa pola pemakaian data muncul berulang-ulang di hampir semua aplikasi: urungkan langkah (undo) yang selalu mengembalikan perubahan terakhir, dan antrean layanan yang selalu melayani pendaftar pertama. Untuk pola itu standard library tidak menyuruh kita memakai vector secara mentah, melainkan menyediakan container adapter: std::stack untuk tumpukan LIFO (Last-In, First-Out), std::queue untuk antrean FIFO (First-In, First-Out), dan std::priority_queue untuk antrean berdasarkan prioritas. Disebut adapter karena keduanya membungkus container lain (defaultnya std::deque) dan membatasi antarmukanya agar hanya menampilkan operasi yang benar untuk pola tersebut. Chapter ini memperagakan ketiganya dengan dua kasus klasik: undo editor teks dan antrian pelayanan.

stack: Terakhir Masuk, Pertama Keluar #

std::stack hanya membuka tiga operasi inti: push menaruh elemen di puncak, top membaca elemen puncak, dan pop membuang elemen puncak. Dibantu empty() dan size(), kita sudah bisa menuliskan seluruh logika undo. Perhatikan bahwa pop() tidak mengembalikan nilai — kita wajib membaca top() lebih dulu bila ingin tahu apa yang dibuang.

#include <iostream>  // std::cout
#include <queue>     // std::queue (FIFO) dan std::priority_queue
#include <stack>     // std::stack (LIFO)
#include <string>    // std::string

int main() {
    // --- stack LIFO: mensimulasikan fitur undo editor teks ---
    std::stack<std::string> riwayat;
    riwayat.push("ketik 'Halo'");
    riwayat.push("ketik 'Dunia'");
    riwayat.push("hapus 'Dunia'");

    std::cout << "Undo (terakhir dulu):\n";
    while (!riwayat.empty()) {
        std::cout << "  urungkan: " << riwayat.top() << "\n";
        riwayat.pop();
    }

    // --- queue FIFO: antrian layanan pertama datang, pertama dilayani ---
    std::queue<std::string> antrian;
    antrian.push("Siti");
    antrian.push("Dewi");
    antrian.push("Budi");

    std::cout << "Antrian (pertama dulu):\n";
    while (!antrian.empty()) {
        std::cout << "  layani " << antrian.front() << "\n";
        antrian.pop();
    }

    // --- priority_queue (preview): terbesar selalu di puncak ---
    std::priority_queue<int> tugas;
    tugas.push(3);    // prioritas rendah
    tugas.push(10);
    tugas.push(7);

    std::cout << "priority_queue: top=" << tugas.top() << "\n";
    tugas.pop();
    std::cout << "Setelah pop   : top=" << tugas.top() << "\n";

    return 0;
}

Output yang Dihasilkan:

Undo (terakhir dulu):
  urungkan: hapus 'Dunia'
  urungkan: ketik 'Dunia'
  urungkan: ketik 'Halo'
Antrian (pertama dulu):
  layani Siti
  layani Dewi
  layani Budi
priority_queue: top=10
Setelah pop   : top=7

Mari kita bedah:

1. Baris 9-11 (mengisi riwayat): tiga aksi editor ditumpuk berurutan. Keadaan terakhir stack: "hapus 'Dunia'" berada di puncak karena masuk paling akhir.
2. Baris 14-17 (loop undo): selama stack tidak kosong, top() membaca puncak lalu pop() membuangnya. Urutan keluar otomatis terbalik dari urutan masuk — persis perilaku undo yang diinginkan pengguna: langkah terakhir diurungkan lebih dulu.
3. Baris 21-23 (mengisi antrian): tiga pelanggan masuk sesuai urutan kedatangan. push pada queue berarti masuk di belakang barisan.
4. Baris 26-29 (melayani): front() membaca paling depan dan pop() menggeser barisan. Siti keluar duluan padahal ia masuk pertama — kebalikan stack.
5. Baris 32-39 (priority_queue): kita memasukkan 3, 10, 7 secara acak, tetapi top() selalu mengembalikan nilai terbesar. Setelah satu pop, puncak berpindah ke 7. Adapter ini menjamin elemen prioritas tertinggi siap diambil kapan pun, dengan biaya push dan pop O(log n).

Adapter Membungkus Container #

Menariknya, stack dan queue bukan struktur data baru melainkan interface ketat di atas container lama. Secara default keduanya memakai std::deque, tetapi kita bisa memilih dasarnya: std::stack<int, std::vector<int>> atau std::queue<std::string, std::list<std::string>>. Batasan antarmukanya adalah nilainya: dengan hanya push/top/pop atau push/front/pop, kita tidak bisa secara tidak sengaja mengubah elemen tengah — invariant pola tetap terjaga.

Kasus Pemakaian yang Khas #

• stack: undo/redo editor, riwayat navigasi (tombol back browser), evaluasi ekspresi matematika, penelusuran depth-first pada graf, serta pencabutan pemanggilan fungsi itu sendiri — call stack program memakai prinsip yang sama.
• queue: antrean cetak, buffer pesan antar-thread, penjadwalan tugas berkeadilan (round-robin), penelusuran breadth-first pada graf.
• priority_queue: penjadwal berbasis urgensi, algoritma Dijkstra, dan sistem antrian tiket yang memprioritaskan pelanggan tertentu.

Tumpukan dan antrean menuntut data diambil sesuai urutan kedatangan. Banyak masalah lain justru kebalikannya: kita ingin data selalu terurut dan bebas duplikat sejak awal — kebutuhan yang dijawab std::set pada Chapter berikutnya.

Rujukan resmi: cppreference — std::stack , cppreference — std::queue , cppreference — std::priority_queue .