Struktur data memainkan peran kunci dalam dunia pemrograman. Mereka membantu kami mengatur data kami dengan cara yang dapat digunakan secara efisien. Tumpukan adalah salah satu struktur data yang paling sederhana.
Mari belajar tentang stack dan implementasinya di Python.
Daftar isi
Apa itu Tumpukan?
Tumpukan mirip dengan tumpukan buku, kursi, dll., di kehidupan nyata. Dan itu mengikuti prinsip Last-in/First-out (LIFO). Ini adalah struktur data yang paling sederhana. Mari kita lihat skenario dengan contoh dunia nyata.
Katakanlah kita memiliki setumpuk buku sebagai berikut.
Saat kita menginginkan buku ketiga dari atas, kita harus menghapus dua buku pertama dari atas untuk mengeluarkan buku ketiga. Di sini, buku paling atas berada paling belakang di tumpukan dan didahulukan dari tumpukan. Tumpukan struktur data mengikuti prinsip yang sama Last-in/First-out (LIFO) dalam pemrograman.
Operasi di Stack
Terutama ada dua operasi dalam tumpukan
1. dorong (data)
Menambahkan atau mendorong data ke dalam tumpukan.
2. pop()
Menghapus atau memunculkan elemen paling atas dari tumpukan.
Lihat ilustrasi operasi push dan pop di bawah ini.
Kami akan menulis beberapa fungsi pembantu yang membantu kami mendapatkan lebih banyak info tentang tumpukan.
Mari kita lihat mereka.
mengintip()
Mengembalikan elemen paling atas dari tumpukan.
kosong()
Mengembalikan apakah tumpukan kosong atau tidak.
Aspek konseptual yang cukup dari struktur data tumpukan. Mari lompat ke implementasi tanpa basa-basi lagi.
Saya menganggap Anda telah menginstal python di PC Anda jika tidak, Anda juga dapat mencoba kompiler online.
Implementasi Tumpukan
Mengimplementasikan stack adalah yang termudah dibandingkan dengan implementasi struktur data lainnya. Kami dapat mengimplementasikan tumpukan dengan berbagai cara di Python.
Mari kita lihat semuanya satu per satu.
#1. Daftar
Kami akan mengimplementasikan tumpukan menggunakan daftar di kelas. Mari kita lihat implementasi langkah demi langkah dari stack.
Langkah1: Tulis kelas yang disebut Stack.
class Stack: pass
Langkah2: Kita harus mempertahankan data dalam daftar. Mari tambahkan daftar kosong di kelas Stack dengan elemen nama.
class Stack: def __init__(self): self.elements = []
Langkah3: Untuk mendorong elemen ke dalam tumpukan, kita memerlukan metode. Mari tulis metode push yang mengambil data sebagai argumen dan menambahkannya ke daftar elemen.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data
Langkah4: Demikian pula, mari tulis metode pop yang memunculkan elemen paling atas dari tumpukan. Kita dapat menggunakan metode pop dari tipe data daftar.
class Stack: ## ... def pop(self): return self.elements.pop()
Kami telah menyelesaikan implementasi tumpukan dengan operasi yang diperlukan. Sekarang, mari tambahkan fungsi pembantu untuk mendapatkan lebih banyak info tentang tumpukan.
Langkah5: Kita bisa mendapatkan elemen paling atas dari tumpukan menggunakan indeks negatif. Elemen kode [-1] mengembalikan yang terakhir dari daftar. Ini adalah elemen paling atas dari tumpukan dalam kasus kami.
class Stack: ## ... def peek(self): return self.elements[-1]
Langkah6: Jika panjang daftar elemen adalah 0, maka tumpukan kosong. Mari tulis metode yang mengembalikan apakah elemen kosong atau tidak.
class Stack: ## ... def is_empty(self): return len(self.elements) == 0
Kami telah menyelesaikan penerapan tumpukan menggunakan tipe data daftar.
Oh! tunggu kami baru saja menerapkannya. Tapi, tidak melihat cara menggunakannya. Lalu bagaimana cara menggunakannya?
Ayo mari kita lihat bagaimana menerapkannya. Kita harus membuat objek untuk kelas Stack untuk menggunakannya. Itu bukan masalah besar. Mari kita lakukan dulu.
class Stack:
## ...
if __name__ == '__main__':
stack = Stack()
Kami telah membuat objek tumpukan dan siap menggunakannya. Mari ikuti langkah-langkah di bawah ini untuk menguji operasi tumpukan.
- Periksa apakah tumpukan kosong atau tidak menggunakan metode is_empty. Itu harus mengembalikan True.
- Dorong angka 1, 2, 3, 4, 5 ke dalam tumpukan menggunakan metode push.
- Metode is_empty harus mengembalikan False. Periksa.
- Cetak elemen paling atas menggunakan metode peek.
- Pop elemen dari tumpukan menggunakan metode pop.
- Periksa elemen mengintip. Itu harus mengembalikan elemen 4.
- Sekarang, keluarkan semua elemen dari tumpukan.
- Metode is_empty harus mengembalikan True. Periksa.
Implementasi tumpukan kami selesai jika melewati semua langkah di atas. Cobalah untuk menulis kode untuk langkah-langkah di atas.
Apakah Anda menulis kode? Tidak, jangan khawatir periksa kode di bawah ini.
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
def pop(self):
return self.elements.pop()
def peek(self):
return self.elements[-1]
def is_empty(self):
return len(self.elements) == 0
if __name__ == '__main__':
stack = Stack()
## checking is_empty method -> true
print(stack.is_empty())
## pushing the elements
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
## again checking is_empty method -> false
print(stack.is_empty())
## printing the topmost element of the stack -> 5
print(stack.peek())
## popping the topmost element -> 5
stack.pop()
## checking the topmost element using peek method -> 4
print(stack.peek())
## popping all the elements
stack.pop()
stack.pop()
stack.pop()
stack.pop()
## checking the is_empty method for the last time -> true
print(stack.is_empty())
Hore! kami telah menyelesaikan implementasi tumpukan dari awal menggunakan tipe data daftar. Anda akan melihat output seperti yang disebutkan di bawah ini jika Anda menjalankan kode di atas.
True False 5 4 True
Kita bisa langsung menggunakan tipe data list sebagai stack. Implementasi stack di atas membantu Anda memahami implementasi stack dalam bahasa pemrograman lain juga.
Anda juga dapat melihat artikel terkait daftar ini.
Mari kita lihat deque bawaan dari modul bawaan koleksi yang dapat bertindak sebagai tumpukan.
#2. deque dari koleksi
Ini diimplementasikan sebagai antrian ujung ganda. Karena mendukung penambahan dan penghapusan elemen dari kedua ujungnya. Oleh karena itu kita dapat menggunakannya sebagai tumpukan. Kita bisa membuatnya mengikuti prinsip LIFO dari stack.
Itu diimplementasikan menggunakan struktur data lain yang disebut daftar tertaut ganda. Jadi kinerja penyisipan dan penghapusan elemen konsisten. Mengakses elemen dari daftar tertaut tengah membutuhkan waktu O(n). Kita dapat menggunakannya sebagai tumpukan karena tidak perlu mengakses elemen tengah dari tumpukan.
Sebelum mengimplementasikan stack, mari kita lihat metode yang digunakan untuk mengimplementasikan stack menggunakan antrian.
- append(data) – digunakan untuk mendorong data ke stack
- pop() – digunakan untuk menghapus elemen paling atas dari tumpukan
Tidak ada metode alternatif untuk peek dan is_empty. Kami dapat mencetak seluruh tumpukan sebagai pengganti metode peek. Selanjutnya, kita dapat menggunakan metode len untuk memeriksa apakah stack tersebut kosong atau tidak.
Mari implementasikan stack menggunakan deque dari modul collections.
from collections import deque ## creating deque object stack = deque() ## checking whether stack is empty or not -> true print(len(stack) == 0) ## pushing the elements stack.append(1) stack.append(2) stack.append(3) stack.append(4) stack.append(5) ## again checking whether stack is empty or not -> false print(len(stack) == 0) ## printing the stack print(stack) ## popping the topmost element -> 5 stack.pop() ## printing the stack print(stack) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the whether stack is empty or not for the last time -> true print(len(stack) == 0)
Itu dia. Kami telah belajar bagaimana mengimplementasikan stack menggunakan deque dari modul built-in collections. Anda akan mendapatkan output seperti yang disebutkan di bawah ini jika Anda menjalankan program di atas.
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Hingga saat ini, kami telah melihat dua cara untuk mengimplementasikan tumpukan. Apakah ada cara lain untuk mengimplementasikan tumpukan? Ya! Mari kita lihat cara terakhir untuk mengimplementasikan tumpukan dalam tutorial ini.
#3. LifoQueue
Nama LifoQueue sendiri menyatakan mengikuti prinsip LIFO. Karenanya kita dapat menggunakannya sebagai tumpukan tanpa keraguan. Itu dari antrian modul bawaan. LifoQueue menyediakan beberapa metode praktis yang berguna dalam implementasi stack. Mari kita lihat mereka
- put(data) – menambah atau mendorong data ke antrian
- get() – menghapus atau memunculkan elemen paling atas dari antrian
- empty() – mengembalikan apakah stack kosong atau tidak
- qsize() – mengembalikan panjang antrian
Mari implementasikan stack menggunakan LifoQueue dari modul queue.
from queue import LifoQueue
## creating LifoQueue object
stack = LifoQueue()
## checking whether stack is empty or not -> true
print(stack.empty())
## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
## again checking whether stack is empty or not -> false
print(stack.empty())
## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())
## checking the stack size
print("Size", stack.qsize())
print(stack.get())
print(stack.get())
## checking the whether stack is empty or not for the last time -> true
print(stack.empty())
Anda akan mendapatkan keluaran yang disebutkan di bawah ini jika Anda menjalankan program di atas tanpa mengubahnya.
True False 5 4 3 Size 2 2 1 True
Penerapan Tumpukan
Sekarang, Anda memiliki pengetahuan yang cukup tentang tumpukan untuk menerapkannya dalam masalah pemrograman. Mari kita lihat masalah dan selesaikan menggunakan tumpukan.
Diberikan ekspresi, tulis program untuk memeriksa apakah tanda kurung, kurung kurawal, kurung kurawal seimbang dengan benar atau tidak.
Mari kita lihat beberapa contoh.
Memasukkan: “[{}]([])”
Keluaran: Seimbang
Memasukkan: “{[}]([])”
Keluaran: Tidak Seimbang
Kita dapat menggunakan stack untuk menyelesaikan masalah di atas. Mari kita lihat langkah-langkah untuk memecahkan masalah.
- Buat tumpukan untuk menyimpan karakter.
- Jika panjang ekspresi ganjil, maka ekspresi tersebut Not Balanced
- Ulangi melalui ekspresi yang diberikan.
- Jika karakter saat ini adalah kurung buka dari ( atau { atau [, then push it to stack.
- Else if the current character is a closing bracket ) or } or ]lalu keluarkan dari tumpukan.
- Jika karakter yang muncul cocok dengan tanda kurung awal, lanjutkan tanda kurung tidak seimbang.
- Setelah iterasi, jika tumpukan kosong maka persamaannya Seimbang jika tidak persamaannya Tidak Seimbang.
Kita dapat menggunakan tipe data yang ditetapkan untuk memeriksa pencocokan tanda kurung.
## stack
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
def pop(self):
return self.elements.pop()
def peek(self):
return self.elements[-1]
def is_empty(self):
return len(self.elements) == 0
def balance_check(expression):
## checking the length of the expression
if len(expression) % 2 != 0:
## not balanced if the length is odd
return False
## for checking
opening_brackets = set('([{')
pairs = set([ ('(',')'), ('[',']'), ('{','}') ])
## stack initialization
stack = Stack()
## iterating through the given expression
for bracket in expression:
## checking whether the current bracket is opened or not
if bracket in opening_brackets:
## adding to the stack
stack.push(bracket)
else:
## popping out the last bracket from the stack
popped_bracket = stack.pop()
## checking whether popped and current bracket pair
if (popped_bracket, bracket) not in pairs:
return False
return stack.is_empty()
if __name__ == '__main__':
if balance_check('[{}]([])'):
print("Balanced")
else:
print("Not Balanced")
if balance_check('{[}]([])'):
print("Balanced")
else:
print("Not Balanced")
Kita dapat menggunakan tumpukan untuk menyelesaikan lebih banyak masalah. Masalah di atas adalah salah satunya. Cobalah untuk menerapkan konsep tumpukan di mana pun menurut Anda paling cocok untuk Anda.
Kesimpulan
Yah! Anda telah menyelesaikan tutorial. Saya harap Anda menikmati tutorial sebanyak yang saya lakukan saat membuatnya. Itu saja untuk tutorialnya.
Selamat Coding 🙂 👨💻
