Pelajari prinsip LIFO, cara mengimplementasikan stack di Python menggunakan list, deque, dan LifoDeque, serta menerapkannya untuk sistem undo/redo atau penelusuran graf.
Setiap kali Anda menekan Ctrl+Z untuk membatalkan kesalahan, mengeklik tombol kembali di browser, atau melihat fungsi rekursif mengurai hasilnya, Anda sedang mengandalkan sebuah stack. Karena begitu tertanam dalam perangkat lunak yang Anda gunakan setiap hari, Anda sering berinteraksi dengan Stack tanpa menyadarinya.
Pada artikel ini, kita akan melihat apa itu stack, logika inti di balik stack, membandingkan berbagai strategi implementasi menggunakan pustaka bawaan Python, dan menerapkannya untuk menyelesaikan masalah algoritmik.
Saya merekomendasikan untuk mengikuti kursus kami tentang Writing Efficient Python Code agar pengetahuan struktur data Anda selaras dengan praktik terbaik performa, dan tetap menyimpan Python Basics Cheat Sheet sebagai referensi cepat.
Apa Itu Stack di Python?
Sebelum melihat kode, penting untuk memahami fondasi konseptual yang membuat stack Python menjadi alat yang begitu kuat. Mari kita lihat prinsip inti di balik stack dan bagaimana perbedaannya dengan struktur data umum lainnya.
Struktur data LIFO
Stack adalah struktur data linear yang mengikuti prinsip Last-In-First-Out (LIFO). Artinya, elemen yang paling terakhir ditambahkan akan selalu menjadi yang pertama dihapus. Bayangkan seperti tumpukan piring di kafetaria. Anda menaruh piring baru di atas dan selalu mengambil piring teratas terlebih dahulu. Anda tidak pernah menarik piring dari tengah atau bawah. Akses sepenuhnya dibatasi pada bagian atas.
Keterbatasan tunggal ini, akses hanya dari atas, adalah yang memberikan prediktabilitas dan efisiensi pada stack. Setiap elemen masuk dan keluar melalui ujung yang sama, sehingga operasi tetap sederhana dan cepat.
Satu hal yang perlu dicatat sejak awal adalah Python tidak menyediakan tipe stack primitif khusus seperti beberapa bahasa lain. Tidak ada kata kunci stack atau kelas bawaan. Sebagai gantinya, Python menawarkan alternatif bawaan yang andal seperta list, collections.deque, dan queue.LifoQueue yang semuanya dapat berperilaku sebagai stack. Kita akan melihat masing-masing implementasi ini secara detail nanti di artikel.
Stack vs Struktur Data Lain
Memahami apa itu stack menjadi jauh lebih jelas ketika Anda melihat apa yang bukan. Dua struktur yang paling sering dibandingkan dengan stack adalah queue dan list Python standar.
Stack vs queue
Queue mengikuti prinsip First-In-First-Out (FIFO), kebalikan dari stack. Pada queue, elemen ditambahkan di belakang dan dihapus dari depan, seperti antrean orang menunggu di loket tiket. Stack dan queue sama-sama linear dan sama-sama membatasi cara Anda mengakses elemen, tetapi melakukannya ke arah yang berlawanan.
Memilih yang salah dapat diam-diam merusak logika algoritma. Misalnya, mengganti stack dengan queue dalam depth-first search akan mengubahnya menjadi breadth-first search, menghasilkan keluaran yang sama sekali berbeda.
Stack vs list
List Python standar, di sisi lain, menyediakan akses acak. Anda dapat membaca, menyisipkan, atau menghapus elemen pada indeks mana pun menggunakan operasi seperti my_list[3] atau my_list.insert(2, value). Fleksibilitas ini berguna dalam banyak konteks, tetapi juga berarti tidak ada yang mencegah Anda secara tidak sengaja mengakses atau memodifikasi elemen di tengah struktur.
Saat Anda mengimplementasikan algoritma yang bergantung pada urutan LIFO yang ketat, seperti backtracking, parsing sintaks, atau fungsi undo, sifat list yang tidak dibatasi dapat memperkenalkan bug halus.
Inilah tepatnya mengapa pola akses terbatas dari sebuah stack adalah fitur, bukan keterbatasan. Dengan hanya mengizinkan interaksi dengan elemen teratas, stack Python menegakkan ketepatan secara desain. Anda tidak bisa secara tidak sengaja mengambil dari ujung yang salah atau menimpa elemen yang terkubur dalam struktur.
Dalam perancangan algoritma, batasan seperti ini yang menjaga logika Anda tetap bersih dan kode Anda dapat diprediksi.
Operasi Inti Stack dan Kompleksitas Waktu
Sekarang kita memahami apa itu stack Python dan bagaimana perbedaannya dari struktur lain, mari kita lihat operasi dasar yang didukung setiap stack dan menganalisis efisiensi masing-masing.
Operasi standar stack
Setiap implementasi stack didasarkan pada seperangkat kecil operasi standar, terlepas dari bahasa pemrograman. Ini adalah blok pembangun yang akan Anda gunakan setiap kali bekerja dengan stack.
Push menambahkan elemen ke bagian atas stack. Jika stack berisi [A, B] dan Anda melakukan push C, stack menjadi [A, B, C], dengan C sekarang berada di atas.
Pop menghapus dan mengembalikan elemen yang saat ini berada di atas. Melanjutkan contoh di atas, melakukan pop dari [A, B, C] mengembalikan C dan menyisakan stack sebagai [A, B].
Peek (kadang disebut top) memungkinkan Anda melihat elemen teratas tanpa menghapusnya. Ini berguna ketika logika Anda perlu memeriksa nilai teratas saat ini sebelum memutuskan apakah akan melakukan pop, pola yang sering muncul dalam parsing ekspresi dan masalah tanda kurung seimbang.
Selain tiga operasi inti tersebut, dua metode pembantu penting untuk menulis kode stack yang aman dan bebas galat:
is_empty() memeriksa apakah stack berisi elemen. Memanggil pop atau peek pada stack kosong adalah sumber umum error saat runtime, jadi memeriksa kekosongan terlebih dahulu adalah kebiasaan pemrograman defensif yang sebaiknya Anda bangun sejak awal.
size() mengembalikan jumlah elemen saat ini dalam stack. Ini membantu saat Anda perlu melacak seberapa dalam rekursi berjalan atau berapa banyak item yang masih harus diproses.
Terakhir, layak untuk mendefinisikan istilah yang akan Anda temui dalam buku teks dan wawancara: Stack Underflow. Ini adalah kondisi error yang terjadi saat Anda mencoba melakukan pop atau peek dari stack kosong. Tidak ada yang dapat dihapus atau dilihat, sehingga operasi tidak valid.
Pengecualian atau perilaku persis yang dihasilkan bergantung pada implementasi. Kita akan melihat bagaimana Python menanganinya secara konkret saat membahas list, deque, dan LifoQueue di bagian berikutnya.
Menganalisis kompleksitas
Salah satu alasan terbesar stack banyak digunakan dalam algoritma adalah efisiensinya. Mari kita uraikan kompleksitas waktu dan ruang dari setiap operasi.
Push adalah O(1). Dalam implementasi stack yang efisien, menambahkan elemen ke atas adalah operasi waktu konstan. Stack tidak perlu menggeser atau menata ulang elemen yang ada. Cukup menaruh item baru di akhir. Ini berlaku untuk collections.deque dan, dalam kasus amortisasi, list bawaan Python.
Pop adalah O(1). Menghapus elemen teratas sama cepatnya. Stack mengakses posisi terakhir secara langsung, mengembalikan nilai, dan mengurangi pelacak ukuran internalnya. Lagi-lagi, tidak perlu menggeser elemen lain.
Peek adalah O(1). Melihat elemen teratas tanpa menghapusnya adalah pengaksesan indeks langsung, sehingga juga waktu konstan.
Pencarian adalah O(n). Di sinilah stack memperlihatkan kompromi yang disengaja. Jika Anda perlu mengetahui apakah suatu nilai tertentu ada di suatu tempat dalam stack, Anda tidak punya pilihan selain memindai semua elemen n dari atas ke bawah.
Stack tidak dirancang untuk pencarian sewenang-wenang. Mereka mengorbankan kemampuan pencarian demi push dan pop yang cepat dan dapat diprediksi. Jika kasus penggunaan Anda memerlukan pencarian yang sering, struktur data lain, seperti set atau dictionary, akan lebih cocok.
Kompleksitas ruang adalah O(n). Stack yang menampung n elemen memerlukan memori yang proporsional dengan n. Tidak ada overhead tersembunyi selain yang diperlukan untuk menyimpan elemen itu sendiri, ditambah konstanta kecil untuk pembukuan internal struktur.
Berikut ringkasan singkatnya:
Operasi
Kompleksitas Waktu
Catatan
Push
O(1)
Waktu konstan. Amortisasi O(1) untuk Python list
Pop
O(1)
Waktu konstan
Peek
O(1)
Akses langsung ke elemen teratas
Pencarian
O(n)
Harus memindai semua elemen
Ruang
O(n)
Linear terhadap jumlah elemen yang disimpan
Inti yang perlu diingat adalah stack Python dioptimalkan untuk penyisipan dan penghapusan cepat di satu ujung. Selama Anda menggunakannya sesuai tujuannya, seperti mengelola akses berurutan LIFO, performanya sangat baik. Begitu Anda sering melakukan pencarian dalam stack, itu menjadi sinyal untuk mempertimbangkan ulang pilihan struktur data.
Implementasi Stack di Python
Dengan teori dan analisis kompleksitas di belakang kita, saatnya menulis kode nyata. Python menawarkan tiga cara utama untuk mengimplementasikan stack, masing-masing dengan kelebihan dan kompromi. Mari kita telusuri ketiganya dan lihat cara memilih yang paling sesuai dengan kasus penggunaan kita.
Stack Python menggunakan list bawaan
Cara paling langsung untuk membuat stack Python adalah dengan list bawaan. Karena list adalah array dinamis yang mendukung penambahan dan penghapusan elemen dari akhir, ini sangat selaras dengan perilaku stack.
Metode .append() berfungsi sebagai push, dan .pop() tanpa argumen menghapus dan mengembalikan elemen terakhir. Mari kita lihat dengan contoh kode berikut:
# Creating a stack using a Python list
stack =[]# Push elements
stack.append(10)
stack.append(20)
stack.append(30)print(stack)# Pop the top element
top = stack.pop()print(top)print(stack)# Peek at the top elementprint(stack[-1])Didukung oleh
Ini berfungsi dengan baik, tetapi Anda perlu menangani kasus stack kosong dengan hati-hati. Di Python, .pop() dan stack[-1] sama-sama memunculkan IndexError saat list kosong. Inilah cara Python menampilkan kondisi Stack Underflow yang kita definisikan sebelumnya.
Praktik terbaik adalah membungkus pemanggilan ini dalam blok try/except atau memeriksa kekosongan sebelum mengakses elemen atas, seperti pada contoh berikut:
# Handling Stack Underflow with try/except
stack =[]try:
stack.pop()except IndexError:print("Stack Underflow: cannot pop from an empty stack")try:
top = stack[-1]except IndexError:print("Stack Underflow: cannot peek at an empty stack")# Alternatively, check before accessingif stack:
top = stack.pop()else:print("Stack is empty")Didukung oleh
Stack Underflow: cannot pop from an empty stack
Stack Underflow: cannot peek at an empty stack
Stack is emptyDidukung oleh
Ada satu nuansa performa yang perlu dipahami. List Python didukung oleh array dinamis. Saat Anda memanggil .append(), operasinya biasanya seketika O(1). Namun, ketika array internal kehabisan ruang yang sudah dialokasikan, Python harus mengalokasikan blok memori baru yang lebih besar dan menyalin semua elemen yang ada ke sana.
Realokasi sesekali ini membuat .append() menjadi operasi O(1) teramortisasi alih-alih O(1) murni. Dalam praktiknya, penundaan ini jarang dan singkat, tetapi dalam aplikasi sensitif latensi atau waktu nyata, ketidakpastian ini bisa berarti.
Terlepas dari catatan ini, .append() dan .pop() pada list adalah pendekatan yang disukai untuk sebagian besar tugas stack sederhana. Tanpa perlu impor, sintaks yang familier, dan tingkat keterbiasaan pengembang yang luas menjadikannya pilihan default yang baik, terutama untuk scripting, prototyping, dan masalah wawancara di mana kesederhanaan penting.
Stack Python menggunakan collections.deque
Jika Anda membutuhkan performa O(1) yang konsisten tanpa lag realokasi sesekali, collections.deque adalah peningkatan yang direkomendasikan. Namanya berarti "double-ended queue," tetapi ini bekerja sangat baik sebagai stack Python berperforma tinggi. Contoh sebelumnya terlihat seperti ini dengan sintaks deque:
from collections import deque
# Creating a stack using deque
stack = deque()# Push elements
stack.append(10)
stack.append(20)
stack.append(30)print(stack)# Pop the top element
top = stack.pop()print(top)print(stack)# Peek at the top elementprint(stack[-1])Didukung oleh
deque([10, 20, 30])
30
deque([10, 20])
20Didukung oleh
Perhatikan bahwa antarmukanya identik dengan pendekatan berbasis list. .append(), .pop(), dan [-1] semuanya bekerja dengan cara yang sama. Perilaku IndexError saat akses kosong juga tidak berubah, jadi kode penanganan error Anda tidak perlu diubah:
from collections import deque
stack = deque()try:
stack.pop()except IndexError:print("Stack Underflow: cannot pop from an empty deque stack")Didukung oleh
Stack Underflow: cannot pop from an empty deque stackDidukung oleh
Perbedaan kritisnya ada di balik layar. deque diimplementasikan sebagai daftar berantai ganda dari blok berukuran tetap, bukan satu array. Ini berarti tidak pernah perlu realokasi dan menyalin seluruh struktur saat tumbuh.
Setiap .append() dan .pop() adalah operasi O(1) sejati dan terjamin, bukan amortisasi, tetapi konsisten. Untuk pekerjaan berat algoritmik di mana Anda melakukan push dan pop ribuan atau jutaan kali, konsistensi ini berdampak besar.
Stack Python menggunakan queue.LifoQueue
Pustaka standar Python juga menyertakan queue.LifoQueue, implementasi stack yang dirancang khusus untuk program multi-thread. "LIFO" pada namanya menegaskan bahwa ia mengikuti urutan Last-In-First-Out, tetapi antarmuka dan perilakunya cukup berbeda dari dua pendekatan sebelumnya. Mari kita lihat dengan contoh kode:
from queue import LifoQueue
# Creating a thread-safe stack
stack = LifoQueue()# Push elements using .put()
stack.put(10)
stack.put(20)
stack.put(30)print(stack.qsize())# Pop the top element using .get()
top = stack.get()print(top)print(stack.qsize())Didukung oleh
Hal pertama yang perlu diperhatikan adalah perubahan sintaks. Push menjadi .put(), dan pop menjadi .get(). Penamaan ini berasal dari pola desain producer-consumer modul queue, di mana satu thread "meletakkan" item dan thread lain "mengambilnya".
Ada dua perbedaan perilaku penting yang perlu diperhatikan.
Pertama, LifoQueue tidak memiliki metode peek yang aman. Tidak ada cara bawaan untuk melihat elemen teratas tanpa menghapusnya. Anda bisa mengakses atribut internal, tetapi melakukannya dalam konteks multi-thread bertentangan dengan tujuan menggunakan kelas thread-safe dan berisiko menimbulkan race condition.
Kedua, LifoQueue tidak memunculkan IndexError saat Anda mencoba mengambil dari stack kosong. Secara default, .get() memblokir. Ini menghentikan thread pemanggil dan menunggu tanpa batas hingga thread lain meletakkan item ke stack. Jika Anda menginginkan perilaku non-blocking, Anda bisa mengoper block=False, yang akan memunculkan pengecualian queue.Empty sebagai gantinya. Mari lihat contohnya:
from queue import LifoQueue, Empty
stack = LifoQueue()# Non-blocking get raises Empty, not IndexErrortry:
stack.get(block=False)except Empty:print("Stack is empty — no items to get")Didukung oleh
Karena mekanisme penguncian internal yang membuat LifoQueue thread-safe, operasinya memiliki overhead lebih besar dibanding list atau deque. Ini menjadikannya pilihan yang buruk untuk kode single-thread. Gunakan LifoQueue hanya saat Anda memiliki skenario multi-thread alami dengan akses bersamaan, dan gunakan deque atau list untuk situasi lainnya.
Memilih implementasi stack yang tepat di Python
Dengan tiga opsi yang tersedia, berikut perbandingan berdampingan untuk memandu keputusan Anda:
Fitur
list
collections.deque
queue.LifoQueue
Perlu impor
Tidak
Ya (collections)
Ya (queue)
Metode push
.append()
.append()
.put()
Metode pop
.pop()
.pop()
.get()
Metode peek
stack[-1]
stack[-1]
Tidak ada metode aman
Error saat kosong
IndexError
IndexError
Memblokir atau Empty
Kecepatan Push/Pop
Amortisasi O(1)
O(1) sejati
O(1) dengan overhead lock
Thread-safe
Tidak
Tidak
Ya
Terbaik untuk
Skrip sederhana, prototyping
Algoritme, kode kritis performa
Producer-consumer multi-thread
Berikut kerangka keputusan saya untuk memilih implementasi terbaik:
Gunakan list saat Anda butuh stack cepat tanpa impor, seperti dalam skrip, notebook, dan whiteboard wawancara.
Gunakan collections.deque saat menulis kode algoritmik, memproses dataset besar, atau membangun apa pun yang menuntut performa.
Gunakan queue.LifoQueue hanya saat Anda memiliki skenario multi-thread alami dengan akses bersamaan.
Anda juga mungkin menemukan tutorial yang mengimplementasikan stack Python dari nol menggunakan kelas linked list kustom, di mana setiap node menyimpan nilai dan pointer ke node di bawahnya. Menurut saya, itu jelas latihan edukatif yang berharga yang dapat memperdalam pemahaman Anda tentang cara kerja internal stack dan bagaimana referensi memori saling terhubung.
Namun, dalam kode Python produksi, stack linked list hampir selalu lebih lambat daripada deque karena overhead pembuatan objek node individual. Untuk pekerjaan Python dunia nyata, collections.deque memberi Anda kombinasi terbaik antara kecepatan, kejelasan, dan keandalan.
Aplikasi Stack di Python
Memahami cara mengimplementasikan stack Python hanyalah separuh gambaran. Nilai nyata stack menjadi jelas ketika Anda melihatnya menyelesaikan masalah yang akan jauh lebih kompleks tanpa pengurutan LIFO. Mari kita lihat tiga aplikasi klasik yang terus muncul dalam wawancara coding, sistem perangkat lunak, dan perancangan algoritma.
Memeriksa tanda kurung seimbang
Masalah tanda kurung seimbang adalah salah satu pertanyaan stack yang paling sering ditanyakan dalam wawancara teknis. Diberikan string yang berisi kurung, seperti (), [], dan {}, Anda perlu menentukan apakah setiap kurung buka memiliki kurung tutup yang sesuai dalam urutan yang benar.
Logikanya sangat cocok dengan stack. Saat Anda memindai string dari kiri ke kanan, dorong setiap kurung buka ke stack. Saat Anda menemukan kurung tutup, lakukan pop pada elemen teratas stack dan periksa apakah cocok.
Jika stack kosong saat Anda mencoba pop, atau jika kurung yang dipop tidak cocok, string tidak seimbang. Setelah memproses seluruh string, stack harus kosong. Setiap kurung buka yang tersisa berarti ada yang belum ditutup. Mari lihat praktiknya:
from collections import deque
defis_balanced(expression):
stack = deque()
matching ={')':'(',']':'[','}':'{'}for char in expression:if char in'([{':
stack.append(char)elif char in')]}':ifnot stack:returnFalse# closing bracket with nothing to matchif stack.pop()!= matching[char]:returnFalse# mismatched pairreturnlen(stack)==0# stack should be empty if balanced# Test casesprint(is_balanced("([])"))print(is_balanced("{[()]}"))print(is_balanced("([)]"))print(is_balanced(
Setiap kali Anda menekan Ctrl+Z untuk membatalkan kesalahan, mengeklik tombol kembali di browser, atau melihat fungsi rekursif mengurai hasilnya, Anda sedang mengandalkan sebuah stack. Karena begitu tertanam dalam perangkat lunak yang Anda gunakan setiap hari, Anda sering berinteraksi dengan Stack tanpa menyadarinya.
Pada artikel ini, kita akan melihat apa itu stack, logika inti di balik stack, membandingkan berbagai strategi implementasi menggunakan pustaka bawaan Python, dan menerapkannya untuk menyelesaikan masalah algoritmik.
Saya merekomendasikan untuk mengikuti kursus kami tentang Writing Efficient Python Code agar pengetahuan struktur data Anda selaras dengan praktik terbaik performa, dan tetap menyimpan Python Basics Cheat Sheet sebagai referensi cepat.
Apa Itu Stack di Python?
Sebelum melihat kode, penting untuk memahami fondasi konseptual yang membuat stack Python menjadi alat yang begitu kuat. Mari kita lihat prinsip inti di balik stack dan bagaimana perbedaannya dengan struktur data umum lainnya.
Struktur data LIFO
Stack adalah struktur data linear yang mengikuti prinsip Last-In-First-Out (LIFO). Artinya, elemen yang paling terakhir ditambahkan akan selalu menjadi yang pertama dihapus. Bayangkan seperti tumpukan piring di kafetaria. Anda menaruh piring baru di atas dan selalu mengambil piring teratas terlebih dahulu. Anda tidak pernah menarik piring dari tengah atau bawah. Akses sepenuhnya dibatasi pada bagian atas.
Keterbatasan tunggal ini, akses hanya dari atas, adalah yang memberikan prediktabilitas dan efisiensi pada stack. Setiap elemen masuk dan keluar melalui ujung yang sama, sehingga operasi tetap sederhana dan cepat.
Satu hal yang perlu dicatat sejak awal adalah Python tidak menyediakan tipe stack primitif khusus seperti beberapa bahasa lain. Tidak ada kata kunci
stackatau kelas bawaan. Sebagai gantinya, Python menawarkan alternatif bawaan yang andal seperta list,collections.deque, danqueue.LifoQueueyang semuanya dapat berperilaku sebagai stack. Kita akan melihat masing-masing implementasi ini secara detail nanti di artikel.Stack vs Struktur Data Lain
Memahami apa itu stack menjadi jauh lebih jelas ketika Anda melihat apa yang bukan. Dua struktur yang paling sering dibandingkan dengan stack adalah queue dan list Python standar.
Stack vs queue
Queue mengikuti prinsip First-In-First-Out (FIFO), kebalikan dari stack. Pada queue, elemen ditambahkan di belakang dan dihapus dari depan, seperti antrean orang menunggu di loket tiket. Stack dan queue sama-sama linear dan sama-sama membatasi cara Anda mengakses elemen, tetapi melakukannya ke arah yang berlawanan.
Memilih yang salah dapat diam-diam merusak logika algoritma. Misalnya, mengganti stack dengan queue dalam depth-first search akan mengubahnya menjadi breadth-first search, menghasilkan keluaran yang sama sekali berbeda.
Stack vs list
List Python standar, di sisi lain, menyediakan akses acak. Anda dapat membaca, menyisipkan, atau menghapus elemen pada indeks mana pun menggunakan operasi seperti
my_list[3]ataumy_list.insert(2, value). Fleksibilitas ini berguna dalam banyak konteks, tetapi juga berarti tidak ada yang mencegah Anda secara tidak sengaja mengakses atau memodifikasi elemen di tengah struktur.Saat Anda mengimplementasikan algoritma yang bergantung pada urutan LIFO yang ketat, seperti backtracking, parsing sintaks, atau fungsi undo, sifat list yang tidak dibatasi dapat memperkenalkan bug halus.
Inilah tepatnya mengapa pola akses terbatas dari sebuah stack adalah fitur, bukan keterbatasan. Dengan hanya mengizinkan interaksi dengan elemen teratas, stack Python menegakkan ketepatan secara desain. Anda tidak bisa secara tidak sengaja mengambil dari ujung yang salah atau menimpa elemen yang terkubur dalam struktur.
Dalam perancangan algoritma, batasan seperti ini yang menjaga logika Anda tetap bersih dan kode Anda dapat diprediksi.
Operasi Inti Stack dan Kompleksitas Waktu
Sekarang kita memahami apa itu stack Python dan bagaimana perbedaannya dari struktur lain, mari kita lihat operasi dasar yang didukung setiap stack dan menganalisis efisiensi masing-masing.
Operasi standar stack
Setiap implementasi stack didasarkan pada seperangkat kecil operasi standar, terlepas dari bahasa pemrograman. Ini adalah blok pembangun yang akan Anda gunakan setiap kali bekerja dengan stack.
Push menambahkan elemen ke bagian atas stack. Jika stack berisi
[A, B]dan Anda melakukan pushC, stack menjadi[A, B, C], denganCsekarang berada di atas.Pop menghapus dan mengembalikan elemen yang saat ini berada di atas. Melanjutkan contoh di atas, melakukan pop dari
[A, B, C]mengembalikanCdan menyisakan stack sebagai[A, B].Peek (kadang disebut top) memungkinkan Anda melihat elemen teratas tanpa menghapusnya. Ini berguna ketika logika Anda perlu memeriksa nilai teratas saat ini sebelum memutuskan apakah akan melakukan pop, pola yang sering muncul dalam parsing ekspresi dan masalah tanda kurung seimbang.
Selain tiga operasi inti tersebut, dua metode pembantu penting untuk menulis kode stack yang aman dan bebas galat:
is_empty()memeriksa apakah stack berisi elemen. Memanggil pop atau peek pada stack kosong adalah sumber umum error saat runtime, jadi memeriksa kekosongan terlebih dahulu adalah kebiasaan pemrograman defensif yang sebaiknya Anda bangun sejak awal.size()mengembalikan jumlah elemen saat ini dalam stack. Ini membantu saat Anda perlu melacak seberapa dalam rekursi berjalan atau berapa banyak item yang masih harus diproses.Terakhir, layak untuk mendefinisikan istilah yang akan Anda temui dalam buku teks dan wawancara: Stack Underflow. Ini adalah kondisi error yang terjadi saat Anda mencoba melakukan pop atau peek dari stack kosong. Tidak ada yang dapat dihapus atau dilihat, sehingga operasi tidak valid.
Pengecualian atau perilaku persis yang dihasilkan bergantung pada implementasi. Kita akan melihat bagaimana Python menanganinya secara konkret saat membahas
list,deque, danLifoQueuedi bagian berikutnya.Menganalisis kompleksitas
Salah satu alasan terbesar stack banyak digunakan dalam algoritma adalah efisiensinya. Mari kita uraikan kompleksitas waktu dan ruang dari setiap operasi.
Push adalah O(1). Dalam implementasi stack yang efisien, menambahkan elemen ke atas adalah operasi waktu konstan. Stack tidak perlu menggeser atau menata ulang elemen yang ada. Cukup menaruh item baru di akhir. Ini berlaku untuk
collections.dequedan, dalam kasus amortisasi,listbawaan Python.Pop adalah O(1). Menghapus elemen teratas sama cepatnya. Stack mengakses posisi terakhir secara langsung, mengembalikan nilai, dan mengurangi pelacak ukuran internalnya. Lagi-lagi, tidak perlu menggeser elemen lain.
Peek adalah O(1). Melihat elemen teratas tanpa menghapusnya adalah pengaksesan indeks langsung, sehingga juga waktu konstan.
Pencarian adalah O(n). Di sinilah stack memperlihatkan kompromi yang disengaja. Jika Anda perlu mengetahui apakah suatu nilai tertentu ada di suatu tempat dalam stack, Anda tidak punya pilihan selain memindai semua elemen
ndari atas ke bawah.Stack tidak dirancang untuk pencarian sewenang-wenang. Mereka mengorbankan kemampuan pencarian demi push dan pop yang cepat dan dapat diprediksi. Jika kasus penggunaan Anda memerlukan pencarian yang sering, struktur data lain, seperti set atau dictionary, akan lebih cocok.
Kompleksitas ruang adalah O(n). Stack yang menampung
nelemen memerlukan memori yang proporsional dengann. Tidak ada overhead tersembunyi selain yang diperlukan untuk menyimpan elemen itu sendiri, ditambah konstanta kecil untuk pembukuan internal struktur.Berikut ringkasan singkatnya:
Operasi
Kompleksitas Waktu
Catatan
Push
O(1)
Waktu konstan. Amortisasi O(1) untuk Python list
Pop
O(1)
Waktu konstan
Peek
O(1)
Akses langsung ke elemen teratas
Pencarian
O(n)
Harus memindai semua elemen
Ruang
O(n)
Linear terhadap jumlah elemen yang disimpan
Inti yang perlu diingat adalah stack Python dioptimalkan untuk penyisipan dan penghapusan cepat di satu ujung. Selama Anda menggunakannya sesuai tujuannya, seperti mengelola akses berurutan LIFO, performanya sangat baik. Begitu Anda sering melakukan pencarian dalam stack, itu menjadi sinyal untuk mempertimbangkan ulang pilihan struktur data.
Implementasi Stack di Python
Dengan teori dan analisis kompleksitas di belakang kita, saatnya menulis kode nyata. Python menawarkan tiga cara utama untuk mengimplementasikan stack, masing-masing dengan kelebihan dan kompromi. Mari kita telusuri ketiganya dan lihat cara memilih yang paling sesuai dengan kasus penggunaan kita.
Stack Python menggunakan list bawaan
Cara paling langsung untuk membuat stack Python adalah dengan
listbawaan. Karena list adalah array dinamis yang mendukung penambahan dan penghapusan elemen dari akhir, ini sangat selaras dengan perilaku stack.Metode
.append()berfungsi sebagai push, dan.pop()tanpa argumen menghapus dan mengembalikan elemen terakhir. Mari kita lihat dengan contoh kode berikut:Ini berfungsi dengan baik, tetapi Anda perlu menangani kasus stack kosong dengan hati-hati. Di Python,
.pop()danstack[-1]sama-sama memunculkanIndexErrorsaat list kosong. Inilah cara Python menampilkan kondisi Stack Underflow yang kita definisikan sebelumnya.Praktik terbaik adalah membungkus pemanggilan ini dalam blok try/except atau memeriksa kekosongan sebelum mengakses elemen atas, seperti pada contoh berikut:
Ada satu nuansa performa yang perlu dipahami. List Python didukung oleh array dinamis. Saat Anda memanggil
.append(), operasinya biasanya seketika O(1). Namun, ketika array internal kehabisan ruang yang sudah dialokasikan, Python harus mengalokasikan blok memori baru yang lebih besar dan menyalin semua elemen yang ada ke sana.Realokasi sesekali ini membuat
.append()menjadi operasi O(1) teramortisasi alih-alih O(1) murni. Dalam praktiknya, penundaan ini jarang dan singkat, tetapi dalam aplikasi sensitif latensi atau waktu nyata, ketidakpastian ini bisa berarti.Terlepas dari catatan ini,
.append()dan.pop()pada list adalah pendekatan yang disukai untuk sebagian besar tugas stack sederhana. Tanpa perlu impor, sintaks yang familier, dan tingkat keterbiasaan pengembang yang luas menjadikannya pilihan default yang baik, terutama untuk scripting, prototyping, dan masalah wawancara di mana kesederhanaan penting.Stack Python menggunakan collections.deque
Jika Anda membutuhkan performa O(1) yang konsisten tanpa lag realokasi sesekali,
collections.dequeadalah peningkatan yang direkomendasikan. Namanya berarti "double-ended queue," tetapi ini bekerja sangat baik sebagai stack Python berperforma tinggi. Contoh sebelumnya terlihat seperti ini dengan sintaksdeque:Perhatikan bahwa antarmukanya identik dengan pendekatan berbasis list.
.append(),.pop(), dan[-1]semuanya bekerja dengan cara yang sama. PerilakuIndexErrorsaat akses kosong juga tidak berubah, jadi kode penanganan error Anda tidak perlu diubah:Perbedaan kritisnya ada di balik layar.
dequediimplementasikan sebagai daftar berantai ganda dari blok berukuran tetap, bukan satu array. Ini berarti tidak pernah perlu realokasi dan menyalin seluruh struktur saat tumbuh.Setiap
.append()dan.pop()adalah operasi O(1) sejati dan terjamin, bukan amortisasi, tetapi konsisten. Untuk pekerjaan berat algoritmik di mana Anda melakukan push dan pop ribuan atau jutaan kali, konsistensi ini berdampak besar.Stack Python menggunakan queue.LifoQueue
Pustaka standar Python juga menyertakan
queue.LifoQueue, implementasi stack yang dirancang khusus untuk program multi-thread. "LIFO" pada namanya menegaskan bahwa ia mengikuti urutan Last-In-First-Out, tetapi antarmuka dan perilakunya cukup berbeda dari dua pendekatan sebelumnya. Mari kita lihat dengan contoh kode:Hal pertama yang perlu diperhatikan adalah perubahan sintaks. Push menjadi
.put(), dan pop menjadi.get(). Penamaan ini berasal dari pola desain producer-consumer modulqueue, di mana satu thread "meletakkan" item dan thread lain "mengambilnya".Ada dua perbedaan perilaku penting yang perlu diperhatikan.
Pertama,
LifoQueuetidak memiliki metode peek yang aman. Tidak ada cara bawaan untuk melihat elemen teratas tanpa menghapusnya. Anda bisa mengakses atribut internal, tetapi melakukannya dalam konteks multi-thread bertentangan dengan tujuan menggunakan kelas thread-safe dan berisiko menimbulkan race condition.Kedua,
LifoQueuetidak memunculkanIndexErrorsaat Anda mencoba mengambil dari stack kosong. Secara default,.get()memblokir. Ini menghentikan thread pemanggil dan menunggu tanpa batas hingga thread lain meletakkan item ke stack. Jika Anda menginginkan perilaku non-blocking, Anda bisa mengoperblock=False, yang akan memunculkan pengecualianqueue.Emptysebagai gantinya. Mari lihat contohnya:Karena mekanisme penguncian internal yang membuat
LifoQueuethread-safe, operasinya memiliki overhead lebih besar dibandinglistataudeque. Ini menjadikannya pilihan yang buruk untuk kode single-thread. GunakanLifoQueuehanya saat Anda memiliki skenario multi-thread alami dengan akses bersamaan, dan gunakandequeataulistuntuk situasi lainnya.Memilih implementasi stack yang tepat di Python
Dengan tiga opsi yang tersedia, berikut perbandingan berdampingan untuk memandu keputusan Anda:
Fitur
listcollections.dequequeue.LifoQueuePerlu impor
Tidak
Ya (
collections)Ya (
queue)Metode push
.append().append().put()Metode pop
.pop().pop().get()Metode peek
stack[-1]stack[-1]Tidak ada metode aman
Error saat kosong
IndexErrorIndexErrorMemblokir atau
EmptyKecepatan Push/Pop
Amortisasi O(1)
O(1) sejati
O(1) dengan overhead lock
Thread-safe
Tidak
Tidak
Ya
Terbaik untuk
Skrip sederhana, prototyping
Algoritme, kode kritis performa
Producer-consumer multi-thread
Berikut kerangka keputusan saya untuk memilih implementasi terbaik:
Gunakan
listsaat Anda butuh stack cepat tanpa impor, seperti dalam skrip, notebook, dan whiteboard wawancara.Gunakan
collections.dequesaat menulis kode algoritmik, memproses dataset besar, atau membangun apa pun yang menuntut performa.Gunakan
queue.LifoQueuehanya saat Anda memiliki skenario multi-thread alami dengan akses bersamaan.Anda juga mungkin menemukan tutorial yang mengimplementasikan stack Python dari nol menggunakan kelas linked list kustom, di mana setiap node menyimpan nilai dan pointer ke node di bawahnya. Menurut saya, itu jelas latihan edukatif yang berharga yang dapat memperdalam pemahaman Anda tentang cara kerja internal stack dan bagaimana referensi memori saling terhubung.
Namun, dalam kode Python produksi, stack linked list hampir selalu lebih lambat daripada
dequekarena overhead pembuatan objek node individual. Untuk pekerjaan Python dunia nyata,collections.dequememberi Anda kombinasi terbaik antara kecepatan, kejelasan, dan keandalan.Aplikasi Stack di Python
Memahami cara mengimplementasikan stack Python hanyalah separuh gambaran. Nilai nyata stack menjadi jelas ketika Anda melihatnya menyelesaikan masalah yang akan jauh lebih kompleks tanpa pengurutan LIFO. Mari kita lihat tiga aplikasi klasik yang terus muncul dalam wawancara coding, sistem perangkat lunak, dan perancangan algoritma.
Memeriksa tanda kurung seimbang
Masalah tanda kurung seimbang adalah salah satu pertanyaan stack yang paling sering ditanyakan dalam wawancara teknis. Diberikan string yang berisi kurung, seperti
(),[], dan{}, Anda perlu menentukan apakah setiap kurung buka memiliki kurung tutup yang sesuai dalam urutan yang benar.Logikanya sangat cocok dengan stack. Saat Anda memindai string dari kiri ke kanan, dorong setiap kurung buka ke stack. Saat Anda menemukan kurung tutup, lakukan pop pada elemen teratas stack dan periksa apakah cocok.
Jika stack kosong saat Anda mencoba pop, atau jika kurung yang dipop tidak cocok, string tidak seimbang. Setelah memproses seluruh string, stack harus kosong. Setiap kurung buka yang tersisa berarti ada yang belum ditutup. Mari lihat praktiknya: