Panduan Tumpukan dengan Python

Pengantar

Meskipun beberapa struktur data bersifat serbaguna dan dapat digunakan dalam berbagai aplikasi, struktur data lainnya dikhususkan dan dirancang untuk menangani masalah tertentu. Salah satu struktur khusus tersebut, yang dikenal karena kesederhanaannya namun kegunaannya luar biasa, adalah tumpukan.

Jadi, apa itu tumpukan? Pada intinya, tumpukan adalah struktur data linier yang mengikuti LIFO Prinsip (Terakhir Masuk Pertama Keluar).. Anggap saja sebagai tumpukan piring di kafetaria; Anda hanya mengambil piring yang ada di atas, dan ketika meletakkan piring baru, piring itu akan masuk ke tumpukan paling atas.

Elemen terakhir yang ditambahkan adalah elemen pertama yang dihilangkan

Namun, mengapa memahami tumpukan itu penting? Selama bertahun-tahun, tumpukan telah menemukan aplikasinya di banyak bidang, mulai dari manajemen memori dalam bahasa pemrograman favorit Anda hingga fungsi tombol kembali di browser web Anda. Kesederhanaan intrinsik ini, dipadukan dengan penerapannya yang luas, menjadikan tumpukan sebagai alat yang sangat diperlukan dalam gudang senjata pengembang.

Dalam panduan ini, kita akan mendalami konsep di balik tumpukan, implementasinya, kasus penggunaan, dan banyak lagi. Kita akan mendefinisikan apa itu tumpukan, cara kerjanya, dan kemudian, kita akan melihat dua cara paling umum untuk mengimplementasikan struktur data tumpukan dengan Python.

Konsep Dasar Struktur Data Tumpukan

Pada intinya, tumpukan tampak sederhana, namun memiliki nuansa yang memberinya aplikasi serbaguna dalam domain komputasi. Sebelum mendalami implementasi dan penggunaan praktisnya, mari kita pastikan pemahaman yang kuat tentang konsep inti seputar tumpukan.

Prinsip LIFO (Last In First Out).

LIFO adalah prinsip panduan di balik tumpukan. Artinya, item terakhir yang masuk ke tumpukan adalah item pertama yang keluar. Karakteristik ini membedakan tumpukan dari struktur data linier lainnya, seperti antrian.

Operasi Dasar

Setiap struktur data ditentukan oleh operasi yang didukungnya. Untuk tumpukan, operasi ini mudah namun penting:

• Dorong – Menambahkan elemen ke bagian atas tumpukan. Jika tumpukan penuh, operasi ini mungkin mengakibatkan tumpukan meluap.

• pop – Menghapus dan mengembalikan elemen paling atas dari tumpukan. Jika tumpukan kosong, upaya pop dapat menyebabkan tumpukan kekurangan.

• Intip (atau Atas) – Mengamati elemen paling atas tanpa menghapusnya. Operasi ini berguna ketika Anda ingin memeriksa elemen teratas saat ini tanpa mengubah status tumpukan.

Saat ini, pentingnya struktur data tumpukan dan konsep dasarnya sudah jelas. Seiring berjalannya waktu, kami akan mendalami penerapannya, menjelaskan bagaimana prinsip-prinsip dasar ini diterjemahkan ke dalam kode praktis.

Bagaimana Mengimplementasikan Stack dari Awal dengan Python

Setelah memahami prinsip dasar di balik tumpukan, sekarang saatnya menyingsingkan lengan baju dan mempelajari sisi praktisnya. Menerapkan tumpukan, meskipun mudah, dapat dilakukan dengan berbagai cara. Di bagian ini, kita akan mengeksplorasi dua metode utama dalam mengimplementasikan tumpukan – menggunakan array dan daftar tertaut.

Mengimplementasikan Stack Menggunakan Array

Array, menjadi lokasi memori yang berdekatan, menawarkan cara intuitif untuk merepresentasikan tumpukan. Mereka memungkinkan kompleksitas waktu O(1) untuk mengakses elemen berdasarkan indeks, memastikan operasi push, pop, dan peek yang cepat. Selain itu, array bisa lebih hemat memori karena tidak ada overhead pointer seperti pada daftar tertaut.

Di sisi lain, array tradisional memiliki ukuran tetap, artinya setelah diinisialisasi, ukurannya tidak dapat diubah. Hal ini dapat menyebabkan a stack overflow jika tidak dipantau. Hal ini dapat diatasi dengan array dinamis (seperti milik Python list), yang dapat diubah ukurannya, tetapi operasi ini cukup mahal.

Setelah semua itu selesai, mari mulai mengimplementasikan kelas tumpukan kita menggunakan array dengan Python. Pertama-tama, mari kita buat kelasnya sendiri, dengan konstruktor yang menggunakan ukuran tumpukan sebagai parameter:

class Stack: def __init__(self, size): self.size = size self.stack = [None] * size self.top = -1

Seperti yang Anda lihat, kami menyimpan tiga nilai di kelas kami. Itu size adalah ukuran tumpukan yang diinginkan, itu stack adalah array sebenarnya yang digunakan untuk mewakili struktur data tumpukan, dan top adalah indeks elemen terakhir di stack array (bagian atas tumpukan).

Mulai sekarang, kami akan membuat dan menjelaskan satu metode untuk setiap operasi tumpukan dasar. Masing-masing metode tersebut akan terkandung dalam Stack kelas yang baru saja kita buat.

Mari kita mulai dengan push() metode. Seperti yang telah dibahas sebelumnya, operasi push menambahkan elemen ke bagian atas tumpukan. Pertama-tama, kita akan memeriksa apakah tumpukan memiliki ruang tersisa untuk elemen yang ingin kita tambahkan. Jika tumpukan sudah penuh, kami akan menaikkannya Stack Overflow pengecualian. Jika tidak, kita hanya akan menambahkan elemen dan menyesuaikannya top dan stack demikian:

def push(self, item): if self.top == self.size - 1: raise Exception("Stack Overflow") self.top += 1 self.stack[self.top] = item

Sekarang, kita dapat menentukan metode untuk menghapus elemen dari atas tumpukan – the pop() metode. Bahkan sebelum kita mencoba menghapus sebuah elemen, kita perlu memeriksa apakah ada elemen di tumpukan karena tidak ada gunanya mencoba mengeluarkan elemen dari tumpukan kosong:

def pop(self): if self.top == -1: raise Exception("Stack Underflow") item = self.stack[self.top] self.top -= 1 return item

Akhirnya, kita dapat mendefinisikan peek() metode yang hanya mengembalikan nilai elemen yang saat ini berada di puncak tumpukan:

def peek(self): if self.top == -1: raise Exception("Stack is empty") return self.stack[self.top]

Dan itu saja! Kami sekarang memiliki kelas yang mengimplementasikan perilaku tumpukan menggunakan daftar dengan Python.

Menerapkan Stack Menggunakan Daftar Tertaut

Daftar tertaut, menjadi struktur data dinamis, dapat dengan mudah tumbuh dan menyusut, yang dapat bermanfaat untuk mengimplementasikan tumpukan. Karena daftar tertaut mengalokasikan memori sesuai kebutuhan, tumpukan dapat bertambah dan berkurang secara dinamis tanpa perlu mengubah ukuran secara eksplisit. Manfaat lain menggunakan daftar tertaut untuk mengimplementasikan tumpukan adalah operasi push dan pop hanya memerlukan perubahan penunjuk sederhana. Kelemahannya adalah setiap elemen dalam daftar tertaut memiliki penunjuk tambahan, sehingga menghabiskan lebih banyak memori dibandingkan dengan array.

Seperti yang sudah kita bahas di “Daftar Tertaut Python” artikel, hal pertama yang perlu kita implementasikan sebelum daftar tertaut sebenarnya adalah kelas untuk satu node:

class Node: def __init__(self, data): self.data = data self.next = None

Implementasi ini hanya menyimpan dua titik data – nilai yang disimpan dalam node (data) dan referensi ke node berikutnya (next).

Sekarang kita bisa melompat ke kelas tumpukan sebenarnya. Konstruktornya akan sedikit berbeda dari yang sebelumnya. Ini hanya akan berisi satu variabel – referensi ke node di bagian atas tumpukan:

class Stack: def __init__(self): self.top = None

Seperti yang diharapkan, push() metode menambahkan elemen baru (simpul dalam hal ini) ke bagian atas tumpukan:

def push(self, item): node = Node(item) if self.top: node.next = self.top self.top = node

Grafik pop() metode memeriksa apakah ada elemen dalam tumpukan dan menghapus elemen paling atas jika tumpukan tidak kosong:

def pop(self): if not self.top: raise Exception("Stack Underflow") item = self.top.data self.top = self.top.next return item

Akhirnya, peek() metode cukup membaca nilai elemen dari atas tumpukan (jika ada):

def peek(self): if not self.top: raise Exception("Stack is empty") return self.top.data

Pilihan antara array dan daftar tertaut bergantung pada persyaratan dan batasan spesifik aplikasi.

Cara Mengimplementasikan Stack menggunakan Struktur Bawaan Python

Bagi banyak pengembang, membangun tumpukan dari awal, meskipun bersifat mendidik, mungkin bukan cara paling efisien untuk menggunakan tumpukan dalam aplikasi dunia nyata. Untungnya, banyak bahasa pemrograman populer dilengkapi dengan struktur data dan kelas bawaan yang secara alami mendukung operasi tumpukan. Di bagian ini, kita akan mengeksplorasi penawaran Python dalam hal ini.

Python, sebagai bahasa yang serbaguna dan dinamis, tidak memiliki kelas tumpukan khusus. Namun, struktur data bawaannya, khususnya daftar dan kelas deque dari collections modul, dapat dengan mudah berfungsi sebagai tumpukan.

Menggunakan Daftar Python sebagai Tumpukan

Daftar Python dapat meniru tumpukan dengan cukup efektif karena sifatnya yang dinamis dan adanya metode seperti itu append() dan pop().

• Operasi Dorong – Menambahkan elemen ke bagian atas tumpukan semudah menggunakan append() Metode:

  stack = []
  stack.append('A')
  stack.append('B')
  

• Operasi Pop – Menghapus elemen paling atas dapat dilakukan dengan menggunakan pop() metode tanpa argumen apa pun:

  top_element = stack.pop() 

• Operasi Intip Mengakses bagian atas tanpa muncul dapat dilakukan menggunakan pengindeksan negatif:

  top_element = stack[-1] 

Menggunakan deque Kelas dari koleksi Modul

Grafik deque Kelas (kependekan dari antrian berujung ganda) adalah alat serbaguna lainnya untuk implementasi tumpukan. Ini dioptimalkan untuk penambahan dan pop cepat dari kedua ujungnya, membuatnya sedikit lebih efisien untuk operasi tumpukan dibandingkan daftar.

• Inisialisasi:

  from collections import deque
  stack = deque()
  

• Operasi Dorong – Mirip dengan daftar, append() metode yang digunakan:

  stack.append('A')
  stack.append('B')
  

• Operasi Pop – Suka daftar, pop() metode melakukan pekerjaan:

  top_element = stack.pop() 

• Operasi Intip – Pendekatannya sama dengan daftar:

  top_element = stack[-1] 

Kapan Menggunakan Yang Mana?

Meskipun daftar dan deques dapat digunakan sebagai tumpukan, jika Anda terutama menggunakan struktur sebagai tumpukan (dengan tambahan dan munculan dari satu ujung), deque bisa sedikit lebih cepat karena optimasinya. Namun, untuk sebagian besar tujuan praktis dan kecuali jika berurusan dengan aplikasi yang kinerjanya kritis, daftar Python sudah cukup.

Potensi Masalah Terkait Stack dan Cara Mengatasinya

Meskipun tumpukan sangat serbaguna dan efisien, seperti struktur data lainnya, tumpukan tidak kebal terhadap potensi kesalahan. Penting untuk mengenali tantangan-tantangan ini ketika bekerja dengan tumpukan dan mempunyai strategi untuk mengatasinya. Di bagian ini, kita akan mendalami beberapa masalah umum terkait tumpukan dan mencari cara untuk mengatasinya.

Stack Overflow

Hal ini terjadi ketika ada upaya untuk mendorong elemen ke tumpukan yang telah mencapai kapasitas maksimumnya. Masalah ini terutama terjadi di lingkungan yang ukuran tumpukannya tetap, seperti dalam skenario pemrograman tingkat rendah tertentu atau pemanggilan fungsi rekursif.

Jika Anda menggunakan tumpukan berbasis larik, pertimbangkan untuk beralih ke larik dinamis atau implementasi daftar tertaut, yang akan mengubah ukurannya sendiri. Langkah lain dalam pencegahan stack overflow adalah dengan terus memantau ukuran tumpukan, terutama sebelum operasi push, dan memberikan pesan kesalahan yang jelas atau petunjuk untuk stack overflow.

Jika stack overflow terjadi karena panggilan rekursif yang berlebihan, pertimbangkan solusi berulang atau tingkatkan batas rekursi jika lingkungan mengizinkan.

Tumpukan Aliran Bawah

Hal ini terjadi ketika ada upaya untuk mengeluarkan elemen dari tumpukan kosong. Untuk mencegah hal ini terjadi, selalu periksa apakah tumpukan kosong sebelum menjalankan operasi pop atau peek. Kembalikan pesan kesalahan yang jelas atau tangani underflow dengan baik tanpa membuat program mogok.

Di lingkungan yang dapat diterima, pertimbangkan untuk mengembalikan nilai khusus saat muncul dari tumpukan kosong untuk menandakan ketidakabsahan operasi.

Kendala Memori

Dalam lingkungan dengan memori terbatas, bahkan mengubah ukuran tumpukan secara dinamis (seperti yang didasarkan pada daftar tertaut) dapat menyebabkan kehabisan memori jika ukurannya bertambah terlalu besar. Oleh karena itu, perhatikan penggunaan memori aplikasi secara keseluruhan dan pertumbuhan tumpukannya. Mungkin memperkenalkan soft cap pada ukuran tumpukan.

Masalah Keamanan Benang

Dalam lingkungan multi-thread, operasi simultan pada tumpukan bersama oleh thread berbeda dapat menyebabkan inkonsistensi data atau perilaku yang tidak terduga. Solusi potensial untuk masalah ini mungkin adalah:

• Mutex dan Kunci – Gunakan mutex (objek saling mengecualikan) atau kunci untuk memastikan bahwa hanya satu thread yang dapat melakukan operasi pada tumpukan pada waktu tertentu.
• Operasi Atom – Memanfaatkan operasi atom, jika didukung oleh lingkungan, untuk memastikan konsistensi data selama operasi push dan pop.
• Tumpukan thread-lokal – Dalam skenario di mana setiap thread memerlukan tumpukannya sendiri, pertimbangkan untuk menggunakan penyimpanan lokal thread untuk memberikan instance tumpukan terpisah pada setiap thread.

Meskipun tumpukan memang kuat, menyadari potensi masalah mereka dan secara aktif menerapkan solusi akan memastikan aplikasi yang kuat dan bebas kesalahan. Menyadari kendala-kendala ini adalah separuh dari perjuangan – separuh lainnya adalah menerapkan praktik terbaik untuk mengatasinya secara efektif.

Kesimpulan

Tumpukan, meskipun sifatnya tampak sederhana, mendukung banyak operasi mendasar di dunia komputasi. Dari mengurai ekspresi matematika yang kompleks hingga mengelola pemanggilan fungsi, kegunaannya sangat luas dan penting. Saat kita menelusuri seluk beluk struktur data ini, jelas bahwa kekuatannya tidak hanya terletak pada efisiensinya namun juga pada keserbagunaannya.

Namun, seperti halnya semua alat, efektivitasnya bergantung pada cara penggunaannya. Pastikan Anda memiliki pemahaman menyeluruh tentang prinsip-prinsipnya, potensi kendala, dan praktik terbaiknya untuk memastikan bahwa Anda dapat memanfaatkan kekuatan tumpukan yang sebenarnya. Baik Anda menerapkannya dari awal atau memanfaatkan fasilitas bawaan dalam bahasa seperti Python, penerapan struktur data inilah yang akan membedakan solusi Anda.

• Konten Bertenaga SEO & Distribusi PR. Dapatkan Amplifikasi Hari Ini.
• PlatoData.Jaringan Vertikal Generatif Ai. Berdayakan Diri Anda. Akses Di Sini.
• PlatoAiStream. Intelijen Web3. Pengetahuan Diperkuat. Akses Di Sini.
• PlatoESG. Karbon, teknologi bersih, energi, Lingkungan Hidup, Tenaga surya, Penanganan limbah. Akses Di Sini.
• PlatoHealth. Kecerdasan Uji Coba Biotek dan Klinis. Akses Di Sini.
• Sumber: https://stackabuse.com/guide-to-stacks-in-python/