Implementasi Stack dan Penerapannya
Implementasikan stack dengan push/pop/peek, lalu selesaikan valid-parentheses, min-stack, dan evaluasi notasi reverse-polish.
Implementasi Stack dan Penerapannya adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Struktur Data Stack
Tumpukan adalah struktur data masuk-terakhir, keluar-pertama (LIFO). Elemen terakhir yang dimasukkan adalah elemen pertama yang dikeluarkan. Bayangkan tumpukan piring: Anda hanya dapat menambahkan atau menghapus dari bagian atas. Operasi inti adalah push (menambahkan ke bagian atas), pop (menghapus dari bagian atas), dan peek (membaca elemen teratas tanpa menghapusnya). Ketiganya memerlukan O(1) pada tumpukan yang diimplementasikan dengan baik.
Dalam Python, list berfungsi sebagai tumpukan yang sempurna: append adalah push, pop() adalah pop, dan [-1] adalah peek.
stack = []
# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack) # [10, 20, 30]
# Peek
print('Top:', stack[-1]) # 30
# Pop
print('Popped:', stack.pop()) # 30
print('After pop:', stack) # [10, 20]Kelas Stack dengan push, pop, peek, isEmpty
Membungkus list dalam sebuah kelas menyediakan antarmuka yang lebih rapi dan mencegah penggunaan operasi non-tumpukan secara tidak sengaja, seperti insert atau pengindeksan pada posisi selain bagian atas. Inilah implementasi yang diharapkan pewawancara ketika meminta Anda 'mengimplementasikan tumpukan dari awal'.
class Stack:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
def pop(self):
if self.is_empty():
raise IndexError('pop from empty stack')
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty stack')
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek()) # 3
print(s.pop()) # 3
print(len(s)) # 2Tanda Kurung Valid (LeetCode 20)
LeetCode 20 'Tanda Kurung Valid': tentukan apakah sebuah teks yang berisi tanda kurung seimbang. Untuk setiap tanda kurung buka, masukkan ke tumpukan dengan push. Untuk setiap tanda kurung tutup, periksa apakah elemen teratas tumpukan adalah tanda kurung buka yang sesuai; jika tidak, atau jika tumpukan kosong, kembalikan nilai salah. Jika tumpukan kosong pada akhir proses, teks tersebut valid. Ini merupakan penerapan pertama tumpukan yang paling umum dalam wawancara pemrograman.
def isValid(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack[-1] != matching[ch]:
return False
stack.pop()
return len(stack) == 0
print(isValid('()[]{}')) # True
print(isValid('([)]')) # False
print(isValid('{[]}')) # True
print(isValid(']')) # FalseStack Minimum (LeetCode 155)
LeetCode 155 'Stack Minimum': rancang tumpukan yang mendukung push, pop, peek, dan getMin, semuanya dalam O(1). Triknya adalah mempertahankan tumpukan kedua yang melacak nilai minimum pada setiap titik. Saat melakukan push, masukkan nilai tersebut ke tumpukan minimum jika nilai baru <= minimum saat ini (atau jika tumpukan minimum kosong). Saat melakukan pop, keluarkan juga elemen dari tumpukan minimum jika nilai yang dikeluarkan sama dengan minimum saat ini.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin()) # -3
ms.pop()
print(ms.top()) # 0
print(ms.getMin()) # -2Mengevaluasi Notasi Polandia Terbalik
LeetCode 150 'Mengevaluasi Notasi Polandia Terbalik' (postfiks): operand dimasukkan ke tumpukan; saat menemukan operator, keluarkan dua operand, terapkan operator tersebut, lalu masukkan hasilnya. Urutannya penting untuk pengurangan dan pembagian: operand yang pertama dikeluarkan adalah operand kanan, sedangkan operand kedua adalah operand kiri.
def evalRPN(tokens):
stack = []
ops = set(['+', '-', '*', '/'])
for tok in tokens:
if tok not in ops:
stack.append(int(tok))
else:
b = stack.pop() # right operand
a = stack.pop() # left operand
if tok == '+':
stack.append(a + b)
elif tok == '-':
stack.append(a - b)
elif tok == '*':
stack.append(a * b)
else: # division truncated toward zero
stack.append(int(a / b))
return stack[0]
print(evalRPN(['2','1','+','3','*'])) # 9
print(evalRPN(['4','13','5','/','+'])) # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+'])) # 22Mendekode Teks (LeetCode 394)
LeetCode 394 'Dekodekan Teks': jika diberikan teks berkode seperti 3[a2[c]], kembangkan menjadi accaccacc. Gunakan dua tumpukan: satu untuk jumlah pengulangan dan satu untuk teks yang telah diakumulasikan. Saat menemukan digit, bentuk bilangan lengkapnya. Saat menemukan [, masukkan teks dan jumlah saat ini ke tumpukan. Saat menemukan ], keluarkan keduanya lalu ulangi segmen saat ini. Saat menemukan huruf, tambahkan huruf tersebut ke teks saat ini.
def decodeString(s):
count_stack = []
str_stack = []
current_str = ''
current_num = 0
for ch in s:
if ch.isdigit():
current_num = current_num * 10 + int(ch)
elif ch == '[':
count_stack.append(current_num)
str_stack.append(current_str)
current_str = ''
current_num = 0
elif ch == ']':
repeats = count_stack.pop()
current_str = str_stack.pop() + current_str * repeats
else:
current_str += ch
return current_str
print(decodeString('3[a]2[bc]')) # 'aaabcbc'
print(decodeString('3[a2[c]]')) # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'Suhu Harian (Pratinjau Tumpukan Monoton)
LeetCode 739 'Suhu Harian': untuk setiap hari, temukan berapa hari yang diperlukan hingga suhu yang lebih hangat. Pendekatan coba semua kemungkinan memerlukan O(n²). Dengan tumpukan, telusuri suhu; untuk setiap hari, keluarkan semua entri tumpukan (indeks hari) yang suhunya lebih rendah daripada suhu hari ini. Jawaban untuk hari-hari yang dikeluarkan tersebut adalah selisih antara hari ini dan hari yang dikeluarkan. Masukkan hari ini ke tumpukan. Entri yang tersisa tidak pernah menemukan hari yang lebih hangat — jawabannya adalah 0.
def dailyTemperatures(temps):
result = [0] * len(temps)
stack = [] # stores indices
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]Stack untuk Penelusuran DFS
Tumpukan pemanggilan dalam DFS rekursif dapat digantikan dengan tumpukan eksplisit sehingga algoritmanya menjadi iteratif. Masukkan akar dengan push; selama tumpukan tidak kosong, keluarkan sebuah simpul dengan pop, proses simpul tersebut, lalu masukkan anak-anaknya (kanan sebelum kiri untuk pemrosesan dari kiri ke kanan). DFS iteratif ini berperilaku sama dengan DFS rekursif, tetapi menghindari batas rekursi Python untuk pohon yang dalam.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_iterative(root):
if not root:
return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right) # push right first
if node.left:
stack.append(node.left) # so left is processed first
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Kompleksitas Waktu dan Ruang
Semua operasi tumpukan (push, pop, peek, isEmpty) memerlukan O(1) secara diamortisasi. Membangun tumpukan yang berisi n elemen memerlukan O(n). Ruang yang digunakan adalah O(n) pada kasus terburuk, ketika semua elemen tersimpan. Untuk masalah yang menggunakan tumpukan monoton, setiap elemen dimasukkan dan dikeluarkan paling banyak satu kali, sehingga total waktu di seluruh iterasi adalah O(n) — bukan O(n²) seperti yang mungkin disiratkan oleh analisis naif terhadap perulangan luar.
# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total
def count_ops(n):
pushes = pops = 0
stack = []
for i in range(n):
while stack and stack[-1] < i: # simulated decreasing condition
stack.pop()
pops += 1
stack.append(i)
pushes += 1
return pushes, pops
p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}') # <= 2000Persegi Panjang Terbesar dalam Histogram (Pratinjau)
LeetCode 84 'Persegi Panjang Terbesar dalam Histogram' adalah masalah tumpukan klasik yang paling sulit. Untuk setiap batang, persegi panjang yang dapat berporos pada batang tersebut memanjang ke kiri hingga ditemukan batang yang lebih pendek, dan ke kanan hingga ditemukan batang yang lebih pendek. Tumpukan monoton melacak indeks batang dalam urutan tinggi yang meningkat. Saat batang yang lebih pendek ditemukan, keluarkan batang dari tumpukan dan hitung persegi panjang menggunakan tinggi batang yang dikeluarkan. Tumpukan tersebut memberikan batas kiri dan kanan dalam O(1) untuk setiap operasi pop.
def largestRectangleArea(heights):
stack = [] # indices, increasing heights
result = 0
heights = heights + [0] # sentinel forces all pops
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2,1,5,6,2,3])) # 10
print(largestRectangleArea([2,4])) # 4Strategi Wawancara untuk Masalah Stack
Masalah tumpukan sering menyamarkan dirinya sebagai 'memproses dari bagian dalam ke luar' atau 'menemukan elemen yang lebih besar atau lebih kecil berikutnya'. Beberapa tanda bahwa tumpukan mungkin membantu: Anda memerlukan elemen yang paling baru dilihat, Anda mencocokkan pasangan (tanda kurung, tag), atau Anda menginginkan O(n) pada masalah yang secara naif memerlukan perulangan bersarang O(n²). Tumpukan monoton khususnya mengubah pencarian 'elemen yang lebih besar atau lebih kecil terdekat untuk setiap elemen' dari O(n²) menjadi O(n).
Dalam wawancara, nyatakan invarian tumpukan Anda dengan jelas: 'Saya akan mempertahankan tumpukan indeks dalam urutan tinggi menurun.'
Pemeriksaan Singkat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari: list Python mengimplementasikan push/pop/peek O(1) sehingga ideal sebagai tumpukan, tanda kurung valid dan tumpukan minimum adalah dua masalah wawancara tumpukan yang paling umum, dan tumpukan monoton menyelesaikan masalah elemen yang lebih besar berikutnya dalam O(n) dengan memasukkan dan mengeluarkan setiap elemen paling banyak satu kali. Selanjutnya kita akan membangun antrean menggunakan deque Python dan menyelesaikan masalah maksimum jendela geser.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Implementasi Stack dan Penerapannya” gratis?
Ya — teks lengkap “Implementasi Stack dan Penerapannya” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Implementasi Stack dan Penerapannya”?
Implementasikan stack dengan push/pop/peek, lalu selesaikan valid-parentheses, min-stack, dan evaluasi notasi reverse-polish. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Implementasi Stack dan Penerapannya” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Implementasi Stack dan Penerapannya
- Implementasi Queue dan Deque
- Pola Stack Monotonik
- Simulasi Saling Menggunakan Stack dan Queue