Array dan linked list membolehkan akses ke posisi mana pun, dan keluwesan itu berharga. Namun banyak persoalan justru bertambah sederhana ketika aksesnya dibatasi: riwayat tombol undo hanya butuh yang terakhir masuk, antrean loket hanya butuh yang paling depan menunggu. Stack memaksa prinsip Last-In-First-Out (LIFO) — yang terakhir masuk keluar lebih dulu; queue memaksa First-In-First-Out (FIFO) — yang pertama masuk dilayani lebih dulu. Bab ini membangun kedua struktur secara manual dari bahan Chapter sebelumnya (array dan node bertaut), lalu menggunakannya untuk satu studi kasus klasik: pemeriksa kurung pada kode sumber.

Stack LIFO dan Queue FIFO dalam Satu Program #

Kedua struktur bisa dibangun dari bahan yang berbeda. Stack cocok memakai array karena aktivitasnya terjadi di ujung: field atas menunjuk slot kosong berikutnya, push menulis ke sana, pop membaca slot di bawahnya. Queue justru cocok memakai linked list karena dua ujungnya bergerak independen: depan menjadi pintu keluar, belakang menjadi pintu masuk. Program berikut mengimplementasikan keduanya sekaligus:

java StackDanQueueManual.java 
public class StackDanQueueManual {

    // ===== Stack berbasis array: masuk dan keluar lewat ujung yang sama =====
    static class StackArray {
        private String[] isi = new String[8];
        private int atas;   // jumlah elemen sekaligus indeks slot kosong teratas

        void push(String nilai) {
            if (atas == isi.length) {
                throw new IllegalStateException("Stack penuh");
            }
            isi[atas++] = nilai;
        }

        String pop() {
            if (atas == 0) {
                throw new IllegalStateException("Stack kosong");
            }
            String nilai = isi[--atas];
            isi[atas] = null;   // lepaskan referensi agar garbage collector bekerja
            return nilai;
        }

        String peek() {
            if (atas == 0) {
                throw new IllegalStateException("Stack kosong");
            }
            return isi[atas - 1];
        }

        int ukuran() {
            return atas;
        }
    }

    // ===== Queue berbasis linked list: masuk di belakang, keluar di depan =====
    static class QueueLinked {
        static class Node {
            String data;
            Node next;

            Node(String data) {
                this.data = data;
            }
        }

        private Node depan;      // elemen keluar dari sini
        private Node belakang;   // elemen masuk dari sini
        private int ukuran;

        void enqueue(String nilai) {
            Node baru = new Node(nilai);
            if (belakang == null) {
                depan = baru;     // queue masih kosong
            } else {
                belakang.next = baru;
            }
            belakang = baru;
            ukuran++;
        }

        String dequeue() {
            if (depan == null) {
                throw new IllegalStateException("Queue kosong");
            }
            String nilai = depan.data;
            depan = depan.next;
            if (depan == null) {
                belakang = null;  // queue kembali kosong
            }
            ukuran--;
            return nilai;
        }

        int ukuran() {
            return ukuran;
        }
    }

    public static void main(String[] args) {
        System.out.println("=== Stack (LIFO) berbasis array ===");
        StackArray stack = new StackArray();
        stack.push("Budi");
        stack.push("Siti");
        stack.push("Dewi");
        System.out.println("peek()  : " + stack.peek());
        System.out.println("pop()   : " + stack.pop());
        System.out.println("pop()   : " + stack.pop());
        System.out.println("ukuran(): " + stack.ukuran());

        System.out.println();
        System.out.println("=== Queue (FIFO) berbasis linked list ===");
        QueueLinked queue = new QueueLinked();
        queue.enqueue("Budi");
        queue.enqueue("Siti");
        queue.enqueue("Dewi");
        System.out.println("dequeue(): " + queue.dequeue());
        System.out.println("dequeue(): " + queue.dequeue());
        System.out.println("ukuran() : " + queue.ukuran());
    }
}

Output yang Dihasilkan:

text 
=== Stack (LIFO) berbasis array ===
peek()  : Dewi
pop()   : Dewi
pop()   : Siti
ukuran(): 1

=== Queue (FIFO) berbasis linked list ===
dequeue(): Budi
dequeue(): Siti
ukuran() : 1

Urutan keluar keduanya berlawanan: stack mengembalikan Dewi lebih dulu padahal Dewi masuk terakhir, queue mengembalikan Budi lebih dulu karena Budi masuk paling awal. Mari kita bedah mekanisme di baliknya:

  1. Baris 11-16 (push): pemeriksaan atas == isi.length menjaga agar penulisan tidak melewati batas array; bila lolos, isi[atas++] = nilai menulis nilai lalu menaikkan atas satu satuan dalam satu pernyataan. Biaya total O(1) — tidak ada pergeseran elemen.
  2. Baris 18-26 (pop): isi[--atas] menurunkan atas lebih dulu baru membaca slot yang baru dikosongkan, sehingga elemen terakhir yang masuk menjadi yang pertama keluar. Penugasan isi[atas] = null melepas referensi lama — tanpa baris ini objek tetap ditahan array meski sudah tidak terpakai.
  3. Baris 51-61 (enqueue): node baru selalu ditambalkan setelah belakang, lalu belakang digeser ke node baru. Dua penunjuk membuat operasi O(1) meskipun queue memakai linked list yang traversal-nya O(n).
  4. Baris 63-74 (dequeue): depan = depan.next memindahkan pintu keluar satu node ke depan; node lama dilepas begitu saja. Ketika depan mencapai null, field belakang juga di-reset agar queue kosong tidak menyimpan penunjuk basi.

Studi Kasus Pencocokan Kurung #

Ke mana perginya kelincahan akses bebas? Ke jaminan perilaku. Compiler memeriksa keseimbangan kurung (), [], {} pada kode sumber dengan satu aturan elegan: kurung pembuka paling akhir harus ditutup lebih dulu — persis definisi LIFO. Versi produksi memakai ArrayDeque dari pustaka standar sebagai stack:

java PencocokKurung.java 
import java.util.ArrayDeque;
import java.util.Deque;

public class PencocokKurung {

    public static void main(String[] args) {
        String[] uji = {
            "int x = (a + b) * c[indeks];",
            "if (data[i] < maks) { total += data[i]; }",
            "{[(])}",       // pasangan bersilang
            "((()))(",      // kurung buka tanpa pasangan
            "())"           // kurung tutup tanpa pembuka
        };

        for (String teks : uji) {
            System.out.printf("%-42s -> %s%n", teks, cocok(teks));
        }
    }

    static String cocok(String teks) {
        Deque<Character> tumpukan = new ArrayDeque<>();
        for (char huruf : teks.toCharArray()) {
            if (huruf == '(' || huruf == '[' || huruf == '{') {
                tumpukan.push(huruf);      // pembuka ditumpuk
            } else if (huruf == ')' || huruf == ']' || huruf == '}') {
                if (tumpukan.isEmpty()) {
                    return "tidak cocok: '" + huruf + "' tanpa pembuka";
                }
                char pembuka = tumpukan.pop();
                if (!pasangan(pembuka, huruf)) {
                    return "tidak cocok: '" + pembuka + "' lawan '" + huruf + "'";
                }
            }
        }
        if (!tumpukan.isEmpty()) {
            return "tidak cocok: " + tumpukan.size()
                    + " pembuka tanpa penutup";
        }
        return "cocok";
    }

    static boolean pasangan(char pembuka, char penutup) {
        return (pembuka == '(' && penutup == ')')
                || (pembuka == '[' && penutup == ']')
                || (pembuka == '{' && penutup == '}');
    }
}

Output yang Dihasilkan:

text 
int x = (a + b) * c[indeks];               -> cocok
if (data[i] < maks) { total += data[i]; }  -> cocok
{[(])}                                     -> tidak cocok: '(' lawan ']'
((()))(                                    -> tidak cocok: 1 pembuka tanpa penutup
())                                        -> tidak cocok: ')' tanpa pembuka

Algoritma ini membaca teks satu karakter sekali jalan sehingga waktunya O(n), dan tiga jenis kegagalan tertangkap dengan pesan berbeda. Bedah logikanya:

  1. Baris 21-23 (tumpukan.push(huruf)): setiap pembuka dicatat di atas tumpukan. Urutan pencatatan menyimpan informasi urutan pembukaan — bagian yang akan diuji saat penutup muncul.
  2. Baris 24-31 (cabang penutup): penutup harus berhadapan dengan pembuka terakhir yang belum tertutup. pop() mengambil pembuka paling atas; bila jenisnya tidak cocok, pasangan bersilang seperti pada {[(])} terbukti dari pesan '(' lawan ']'.
  3. Baris 35-38 (pemeriksaan akhir): teks yang habis dibaca sementara tumpukan masih berisi berarti ada pembuka yang tidak pernah ditutup — kasus ((()))( dilaporkan sebagai 1 pembuka tanpa penutup.

Deque Membuka Dua Pintu #

Deque (double-ended queue) melonggarkan aturan menjadi dua pintu: elemen boleh masuk dan keluar dari kedua ujung. Operasi offerFirst/pollFirst mengurus ujung depan, offerLast/pollLast mengurus ujung belakang:

java DequeJava.java 
import java.util.ArrayDeque;
import java.util.Deque;

public class DequeJava {

    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        deque.offerFirst("Budi");
        deque.offerLast("Siti");
        deque.offerFirst("Dewi");
        deque.offerLast("Andi");

        System.out.println("deque        : " + deque);
        System.out.println("peekFirst()  : " + deque.peekFirst());
        System.out.println("peekLast()   : " + deque.peekLast());
        System.out.println("pollFirst()  : " + deque.pollFirst());
        System.out.println("pollLast()   : " + deque.pollLast());
        System.out.println("deque        : " + deque);
        System.out.println("ukuran()     : " + deque.size());
    }
}

Output yang Dihasilkan:

text 
deque        : [Dewi, Budi, Siti, Andi]
peekFirst()  : Dewi
peekLast()   : Andi
pollFirst()  : Dewi
pollLast()   : Andi
deque        : [Budi, Siti]
ukuran()     : 2

Dengan dua pintu terbuka, satu struktur yang sama bisa berperilaku sebagai stack (pakai satu ujung saja) atau queue (pakai kedua ujung berlawanan arah) — itulah alasan ArrayDeque menjadi implementasi serbaguna di pustaka Java.

Stack dan queue mengatur urutan kedatangan. Struktur berikutnya menukar urutan demi pencarian kilat: hash table, yang menemukan data tanpa menelusuri satu per satu.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

DequeJava.java

Unduh berkas
java 
import java.util.ArrayDeque;
import java.util.Deque;

public class DequeJava {

    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        deque.offerFirst("Budi");
        deque.offerLast("Siti");
        deque.offerFirst("Dewi");
        deque.offerLast("Andi");

        System.out.println("deque        : " + deque);
        System.out.println("peekFirst()  : " + deque.peekFirst());
        System.out.println("peekLast()   : " + deque.peekLast());
        System.out.println("pollFirst()  : " + deque.pollFirst());
        System.out.println("pollLast()   : " + deque.pollLast());
        System.out.println("deque        : " + deque);
        System.out.println("ukuran()     : " + deque.size());
    }
}

PencocokKurung.java

Unduh berkas
java 
import java.util.ArrayDeque;
import java.util.Deque;

public class PencocokKurung {

    public static void main(String[] args) {
        String[] uji = {
            "int x = (a + b) * c[indeks];",
            "if (data[i] < maks) { total += data[i]; }",
            "{[(])}",       // pasangan bersilang
            "((()))(",      // kurung buka tanpa pasangan
            "())"           // kurung tutup tanpa pembuka
        };

        for (String teks : uji) {
            System.out.printf("%-42s -> %s%n", teks, cocok(teks));
        }
    }

    static String cocok(String teks) {
        Deque<Character> tumpukan = new ArrayDeque<>();
        for (char huruf : teks.toCharArray()) {
            if (huruf == '(' || huruf == '[' || huruf == '{') {
                tumpukan.push(huruf);      // pembuka ditumpuk
            } else if (huruf == ')' || huruf == ']' || huruf == '}') {
                if (tumpukan.isEmpty()) {
                    return "tidak cocok: '" + huruf + "' tanpa pembuka";
                }
                char pembuka = tumpukan.pop();
                if (!pasangan(pembuka, huruf)) {
                    return "tidak cocok: '" + pembuka + "' lawan '" + huruf + "'";
                }
            }
        }
        if (!tumpukan.isEmpty()) {
            return "tidak cocok: " + tumpukan.size()
                    + " pembuka tanpa penutup";
        }
        return "cocok";
    }

    static boolean pasangan(char pembuka, char penutup) {
        return (pembuka == '(' && penutup == ')')
                || (pembuka == '[' && penutup == ']')
                || (pembuka == '{' && penutup == '}');
    }
}

StackDanQueueManual.java

Unduh berkas
java 
public class StackDanQueueManual {

    // ===== Stack berbasis array: masuk dan keluar lewat ujung yang sama =====
    static class StackArray {
        private String[] isi = new String[8];
        private int atas;   // jumlah elemen sekaligus indeks slot kosong teratas

        void push(String nilai) {
            if (atas == isi.length) {
                throw new IllegalStateException("Stack penuh");
            }
            isi[atas++] = nilai;
        }

        String pop() {
            if (atas == 0) {
                throw new IllegalStateException("Stack kosong");
            }
            String nilai = isi[--atas];
            isi[atas] = null;   // lepaskan referensi agar garbage collector bekerja
            return nilai;
        }

        String peek() {
            if (atas == 0) {
                throw new IllegalStateException("Stack kosong");
            }
            return isi[atas - 1];
        }

        int ukuran() {
            return atas;
        }
    }

    // ===== Queue berbasis linked list: masuk di belakang, keluar di depan =====
    static class QueueLinked {
        static class Node {
            String data;
            Node next;

            Node(String data) {
                this.data = data;
            }
        }

        private Node depan;      // elemen keluar dari sini
        private Node belakang;   // elemen masuk dari sini
        private int ukuran;

        void enqueue(String nilai) {
            Node baru = new Node(nilai);
            if (belakang == null) {
                depan = baru;     // queue masih kosong
            } else {
                belakang.next = baru;
            }
            belakang = baru;
            ukuran++;
        }

        String dequeue() {
            if (depan == null) {
                throw new IllegalStateException("Queue kosong");
            }
            String nilai = depan.data;
            depan = depan.next;
            if (depan == null) {
                belakang = null;  // queue kembali kosong
            }
            ukuran--;
            return nilai;
        }

        int ukuran() {
            return ukuran;
        }
    }

    public static void main(String[] args) {
        System.out.println("=== Stack (LIFO) berbasis array ===");
        StackArray stack = new StackArray();
        stack.push("Budi");
        stack.push("Siti");
        stack.push("Dewi");
        System.out.println("peek()  : " + stack.peek());
        System.out.println("pop()   : " + stack.pop());
        System.out.println("pop()   : " + stack.pop());
        System.out.println("ukuran(): " + stack.ukuran());

        System.out.println();
        System.out.println("=== Queue (FIFO) berbasis linked list ===");
        QueueLinked queue = new QueueLinked();
        queue.enqueue("Budi");
        queue.enqueue("Siti");
        queue.enqueue("Dewi");
        System.out.println("dequeue(): " + queue.dequeue());
        System.out.println("dequeue(): " + queue.dequeue());
        System.out.println("ukuran() : " + queue.ukuran());
    }
}