Stack

Stack adalah struktur data dengan satu pintu, yaitu elemen masuk dan keluar melalui tempat yang sama bernama puncak. Prinsipnya disebut LIFO (last in, first out), yakni elemen yang terakhir masuk adalah yang pertama keluar, persis seperti tumpukan piring yang hanya bisa diambil dari bagian atasnya. Topik ini membangun stack dari dua bahan berbeda, yaitu list Python dan array tetap berindeks puncak pada Java, lalu menghubungkannya dengan call stack yang menjalankan pemanggilan fungsi. Setelah selesai membaca, operasi push, pop, dan peek dapat diimplementasikan sendiri lengkap dengan penjaga kondisi penuh dan kosong.

Prinsip LIFO#

Semua aktivitas stack terjadi di satu ujung yang disebut puncak (top). Operasi push menaruh elemen baru di puncak, operasi pop mengambil sekaligus menghapus elemen paling atas, sedangkan peek membacanya tanpa menghapus. Tidak ada operasi yang menyentuh bagian tengah atau dasar stack, dan itulah sebabnya ketiganya berbiaya $O(1)$, tetap sama cepat berapa pun tinggi tumpukannya. Sebagai perbandingan, list memperbolehkan penyisipan di indeks mana pun, dan kemudahan itu dibayar dengan pergeseran elemen berbiaya $O(n)$.

Diagram berikut memperlihatkan kedua arah operasi pada satu tumpukan nilai. push(40) menambah elemen di puncak, sedangkan pop() mengambil 30 dari tempat yang sama. Nilai 10 yang masuk paling awal berada paling bawah, dan ia hanya menyentuh tangan pembaca setelah seluruh elemen di atasnya habis diambil.

Stack dengan list Python#

Python menyediakan bahan baku stack pada list, cukup diambil dari ujung kanannya. Metode append menambah elemen di ujung kanan dengan biaya amortisasi $O(1)$, metode pop tanpa argumen menghapus dari ujung yang sama juga dengan $O(1)$, sedangkan data[-1] membaca puncak tanpa menghapusnya. Yang perlu dihindari hanyalah insert(0, x) dan pop(0), karena keduanya menggeser seluruh elemen dan berbiaya $O(n)$. Berkas berikut memperagakan satu siklus push, peek, dan pop pada satu list.

"""Stack dengan list Python: append sebagai push, pop dari ujung kanan."""

tumpukan = []

# push tiga elemen dari ujung kanan list
tumpukan.append(10)
tumpukan.append(20)
tumpukan.append(30)
print("isi stack :", tumpukan)

# peek: membaca puncak tanpa menghapusnya
print("peek      :", tumpukan[-1])

# pop dua kali: yang terakhir masuk keluar lebih dulu
print("pop       :", tumpukan.pop())
print("pop       :", tumpukan.pop())
print("sisa      :", tumpukan)

isi stack : [10, 20, 30]
peek      : 30
pop       : 30
pop       : 20
sisa      : [10]

Keluarannya menegaskan urutan LIFO. Nilai 30 yang paling akhir masuk keluar lebih dulu, disusul 20, dan 10 yang paling awal masuk justru tertinggal sampai akhir. Untuk hampir semua kebutuhan sehari-hari, stack berbasis list Python sudah memadai dan tidak memerlukan kelas tambahan.

Stack dengan array tetap pada Java#

Java menawarkan versi yang lebih terbuka, yaitu membangun stack di atas array tetap dengan satu indeks puncak. Indeks top dimulai dari -1 sebagai tanda kosong, push menaikkannya lalu menulis nilai pada posisi baru, sedangkan pop membaca nilai di top lalu menurunkannya. Karena kapasitas array terkunci sejak dibuat, push wajib memeriksa kondisi penuh terlebih dahulu, dan pop wajib memeriksa kosong. Kelas berikut mengimplementasikan seluruh operasi tersebut dari nol.

public class StackArray {
    private int[] data;
    private int top;   // indeks puncak, -1 berarti kosong

    public StackArray(int kapasitas) {
        data = new int[kapasitas];
        top = -1;
    }

    public boolean kosong() {
        return top == -1;
    }

    public boolean penuh() {
        return top == data.length - 1;
    }

    public void push(int nilai) {
        if (penuh()) {
            throw new IllegalStateException("stack penuh");
        }
        data[++top] = nilai;
    }

    public int pop() {
        if (kosong()) {
            throw new IllegalStateException("stack kosong");
        }
        return data[top--];
    }

    public int peek() {
        if (kosong()) {
            throw new IllegalStateException("stack kosong");
        }
        return data[top];
    }

    public static void main(String[] args) {
        StackArray s = new StackArray(3);
        System.out.println("kosong : " + s.kosong());
        s.push(5);
        s.push(12);
        s.push(7);
        System.out.println("penuh  : " + s.penuh());
        System.out.println("peek   : " + s.peek());
        System.out.println("pop    : " + s.pop());
        System.out.println("kosong : " + s.kosong());
    }
}

kosong : true
penuh  : true
peek   : 7
pop    : 7
kosong : false

Pemeriksaan penuh dan kosong pada kelas di atas bukan formalitas. Tanpa pemeriksaan penuh, push ke array yang sudah penuh memunculkan ArrayIndexOutOfBoundsException, sedangkan pop dari stack kosong membaca data[-1] yang tidak sah. Kelas ini memilih melempar IllegalStateException dengan pesan yang jelas. Pemanggil yang lupa memeriksa kondisi stack tetap dapat menelusuri penyebab errornya dengan cepat.

Stack dan call stack#

Setiap pemanggilan fungsi pada Python maupun Java mengerjakan pekerjaan yang sama dengan stack yang baru dibangun. Runtime menyimpan frame (rekam keadaan satu pemanggilan fungsi, mencakup argumen, variabel lokal, dan posisi kembali) pada call stack, yaitu stack yang dikelola otomatis oleh bahasa pemrograman. Fungsi yang dipanggil paling akhir selesai paling awal, persis LIFO. Pemahaman call stack ini menjadi bekal utama saat rekursi dipelajari, karena setiap pemanggilan rekursif menumpuk frame dengan pola yang persis sama.

Program berikut mencetak jejak masuk dan selesai pada rekursi sederhana.

def turun(n):
    if n == 0:                 # kasus dasar: panggilan terdalam
        print("dasar  : n =", n)
        return
    print("masuk  : n =", n)
    turun(n - 1)               # panggilan berikutnya ditumpuk
    print("selesai: n =", n)

turun(3)

masuk  : n = 3
masuk  : n = 2
masuk  : n = 1
dasar  : n = 0
selesai: n = 1
selesai: n = 2
selesai: n = 3

Cetakannya memperlihatkan dua fase yang jelas. Tiga pemanggilan masuk secara berurutan dan menumpuk di call stack, panggilan terdalam mencapai kasus dasarnya, lalu ketiganya selesai dalam urutan terbalik. Pola masuk terakhir, selesai terawal inilah ciri khas stack. Penghitungan kedalaman tumpukan pada program di atas sekaligus menjelaskan dari mana batas rekursi Python berasal.

Kesalahan umum#

1. Pop dari stack kosong. Pada list Python, pop dari list kosong memunculkan IndexError. Pada implementasi array tetap, pop tanpa pemeriksaan membaca data[-1] yang tidak sah. Periksa kosong() atau len(tumpukan) == 0 terlebih dahulu, atau tangkap exception-nya.
2. Mengira pop sekadar membaca. Pop menghapus elemennya, sehingga pemanggilan yang terlalu sering mengosongkan stack tanpa disadari. Untuk sekadar melihat puncak, gunakan peek atau data[-1].
3. Membangun stack di ujung kiri list. insert(0, x) dan pop(0) menggeser seluruh elemen sehingga berbiaya $O(n)$ per operasi. Gunakan ujung kanan list yang biayanya konstan.
4. Push tanpa memeriksa kapasitas array tetap. Tanpa pemeriksaan penuh, push hanya berhenti ketika exception memori terlempar atau lebih buruk. Rencanakan kapasitas sejak awal atau pakai implementasi yang tumbuh otomatis.

Ringkasan#

• Stack bekerja dengan prinsip LIFO, elemen masuk dan keluar hanya lewat puncaknya, sehingga push, pop, dan peek semuanya $O(1)$.
• List Python menyediakan stack siap pakai lewat append dan pop di ujung kanan, sedangkan array tetap pada Java butuh indeks puncak plus pemeriksaan penuh dan kosong.
• Call stack runtime menjalankan pemanggilan fungsi dengan pola yang sama, dan pola inilah dasar dari rekursi.

Referensi#

• Using lists as stacks and queues — Python Software Foundation — bagian dokumentasi Python yang menetapkan append dan pop di ujung kanan sebagai cara memakai list sebagai stack.
• Stack (abstract data type) — Wikipedia — definisi operasi stack serta kumpulan aplikasinya.
• Algorithms, 4th Edition — Princeton University — materi stack Princeton yang memuat implementasi referensi dan aplikasi algoritmiknya.