Stack & Queue

Dua ADT linier paling penting: LIFO dan FIFO, operasi dasarnya, implementasi, dan di mana mereka dipakai.

Stack dan queue adalah Abstract Data Type (ADT): yang didefinisikan adalah perilakunya (operasi apa saja dan aturannya), bukan cara menyimpannya. Keduanya bisa diimplementasikan dengan array maupun linked list.

Stack: Last In, First Out

Bayangkan tumpukan piring. Piring yang terakhir ditaruh adalah yang pertama diambil. Semua operasi terjadi di satu ujung yang disebut top.

Operasi	Arti	Kompleksitas
`push(x)`	taruh `x` di top	$O(1)$
`pop()`	ambil & hapus elemen top	$O(1)$
`peek()` / `top()`	lihat elemen top tanpa menghapus	$O(1)$
`isEmpty()`	apakah kosong?	$O(1)$

Stack ada di mana-mana: call stack saat fungsi dipanggil, tombol undo, tombol back di browser, evaluasi ekspresi postfix, dan pengecekan tanda kurung seimbang.

Queue: First In, First Out

Seperti antrean kasir: yang datang duluan dilayani duluan. Elemen masuk di rear (belakang) dan keluar dari front (depan).

Queue dipakai untuk antrean proses di sistem operasi, buffer jaringan/printer, dan algoritma BFS pada graf.

Implementasi circular queue

class CircularQueue<T> {
  private data: (T | undefined)[];
  private front = 0;
  private size = 0;
  constructor(private cap: number) { this.data = new Array(cap); }

  enqueue(x: T) {
    if (this.size === this.cap) throw new Error('Queue penuh');
    this.data[(this.front + this.size) % this.cap] = x;   // posisi rear
    this.size++;
  }
  dequeue(): T {
    if (this.size === 0) throw new Error('Queue kosong');
    const x = this.data[this.front]!;
    this.front = (this.front + 1) % this.cap;
    this.size--;
    return x;
  }
}

Variasi lain

Deque (double-ended queue): bisa tambah/hapus di kedua ujung.
Priority queue: yang keluar duluan adalah elemen dengan prioritas tertinggi, bukan yang datang duluan. Implementasi efisiennya memakai heap, $O(\log n)$ per operasi.

Postfix dan antrean prioritas

Untuk mengevaluasi postfix, dorong operand ke stack. Ketika bertemu operator, pop operand kanan terlebih dahulu, lalu operand kiri. Pada urutan 8 3 - 2 *, pengurangan mengambil kanan 3 dan kiri 8 sehingga mendorong 5. Perkalian berikutnya menghasilkan 10. Urutan pop penting untuk pengurangan dan pembagian.

Antrean prioritas mengeluarkan elemen berdasarkan prioritas. Jika tiket A datang dulu dengan prioritas rendah dan tiket B datang belakangan dengan prioritas tinggi, B bisa keluar lebih dulu. Aturan FIFO dapat dipakai untuk seri antar elemen dengan prioritas sama jika spesifikasinya begitu.

Latihan: Kurung Seimbang, Evaluasi Postfix, Min Stack.