Apa itu Struktur Data Stack dengan Python?

Struktur Data adalah kumpulan nilai data, hubungan di antara mereka, dan fungsi atau operasi yang dapat diterapkan pada data. Sekarang ada banyak Struktur Data yang tersedia. Namun hari ini fokus kami adalah pada Stack Data Structures. Saya akan membahas topik-topik berikut:

• Mengapa Struktur Data?
• Jenis Struktur Data
• Apa itu Stack Data Structure?
• Membuat Struktur Data Stack
• Dorong Elemen ke dalam Tumpukan
• Elemen Pop dari Stack
• Aplikasi Struktur Data Stack

Mengapa Struktur Data?

Untuk menjawab ini, Anda harus berpikir secara mendalam. Pikirkan bagaimana peta Google menunjukkan kepada Anda rute terbaik hanya dalam hitungan detik, bagaimana peta itu mengembalikan Anda hasil pencarian dalam mikrodetik. Itu tidak hanya berurusan dengan 100 situs web, itu berurusan dengan lebih dari satu miliar situs dan masih menunjukkan kepada Anda hasil dengan sangat cepat.

Nah, meskipun algoritma yang digunakan memainkan peran yang sangat penting, struktur data atau wadah yang digunakan adalah fondasi dari algoritma tersebut. Dalam aplikasi apa pun, mengatur dan menyimpan data dengan cara atau struktur yang paling sesuai untuk penggunaannya adalah kunci untuk akses dan pemrosesan data yang efisien.

Jenis Struktur Data

Ada beberapa struktur data standar yang dapat digunakan untuk bekerja dengan data secara efisien. Kami bahkan dapat menyesuaikannya atau membuat yang benar-benar baru agar sesuai dengan aplikasi kami.

Apa itu Stack Data Structure?

Pertimbangkan beberapa contoh kehidupan nyata:

• Pengiriman kargo
• Piring di atas nampan
• Tumpukan koin
• Tumpukan laci
• Shunting kereta di halaman rel

Semua contoh ini mengikuti a Last-In-First-Out strategi. Perhatikan piring-piring di atas nampan, Saat ingin memilih piring terpaksa harus mengambil piring dari atas sedangkan saat piring disimpan di atas nampan harus dalam urutan terbalik. Contoh di atas yang mengikuti Last-In-First-Out (LIFO) Prinsipnya dikenal sebagai Tumpukan .

Terlepas dari operasi pelengkap, saya dapat mengatakan bahwa Operasi utama yang memungkinkan pada stack adalah:

cara menggunakan goto c ++

1. Dorong atau masukkan elemen ke atas tumpukan
2. Pop atau hapus elemen dari atas tumpukan

Membuat Struktur Data Stack

class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1

• max_size adalah jumlah maksimum elemen yang diharapkan dalam tumpukan.
• Elemen tumpukan disimpan dalam daftar python.
• Top menunjukkan indeks paling atas dari tumpukan yang awalnya diambil -1 untuk menandai tumpukan kosong.

Status awal Stack dapat dilihat pada Gambar dimana max_size = 5

Dorong Elemen ke Tumpukan

Sekarang, jika Anda ingin memasukkan atau mendorong elemen ke tumpukan, Anda harus mengingatnya

• Bagian atas akan menunjukkan indeks tempat elemen akan disisipkan.
• Dan tidak ada elemen yang akan disisipkan saat tumpukan penuh yaitu saat max_size = top.

Jadi apa yang harus menjadi algoritma ??

# mengembalikan ukuran maksimum tumpukan def get_max_size (self): return self .__ max_size # mengembalikan nilai bool apakah tumpukan penuh atau tidak, True jika penuh dan False sebaliknya def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes element di bagian atas stack def push (self, data): if (self.is_full ()): print ('stack is been full') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data #Anda dapat menggunakan di bawah __str __ () untuk mencetak elemen dari objek DS saat debugging def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '.join (msg) msg ​​= 'Stack data (Top to Bottom):' + msg return msg

Sekarang, Saat Anda menjalankan yang berikut:

tumpukan1 = Tumpukan (4)

#Tekan semua elemen yang dibutuhkan.

stack1.push ('A')

stack1.push ('B')

stack1.push ('C')

stack1.push ('E')

cetak (stack1.is_full ())

cetak (stack1)

Keluaran:

tumpukan sudah penuh
Benar
Data tumpukan (Atas ke Bawah): D C B A

Elemen Pop dari Stack

Sekarang, karena Anda telah memasukkan elemen ke dalam tumpukan, Anda ingin memunculkannya, jadi Anda perlu melakukan hal berikut:

• Tumpukan tidak kosong, yaitu atas! = -1
• Saat Anda menghapus data, bagian atas harus mengarah ke bagian atas tumpukan sebelumnya.

Jadi, apa algoritmanya ??

#mengembalikan nilai bool apakah stack kosong atau tidak, True jika kosong dan False sebaliknya def is_empty (self): return self .__ top == - 1 #returns nilai yang muncul def pop (self): if (self.is_empty ()): print ('nothing to pop, been empty') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 return a #display semua elemen stack dari atas ke bawah def display (self): untuk i dalam kisaran (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()

Sekarang, dengan mempertimbangkan tumpukan yang dibuat sebelumnya, coba pop elemen

lompat di c ++

cetak (stack1.pop ())

cetak (stack1.pop ())

cetak (stack1)

cetak (stack1.pop ())

cetak (stack1.pop ())

cetak (stack1.pop ())

Keluaran:

D

C

Data tumpukan (Atas ke Bawah): B A

B

UNTUK

tidak ada yang muncul, sudah kosong

Aplikasi Struktur Data Stack

• Contoh 1:

Tumpukan digunakan untuk mengimplementasikan algoritma pencocokan braket untuk evaluasi ekspresi aritmatika dan juga dalam implementasi pemanggilan metode.

Jawabannya adalah 5.

• Contoh 2:

Papan klip di Windows menggunakan dua tumpukan untuk mengimplementasikan operasi undo-redo (ctrl + z, ctrl + y). Anda pasti pernah bekerja pada editor kata Windows seperti MS-Word, Notepad, dll. Berikut adalah teks yang ditulis dalam MS-Word. Amati bagaimana teks berubah saat mengklik Ctrl-Z dan Ctrl-Y.

Berikut adalah kode yang mensimulasikan operasi undo-redo. Buka kode dan amati bagaimana tumpukan digunakan dalam implementasi ini.

#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): print ('The stack is full !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Stack is empty! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' The stack is empty ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size #Anda dapat menggunakan di bawah __str __ () untuk mencetak elemen Objek DS saat men-debug def __str __ (self): msg = [] index = self .__ top sementara (indeks> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg ​​=' Stack data (Atas ke Bawah): '+ msg mengembalikan ms g #fungsi untuk mengimplementasikan operasi hapus atau spasi mundur def remove (): clipboard global, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Remove:', clipboard) #fungsi untuk mengimplementasikan operasi urungkan def undo (): papan klip global, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Tidak ada data untuk dibatalkan') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', clipboard) #fungsi untuk mengimplementasikan operasi redo def redo (): clipboard global, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Tidak ada data untuk mengulang ') lain: data = redo_stack.pop () if (data tidak ada di clipboard): print (' Tidak ada data untuk diulang ') redo_stack.push (data) lain: clipboard.remove (data) undo_stack.push ( data) print ('Ulangi:', clipboard) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = Stack (len (clipboard)) hapus () batalkan () ulangi ()

Keluaran:

Hapus: ['A', 'B', 'C', 'D', 'E']

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

Ulangi: ['A', 'B', 'C', 'D', 'E']

Dengan ini, kita sampai pada akhir artikel Stack Data Structure dengan Python ini. Jika Anda berhasil memahami dan menjalankan kode sendiri, Anda bukan lagi pemula di Stacks Data Structure.

apa 6 cara menggunakan kata kunci ini

Ada pertanyaan untuk kami? Harap sebutkan di bagian komentar artikel ini dan kami akan menghubungi Anda kembali sesegera mungkin.

Untuk mendapatkan pengetahuan mendalam tentang Python beserta berbagai aplikasinya, Anda dapat mendaftar secara langsung dengan dukungan 24/7 dan akses seumur hidup.