Lewati ke konten utama

Stack Python: Menerapkan Struktur Data LIFO

Pelajari prinsip LIFO, cara mengimplementasikan stack di Python menggunakan list, deque, dan LifoDeque, serta menerapkannya untuk sistem undo/redo atau penelusuran graf.
· 15 mnt Baca

Jelajahi bersama AI

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.

prinsip LIFO stack python

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 python vs list vs queue

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.

operasi stack
python: Push, pop, peek

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 element
print(stack[-1])
[10, 20, 30]
30
[10, 20]
20

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 accessing
if stack:
    top = stack.pop()
else:
    print("Stack is empty")
Stack Underflow: cannot pop from an empty stack
Stack Underflow: cannot peek at an empty stack
Stack is empty

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 element
print(stack[-1])
deque([10, 20, 30])
30
deque([10, 20])
20

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")
Stack Underflow: cannot pop from an empty deque stack

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())
3
30
2

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 IndexError
try:
    stack.get(block=False)
except Empty:
    print("Stack is empty — no items to get")
Stack is empty — no items to get

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

def is_balanced(expression):
    stack = deque()
    matching = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack:
                return False  # closing bracket with nothing to match
            if stack.pop() != matching[char]:
                return False  # mismatched pair
    
    return len(stack) == 0  # stack should be empty if balanced

# Test cases
print(is_balanced("([])")) 
print(is_balanced("{[()]}"))
print(is_balanced("([)]"))
print(is_balanced(