Setelah memahami konsep LIFO di Chapter sebelumnya, sekarang kita membangun stack dengan tiga pendekatan berbeda: berbasis array (menggunakan std::vector), berbasis linked list, dan std::stack<T, Container> dari STL yang parameterizable. Setiap pendekatan punya trade-off — std::vector punya cache locality tinggi, linked list tidak pernah realokasi, dan std::stack memberikan antarmuka yang sudah teruji. Pada Chapter ini kita akan membandingkan ketiganya secara konkret, menguji performa konseptual, dan melihat kapan memilih yang mana.

Pendekatan 1: Stack Berbasis Array (std::vector) #

Mekanisme: vector sebagai Array Dinamis #

std::vector menyimpan elemen dalam blok kontigu. push_back menambah di akhir, pop_back menghapus dari akhir. Karena akhir adalah “top” stack, operasi stack menjadi natural — O(1) amortisasi untuk push_back dan O(1) untuk pop_back.

Kode: ArrayStack #

cpp 
template <typename T>
class ArrayStack {
public:
    void push(const T& v) { data_.push_back(v); }
    T pop() {
        if (data_.empty()) throw std::out_of_range("stack kosong");
        T v = data_.back();
        data_.pop_back();
        return v;
    }
    const T& top() const {
        if (data_.empty()) throw std::out_of_range("stack kosong");
        return data_.back();
    }
    bool empty() const { return data_.empty(); }
    std::size_t size() const { return data_.size(); }
private:
    std::vector<T> data_;
};

Karakteristik #

  • Memori kontigu: cache friendly, prefetcher bekerja, akses cepat.
  • Realokasi: bila kapasitas penuh, std::vector mengalokasikan blok baru 2x lipat dan menyalin elemen lama. push_back menjadi O(1) amortisasi tetapi ada satu operasi mahal sesekali.
  • Memori overhead: hanya capacity - size slot tidak terpakai, biasanya < 2x ukuran sebenarnya.

Pendekatan 2: Stack Berbasis Linked List #

Mekanisme: Push ke Depan, Pop dari Depan #

Linked list stack menyimpan head_ sebagai top. push menambah node baru di depan (jadikan head baru); pop menghapus head lama dan mengganti dengan head->next. Operasi O(1) tanpa realokasi.

cpp 
template <typename T>
struct Node {
    T nilai;
    Node* next;
    Node(const T& v) : nilai(v), next(nullptr) {}
};

template <typename T>
class ListStack {
public:
    ListStack() : head_(nullptr), size_(0) {}
    ~ListStack() {
        while (head_ != nullptr) {
            Node<T>* nx = head_->next;
            delete head_;
            head_ = nx;
        }
    }
    void push(const T& v) {
        Node<T>* n = new Node<T>(v);
        n->next = head_;
        head_ = n;
        ++size_;
    }
    T pop() {
        if (head_ == nullptr) throw std::out_of_range("stack kosong");
        T v = head_->nilai;
        Node<T>* old = head_;
        head_ = head_->next;
        delete old;
        --size_;
        return v;
    }
    const T& top() const {
        if (head_ == nullptr) throw std::out_of_range("stack kosong");
        return head_->nilai;
    }
    bool empty() const { return head_ == nullptr; }
    std::size_t size() const { return size_; }
private:
    Node<T>* head_;
    std::size_t size_;
};

Karakteristik #

  • Tidak ada realokasi: setiap push mengalokasikan tepat satu node. Operasi benar-benar O(1) worst case, bukan amortisasi.
  • Cache locality rendah: node tersebar di heap, jump pointer ke alamat acak.
  • Memori overhead besar: 8 byte pointer ekstra per elemen (sistem 64-bit) — overhead 100% untuk int.
  • Destructor wajib traverse: setiap node harus di-delete; RAII penting di sini.

Pendekatan 3: std::stack<T, Container> #

Mekanisme: Adapter Pattern #

std::stack bukan struktur data baru — ia adalah adapter yang membungkus container lain. Default container adalah std::deque, tetapi kita bisa parameterkan ke std::vector atau std::list:

cpp 
std::stack<int> s1;                              // default: deque
std::stack<int, std::vector<int>> s2;            // vector
std::stack<int, std::list<int>> s3;              // list

Container harus mendukung back(), push_back(), pop_back() — syarat yang dipenuhi std::vector, std::deque, dan std::list.

Keuntungan #

  • Antarmuka terstandar: push, pop, top, empty, size di semua container seragam.
  • Sudah teruji: implementasi STL dioptimasi dan diuji oleh jutaan pengguna.
  • Switchable: ganti container hanya dengan satu template parameter — misal deque (default) → vector untuk cache locality yang lebih baik.

Kode Lengkap Tiga Pendekatan #

cpp 
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <stdexcept>

// 1. Stack berbasis array (vector)
template <typename T>
class ArrayStack {
public:
    void push(const T& v) { data_.push_back(v); }
    T pop() {
        if (data_.empty()) throw std::out_of_range("stack kosong");
        T v = data_.back();
        data_.pop_back();
        return v;
    }
    const T& top() const {
        if (data_.empty()) throw std::out_of_range("stack kosong");
        return data_.back();
    }
    bool empty() const { return data_.empty(); }
    std::size_t size() const { return data_.size(); }
private:
    std::vector<T> data_;
};

// 2. Stack berbasis linked list
template <typename T>
struct Node {
    T nilai;
    Node* next;
    Node(const T& v) : nilai(v), next(nullptr) {}
};

template <typename T>
class ListStack {
public:
    ListStack() : head_(nullptr), size_(0) {}
    ~ListStack() {
        while (head_ != nullptr) {
            Node<T>* nx = head_->next;
            delete head_;
            head_ = nx;
        }
    }
    void push(const T& v) {
        Node<T>* n = new Node<T>(v);
        n->next = head_;
        head_ = n;
        ++size_;
    }
    T pop() {
        if (head_ == nullptr) throw std::out_of_range("stack kosong");
        T v = head_->nilai;
        Node<T>* old = head_;
        head_ = head_->next;
        delete old;
        --size_;
        return v;
    }
    const T& top() const {
        if (head_ == nullptr) throw std::out_of_range("stack kosong");
        return head_->nilai;
    }
    bool empty() const { return head_ == nullptr; }
    std::size_t size() const { return size_; }
private:
    Node<T>* head_;
    std::size_t size_;
};

int main() {
    std::cout << "=== ArrayStack ===\n";
    ArrayStack<int> as;
    as.push(10);
    as.push(20);
    as.push(30);
    std::cout << "top  = " << as.top() << '\n';
    std::cout << "pop  = " << as.pop() << '\n';
    std::cout << "pop  = " << as.pop() << '\n';
    std::cout << "size = " << as.size() << '\n';

    std::cout << "\n=== ListStack ===\n";
    ListStack<std::string> ls;
    ls.push("alpha");
    ls.push("beta");
    ls.push("gamma");
    std::cout << "top  = " << ls.top() << '\n';
    std::cout << "pop  = " << ls.pop() << '\n';
    std::cout << "pop  = " << ls.pop() << '\n';
    std::cout << "size = " << ls.size() << '\n';

    std::cout << "\n=== std::stack (default deque) ===\n";
    std::stack<int> s1;
    s1.push(1); s1.push(2); s1.push(3);
    std::cout << "top  = " << s1.top() << '\n';
    s1.pop();
    std::cout << "top  = " << s1.top() << '\n';

    std::cout << "\n=== std::stack berbasis vector ===\n";
    std::stack<int, std::vector<int>> s2;
    s2.push(100); s2.push(200); s2.push(300);
    std::cout << "top  = " << s2.top() << '\n';
    s2.pop();
    std::cout << "top  = " << s2.top() << '\n';

    std::cout << "\n=== std::stack berbasis list ===\n";
    std::stack<int, std::list<int>> s3;
    s3.push(7); s3.push(8); s3.push(9);
    std::cout << "top  = " << s3.top() << '\n';
    s3.pop();
    std::cout << "top  = " << s3.top() << '\n';

    return 0;
}

Output yang Dihasilkan:

text 
=== ArrayStack ===
top  = 30
pop  = 30
pop  = 20
size = 1

=== ListStack ===
top  = gamma
pop  = gamma
pop  = beta
size = 1

=== std::stack (default deque) ===
top  = 3
top  = 2

=== std::stack berbasis vector ===
top  = 300
top  = 200

=== std::stack berbasis list ===
top  = 9
top  = 8

Tabel Perbandingan Implementasi #

AspekArrayStack (vector)ListStack (linked list)std::stack (deque default)
push worst caseO(1) amortisasi (realokasi sesekali)O(1) selaluO(1) selalu
popO(1)O(1)O(1)
Memori per elemen (int)4 byte12 byte (4 + 8 pointer)~4-8 byte
Cache localityTinggi (kontigu)Rendah (tersebar)Sedang (deque chunked)
Iterator tersediaYa (vector asli)TidakTidak
Use caseStack umumSangat banyak elemen, push criticalProduksi default

Kapan Memilih Yang Mana #

Pilih std::stack<int> (deque default) untuk:

  • Kebutuhan produksi standar — deque memadai untuk hampir semua kasus.
  • Anda tidak ingin memikirkan trade-off rendah-level.

Pilih std::stack<T, std::vector<T>> untuk:

  • Tipe elemen besar (mis. std::string 32 byte+) di mana cache locality signifikan.
  • Anda membutuhkan peek acak ke elemen ke-i (bukan top) lewat container asli.

Pilih linked list stack custom untuk:

  • Kasus di mana realokasi std::vector tidak boleh terjadi sama sekali (sistem real-time).
  • Pembelajaran struktur data — memahami pointer dan ownership.

Ringkasan #

  • Tiga pendekatan stack: std::vector-based (cache friendly, realokasi sesekali), linked list-based (selalu O(1), overhead besar), std::stack<T, Container> (adapter STL).
  • std::stack membungkus container yang mendukung back/push_back/pop_back — default std::deque, bisa diganti vector atau list.
  • std::stack tidak menyediakan iterator — sengaja, karena stack adalah struktur akses terbatas.
  • Untuk produksi, std::stack<T> (deque default) hampir selalu cukup. Custom stack hanya untuk pembelajaran atau kebutuhan real-time.
  • Chapter berikutnya akan membahas queue — kebalikan LIFO, yaitu FIFO (First In First Out).