Struktur Data - Stack

Nama    : Aga Nafta Filadelfiano
NRP      : 5025251055
Kelas     : Struktur Data (D) 

Stack

1. Pengertian Stack

Stack adalah struktur data linear yang menyimpan kumpulan elemen dengan metode akses yang khusus. Dalam Stack, proses penambahan (insertion/push) dan penghapusan (deletion/pop) hanya dapat dilakukan pada satu sisi saja yang disebut sebagai Top (Puncak Stack).

2. Prinsip Stack

Stack beroperasi berdasarkan prinsip:
LIFO (Last In, First Out) 
Artinya: Elemen yang terakhir dimasukkan akan menjadi yang pertama kali dikeluarkan.

3. Operasi Dasar Stack

  • Push: Menambahkan elemen ke puncak stack.

  • Pop: Menghapus/mengeluarkan elemen dari puncak stack.

  • Peek/Top: Melihat elemen yang berada di posisi paling atas.

  • isEmpty: Mengecek apakah stack dalam keadaan kosong.

  • isFull: Mengecek apakah stack sudah penuh (khusus untuk implementasi Array).

4. Implementasi Stack Menggunakan Array (C++)


Hasil Output




5. Stack Menggunakan Linked List

Pada implementasi ini, Stack direpresentasikan sebagai urutan node yang terhubung secara dinamis.

  • Setiap elemen disebut Node.

  • Tiap Node memiliki data dan pointer ke node berikutnya.

  • Top dari stack selalu merujuk pada node paling depan (head).

6. Implementasi Stack dengan Linked List (C++)


Hasil Output

7. Kelebihan Stack dengan Linked List

  1. Dinamis: Ukuran tumpukan tidak terbatas (hanya dibatasi oleh sisa memori komputer).

  2. Efisiensi Memori: Memori hanya dialokasikan saat dibutuhkan (tidak ada unused space seperti pada array).

  3. Tidak Ada Overflow: Kita tidak perlu khawatir tentang batasan MAX yang membuat program berhenti.


8. Contoh Aplikasi: Konversi Ekspresi

Stack sering digunakan dalam pengolahan ekspresi matematika.

Jenis Notasi

  • Infix → operator di tengah (A + B)

  • Postfix → operator di belakang (A B +)

  • Prefix → operator di depan (+ A B)

Alasan Konversi

  • Postfix dan prefix lebih mudah diproses komputer

  • Tidak memerlukan tanda kurung

  • Tidak ambigu (tanpa aturan prioritas yang kompleks)

Contoh Konversi Infix ke Postfix

  • Infix: A + B * C

  • Postfix: A B C * +

Algoritma Singkat

  1. Scan ekspresi dari kiri ke kanan secara bertahap.

  2. Jika menemukan Operand (huruf/angka) langsung masukkan ke hasil Output.

  3. Jika menemukan Operator (+, -, *, /):

    • Cek Stack. Jika Stack kosong atau operator memiliki prioritas lebih tinggi dari yang ada di puncak Stack, masukkan (Push) ke Stack.

    • Jika prioritasnya lebih rendah atau sama, keluarkan (Pop) operator dari Stack ke Output, lalu masukkan operator baru ke Stack.

  4. Setelah selesai scan, keluarkan semua operator yang tersisa di dalam Stack ke Output.


Source Code: GitHub