Stack Python: Menerapkan Struktur Data LIFO

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:

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:

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("(("))
print(is_balanced(""))

True
True
False
False
True

Mari kita telusuri "{[()]}" langkah demi langkah untuk melihat stack beraksi:

Stack kosong pada akhir, jadi ekspresinya seimbang.

Logika yang sama berlaku jauh melampaui masalah wawancara. Compiler dan interpreter menggunakannya untuk memvalidasi sintaks, memastikan setiap tag, kurung, atau delimiter pembuka dalam kode sumber memiliki pasangan yang benar. 

Jika Anda pernah melihat pesan SyntaxError: unexpected EOF di Python, Anda telah melihat bentuk pemeriksaan ini beraksi. Validator HTML, parser JSON, dan bahkan linter file konfigurasi semuanya mengandalkan variasi pendekatan berbasis stack ini.

Mengimplementasikan depth-first search (DFS)

Depth-first search adalah salah satu algoritme penelusuran graf yang mendasar, dan stack adalah struktur data yang menggerakkannya. Idenya sederhana. Mulai dari sebuah node, jelajahi sejauh mungkin di sepanjang satu cabang sebelum kembali untuk mencoba yang berikutnya. Sifat LIFO dari stack Python membuat perilaku "masuk dalam dulu" ini terjadi secara alami.

Sebagian besar kursus pengantar mengajarkan DFS menggunakan rekursi, di mana call stack secara implisit mengelola urutan penelusuran. Namun, pendekatan rekursif memiliki keterbatasan praktis. Batas rekursi bawaan Python adalah 1.000 frame. 

Untuk graf yang besar atau sangat bertingkat, ini menyebabkan RecursionError. Versi iteratif, yang menggunakan stack eksplisit, menghindari masalah ini dan memberi Anda kendali penuh atas penelusuran.

Mari kita lihat contoh kodenya. Kita akan melakukan DFS pada graf berikut:

from collections import deque

def dfs_iterative(graph, start):
    visited = set()
    stack = deque()
    stack.append(start)
    traversal_order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            # Push neighbors onto the stack
            # Reverse to maintain left-to-right order after LIFO popping
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return traversal_order

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(dfs_iterative(graph, 'A'))

['A', 'B', 'D', 'E', 'F', 'C']

Mari kita telusuri eksekusi untuk melihat bagaimana stack mengatur penelusuran:

Perhatikan bagaimana urutan LIFO memaksa algoritme untuk sepenuhnya mengeksplorasi cabang A → B → D dan A → B → E → F sebelum kembali untuk mengunjungi C. Inilah yang membedakan depth-first search dari breadth-first search, yang menggunakan queue dan menjelajahi semua tetangga pada kedalaman saat ini sebelum masuk lebih dalam. 

Pola DFS iteratif yang ditunjukkan di sini berfungsi untuk pohon, graf berarah, dan graf tak berarah. Ini juga menjadi dasar untuk algoritme lanjutan seperti topological sorting, deteksi siklus, dan pemecahan masalah labirin serta teka-teki.

Mengelola operasi undo/redo

Jika Anda pernah menggunakan editor teks, aplikasi menggambar, atau spreadsheet, Anda telah mengandalkan undo dan redo tanpa memikirkan cara kerjanya di bawah permukaan. Mekanismenya elegan, dan berjalan menggunakan tepat dua stack.

Sebuah undo stack menyimpan setiap aksi atau status saat pengguna melakukan perubahan. Ketika pengguna memicu undo, status saat ini dipop dari undo stack dan didorong ke redo stack.

Jika kemudian pengguna memicu redo, status dipop dari redo stack dan didorong kembali ke undo stack. Jika pengguna membuat perubahan baru setelah melakukan undo, redo stack dibersihkan. Anda tidak dapat melakukan redo sesuatu yang telah ditimpa oleh aksi baru. Mari kita lihat contoh kode:

from collections import deque

class TextEditor:
    def __init__(self):
        self.content = ""
        self.undo_stack = deque()
        self.redo_stack = deque()

    def type_text(self, text):
        """Record current state and apply new text."""
        self.undo_stack.append(self.content)
        self.content += text
        self.redo_stack.clear()  # new action invalidates redo history

    def undo(self):
        """Revert to the previous state."""
        if not self.undo_stack:
            print("Nothing to undo")
            return
        self.redo_stack.append(self.content)
        self.content = self.undo_stack.pop()

    def redo(self):
        """Re-apply the last undone action."""
        if not self.redo_stack:
            print("Nothing to redo")
            return
        self.undo_stack.append(self.content)
        self.content = self.redo_stack.pop()

    def show(self):
        print(f'Content: "{self.content}"')

# Demonstrate the undo/redo flow
editor = TextEditor()
editor.type_text("Hello")
editor.show()                

editor.type_text(" World")
editor.show()                

editor.type_text("!")
editor.show()              

editor.undo()
editor.show()           

editor.undo()
editor.show()           

editor.redo()
editor.show()

editor.type_text(" Python")
editor.show()         

editor.redo()  

Content: "Hello"
Content: "Hello World"
Content: "Hello World!"
Content: "Hello World"
Content: "Hello"
Content: "Hello World"
Content: "Hello World Python"
Nothing to redo

Aliran status antara kedua stack mengikuti pola yang jelas:

Pola dua stack ini tidak terbatas pada editor teks. Ini muncul di mana pun pengguna membutuhkan kemampuan untuk mundur dan maju melalui rangkaian perubahan (yang pada dasarnya ada di mana-mana):

• Perangkat lunak pengeditan gambar
• Rollback transaksi basis data
• Manajemen state gim

Prinsip dasarnya selalu sama. Satu stack Python melacak riwayat, yang lain melacak masa depan, dan urutan LIFO memastikan Anda selalu kembali ke status paling baru terlebih dahulu.

Konsep Lanjutan Stack Python

Stack juga memainkan peran penting di balik layar setiap program Python yang Anda jalankan, dan mereka mendukung teknik optimasi yang dapat secara dramatis mengurangi kompleksitas waktu dari masalah tertentu. Mari kita lihat kedua dimensi lanjutan ini.

Memahami call stack

Setiap kali Anda memanggil fungsi di Python, sesuatu terjadi di balik layar yang tidak Anda kendalikan langsung. Python menempatkan sebuah frame baru ke struktur data internal yang dikenal sebagai call stack. Frame ini menyimpan variabel lokal fungsi, parameternya, dan penunjuk kembali ke baris kode yang memulai pemanggilan. 

Saat fungsi selesai dieksekusi, framenya dipop dari call stack, dan kontrol kembali ke pemanggil.

Anda sebenarnya bisa mengamati perilaku ini menggunakan contoh sederhana:

def function_c():
    print("Inside function_c")
    # At this point, the call stack holds:
    # [main → function_a → function_b → function_c]  (top)

def function_b():
    print("Inside function_b")
    function_c()

def function_a():
    print("Inside function_a")
    function_b()

function_a()

Inside function_a
Inside function_b
Inside function_c

Saat function_c dieksekusi, call stack memiliki empat frame yang ditumpuk satu sama lain. Saat setiap fungsi selesai, framenya dipop dalam urutan LIFO. function_c selesai terlebih dahulu, lalu function_b, kemudian function_a, dan akhirnya ruang lingkup modul utama.

Inilah mekanisme yang membuat rekursi bekerja. Setiap pemanggilan rekursif menempatkan frame baru dengan variabel lokalnya sendiri, dan hasilnya terurai saat frame dipop. Mari kita lihat contohnya:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

# Call stack at deepest point:
# factorial(1)  ← top (returns 1)
# factorial(2)  ← waiting for factorial(1)
# factorial(3)  ← waiting for factorial(2)
# factorial(4)  ← waiting for factorial(3)
# factorial(5)  ← waiting for factorial(4)

120

Masalah muncul ketika rekursi terlalu dalam. Python menetapkan batas rekursi default sebesar 1.000 frame untuk mencegah call stack menghabiskan semua memori yang tersedia. Jika fungsi rekursif Anda melampaui batas ini, Python akan memunculkan RecursionError. Mari kita lihat contohnya:

def infinite_recursion(n):
    return infinite_recursion(n + 1)

try:
    infinite_recursion(0)
except RecursionError:
    print("RecursionError: maximum recursion depth exceeded")

RecursionError: maximum recursion depth exceeded

Anda dapat memeriksa dan memodifikasi batas ini menggunakan modul sys, meskipun peningkatannya harus dilakukan dengan hati-hati:

import sys

print(sys.getrecursionlimit())  
sys.setrecursionlimit(5000)     # Increase with caution

5000

Pembedaan penting yang perlu diingat adalah bahwa call stack adalah struktur tingkat sistem yang dikelola oleh interpreter Python itu sendiri. Anda tidak dapat melakukan push atau pop darinya secara langsung. Stack list, deque, dan LifoQueue yang kita bangun di bagian sebelumnya adalah struktur data yang ditentukan pengguna dan berada di memori heap program Anda. Mereka memiliki tujuan berbeda, tetapi keduanya mengikuti prinsip LIFO yang sama.

Menggunakan monotonic stack

Monotonic stack adalah variasi khusus di mana elemen dipertahankan dalam urutan nonmenurun atau nonturun (atau kadang ketat meningkat/menurun, tergantung masalahnya). Setiap kali Anda melakukan push elemen baru, Anda terlebih dahulu melakukan pop semua elemen yang akan melanggar batasan pengurutan. Ini adalah kunci untuk menyelesaikan seluruh kelas masalah optimasi dalam waktu linear.

Contoh klasiknya adalah masalah Next Greater Element: Diberikan array bilangan bulat, temukan elemen pertama di sebelah kanan yang lebih besar dari setiap elemen. Pendekatan brute-force menggunakan loop bersarang berjalan dalam O(n²). Untuk setiap elemen, Anda memindai semuanya di sebelah kanannya. Monotonic stack menyelesaikannya dalam O(n).

Wawasannya adalah Anda menelusuri array dari kanan ke kiri, mempertahankan stack menurun. Untuk setiap elemen, Anda mem-pop semua yang lebih kecil atau sama dengannya. Nilai-nilai tersebut tidak akan pernah bisa menjadi "next greater element" bagi elemen mana pun di sebelah kiri. 

Apa pun yang tersisa di puncak stack setelah pop adalah jawaban untuk elemen saat ini. Kemudian Anda melakukan push elemen saat ini ke stack. Mari kita lihat contoh kode. Perhatikan bahwa -1 dalam kasus ini berarti tidak ada elemen yang lebih besar di sebelah kanan angka tersebut:

from collections import deque

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # default: no greater element found
    stack = deque()     # monotonic decreasing stack (stores values)

    # Traverse from right to left
    for i in range(n - 1, -1, -1):
        # Pop elements that are not greater than current
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        
        # If stack is not empty, top is the next greater element
        if stack:
            result[i] = stack[-1]
        
        # Push current element onto the stack
        stack.append(nums[i])

    return result

nums = [4, 5, 2, 25, 7, 18]
print(next_greater_element(nums))

[5, 25, 25, -1, 18, -1]

Mari kita telusuri eksekusi untuk melihat bagaimana sifat monoton dipertahankan:

Perhatikan bahwa setiap elemen didorong ke stack tepat satu kali dan dipop paling banyak satu kali sepanjang penelusuran. Inilah mengapa total kompleksitas waktu adalah O(n) meskipun ada loop while di dalamnya. Jumlah kumulatif operasi push dan pop di seluruh iterasi tidak pernah melebihi 2n.

Seperti yang saya sebutkan sebelumnya, ada banyak masalah serupa yang pola monotonic stack percepat dari O(n²) menjadi O(n). Di antaranya adalah:

• Masalah rentang saham (stock span): Untuk harga setiap hari, temukan berapa banyak hari sebelumnya secara berurutan yang memiliki harga lebih rendah atau sama.
• Persegi panjang terbesar dalam histogram: Temukan luas persegi panjang maksimum yang masuk di bawah diagram batang (masalah wawancara level sulit klasik).
• Suhu harian (daily temperatures): Diberikan array suhu harian, temukan berapa hari Anda harus menunggu untuk hari yang lebih hangat.
• Menjebak air hujan (trapping rainwater): Hitung berapa banyak air hujan yang terjebak di antara batang dengan ketinggian bervariasi.

Dalam setiap kasus, gagasan intinya sama: batasan monoton memungkinkan Anda membuang elemen yang tidak lagi dapat memengaruhi hasil di masa depan, yang secara efektif memangkas ruang pencarian dari kuadratik menjadi linear.

Kesimpulan

Stack adalah salah satu struktur data pertama yang dipelajari setiap programmer dan salah satu yang terakhir berhenti menemukan kegunaan baru, yang secara ironis berlawanan dengan sifat Last-In-First-Out-nya. 

Dalam artikel ini, kita telah melihat bagaimana batasan LIFO ini dapat membantu dalam berbagai skenario, dari memvalidasi kurung bersarang dan mendorong penelusuran depth-first hingga mengelola state undo/redo dan mengoptimalkan masalah array dengan monotonic stack. 

Jika ada satu rekomendasi yang perlu diingat, itu adalah: gunakan collections.deque sebagai implementasi stack Python andalan Anda kecuali Anda punya alasan khusus untuk tidak melakukannya. 

Sebagai langkah berikutnya, saya merekomendasikan mengambil kursus kami ten Data Structures and Algorithms in Python.