Struktur Linear · Pelajaran 4 dari 10
Stack
9 menit baca · BelajarCode
Stack (tumpukan) bekerja seperti tumpukan piring: piring terakhir yang ditaruh adalah yang pertama diambil. Prinsip ini disebut LIFO (last in, first out).
| Operasi | Arti | Kompleksitas |
|---|---|---|
| push(x) | Menaruh x di atas | O(1) |
| pop() | Mengambil elemen teratas | O(1) |
| peek() | Melihat elemen teratas tanpa mengambil | O(1) |
| kosong() | Memeriksa apakah stack kosong | O(1) |
Di Python, list sudah cukup sebagai stack: append untuk push dan pop() untuk pop, keduanya bekerja di ujung belakang list.
Contoh: memeriksa pasangan kurung
1def kurung_seimbang(teks):2 pasangan = {")": "(", "]": "[", "}": "{"}3 stack = []4 for karakter in teks:5 if karakter in "([{":6 stack.append(karakter)7 elif karakter in ")]}":8 if not stack or stack.pop() != pasangan[karakter]:9 return False10 return not stack1112for t in ["(a + b) * [c - d]", "{[()]}", "(]", "((x)", "f(g[h{}])"]:13 print(f"{t:<18} {kurung_seimbang(t)}")(a + b) * [c - d] True
{[()]} True
(] False
((x) False
f(g[h{}]) TrueSetiap kurung buka ditumpuk. Setiap kurung tutup harus cocok dengan kurung buka teratas. Di akhir, stack harus kosong.
Contoh: menghitung ekspresi postfix
Ekspresi postfix menulis operator setelah operandnya, misalnya 3 4 + 2 * artinya (3 + 4) × 2. Kalkulator dan kompiler memakai bentuk ini karena mudah dihitung dengan stack.
1def hitung_postfix(ekspresi):2 stack = []3 for token in ekspresi.split():4 if token in "+-*/":5 b = stack.pop()6 a = stack.pop()7 if token == "+":8 stack.append(a + b)9 elif token == "-":10 stack.append(a - b)11 elif token == "*":12 stack.append(a * b)13 else:14 stack.append(a / b)15 else:16 stack.append(float(token))17 return stack.pop()1819print(hitung_postfix("3 4 + 2 *"))20print(hitung_postfix("5 1 2 + 4 * + 3 -"))14.0 14.0
Ekspresi kedua sama dengan 5 + (1 + 2) × 4 - 3 = 14.
Call stack
Komputer memakai stack untuk mengelola pemanggilan fungsi. Setiap pemanggilan fungsi menaruh catatan (variabel lokal dan alamat kembali) di call stack, dan mengambilnya saat fungsi selesai. Rekursi yang terlalu dalam membuat call stack penuh, yang di Python menghasilkan RecursionError.
Cek pemahaman
Urutan push 1, push 2, pop, push 3, pop, pop menghasilkan elemen yang diambil dalam urutan apa?
Latihan
Undo dan redo
Buat kelas Editor yang menyimpan teks, dengan metode ketik(s), undo(), dan redo(). Pakai dua stack: satu untuk riwayat undo, satu untuk redo. Mengetik setelah undo menghapus riwayat redo.
Pembahasan
1class Editor:2 def __init__(self):3 self.teks = ""4 self.undo_stack = []5 self.redo_stack = []67 def ketik(self, s):8 self.undo_stack.append(self.teks)9 self.teks += s10 self.redo_stack.clear()1112 def undo(self):13 if self.undo_stack:14 self.redo_stack.append(self.teks)15 self.teks = self.undo_stack.pop()1617 def redo(self):18 if self.redo_stack:19 self.undo_stack.append(self.teks)20 self.teks = self.redo_stack.pop()212223e = Editor()24e.ketik("Halo")25e.ketik(" dunia")26e.ketik("!")27e.undo()28e.undo()29print(repr(e.teks))30e.redo()31print(repr(e.teks))32e.ketik(" semua")33e.redo()34print(repr(e.teks))'Halo' 'Halo dunia' 'Halo dunia semua'
Setelah ketik(" semua"), riwayat redo dihapus, sehingga redo() terakhir tidak mengembalikan tanda seru.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.