Struktur Data Linear: Stack (Tumpukan) dan Queue (Antrean)

Struktur Data Linear: Karakteristik, Desain ADT, dan Implementasi Stack serta Queue

Pendalaman materi mengenai dua struktur data linear terpenting dalam komputasi sistem: Stack yang mengusung disiplin LIFO (Last In First Out) dan Queue yang menerapkan mekanisme FIFO (First In First Out).

1. Stack (Tumpukan - Prinsip LIFO)

Stack adalah koleksi terurut di mana penambahan elemen (push) dan penghapusan elemen (pop) hanya dapat dilakukan pada satu ujung yang disebut puncak tumpukan (top).

• Operasi Inti Stack:
  • push(item): Menyisipkan elemen baru ke posisi top.
  • pop(): Menghapus dan mengembalikan elemen dari posisi top.
  • peek() / top(): Menginspeksi elemen teratas tanpa menghapusnya.
  • isEmpty(): Memeriksa apakah ukuran stack bernilai 0.
• Penerapan Nyata: Mekanisme Undo/Redo pada editor teks, pengelolaan rekursi dan call stack memori pada sistem operasi, serta penelusuran graf Depth-First Search (DFS).

2. Queue (Antrean - Prinsip FIFO)

Queue adalah struktur linear di mana elemen dimasukkan melalui ujung belakang (rear/enqueue) dan dikeluarkan melalui ujung depan (front/dequeue).

• Variasi Desain Queue:
  • Circular Queue: Mengatasi fenomena false overflow pada implementasi array statis dengan memanfaatkan formula modulo: $\text{index} = (\text{index} + 1) \pmod N$.
  • Double-Ended Queue (Deque): Mengizinkan operasi penambahan dan penghapusan di kedua ujung secara efisien ($O(1)$).
  • Priority Queue: Elemen memiliki atribut prioritas dan dikeluarkan berdasarkan urutan bobot tertinggi menggunakan struktur heap.

3. Berkas Terlampir

• Slide materi bagian 1: Stack dan Queue.pptx.
• Slide materi bagian 2: Stack dan Queue 2.pptx.