Struktur Data - Stacks

Oke materi kita sekarang, akan membahas tentang koleksi. Hampir tidak ada definisi formal untuk koleksi karena seperti namanya, hanya sekelompok sesuatu hal yang bisa anda pahami. Mari kita buat beberapa observasi di sini. Koleksi tidak punya pesanan tertentu. Anda bisa mengacak beberapa elemen di sekitar dan itu tidak akan membuat perbedaan besar.

Oke pada materi ini, kita memeriksa representasi set dinamis dengan struktur data sederhana yang menggunakan pointer. Meskipun kita dapat membangun banyak struktur data yang kompleks menggunakan pointer, kita hanya menyajikan yang belum sempurna seperti stacks, queues, linked lists, dan rooted trees, dan inilah yang kita bahas nanti satu persatu. Kita akan menunjukkan cara untuk mensintesis objek dan pointer dari array. Kita mulai dengan Stacks dan queues

Secara harfiah setiap kali saya mendengar tentang stacks, saya hanya bisa memikirkan setumpuk logam, kertas, namun anda harus tahu bahwa stacks (tumpukan) ternyata merupakan struktur data berbasis list, sehingga memiliki sedikit perbedaan dibanding dari array dan linked lists. Ide utamanya adalah stack seperti tumpukan objek dalam kehidupan nyata. Anda tetap menempatkan elemen di atas dan Anda memiliki akses mudah untuk menghapus atau melihat elemen teratas atau terbaru

Oke mari kita bahas lebih lanjut tentang stack ini. Stack merupakan himpunan dinamis di mana elemen dihapus dari himpunan oleh operasi DELETE yang ditentukan. Dalam stack, elemen yang dihapus dari kumpulan adalah yang paling baru disisipkan: stack menerapkan kebijakan yang terakhir(Last In), pertama keluar(First-Out), atau LIFO, policy. Ada beberapa cara efisien untuk mengimplementasikan stack di komputer. Di bagian ini kita menunjukkan cara menggunakan array sederhana untuk mengimplementasikan masing-masing.

Operasi INSERT pada stack sering disebut PUSH, dan operasi DELETE, yang tidak mengambil argumen elemen, sering disebut POP. Nama-nama ini adalah kiasan untuk tumpukan fisik, seperti tumpukan tumpukan piring yang digunakan di kafetaria. Urutan lempengan yang muncul dari stack adalah kebalikan dari urutan di mana mereka didorong ke tumpukan, karena hanya pelat atas yang dapat diakses.

Contoh dibawah akan menunjukkan, dimana kita dapat mengimplementasikan stack paling banyak n elemen dengan array S[1..n]. Array punya atribut S.top yang mengindeks elemen yang paling baru dimasukkan. Stack terdiri dari elemen S[1..S.top]dimana S[1] elemen di bagian bawah tumpukan dan S[S.top] adalah elemen di atas. Proses nya menunjukkan efek dari operasi memodifikasi PUSH dan POP. Masing-masing dari tiga operasi tumpukan membutuhkan O(1) / waktu.

box1

Implementasi susunan stack S. Elemen stack hanya muncul dalam posisi sedikit berbayang.

(a) Stack S memiliki 4 elemen. Elemen teratas adalah 9.

(b) Stack S setelah panggilan PUSH (S,17) dan PUSH (S,3)

box1

( c ) Stack S Setelah panggilan POP (S) telah mengembalikan elemen 3, yang merupakan yang paling baru didorong. Meskipun elemen 3 masih muncul di array,itu tidak lagi dalam stack; bagian atas adalah elemen 17.

Ketika S.top = 0, stack tidak mengandung elemen dan kosong. Kita bisa menguji lihat apakah stack kosong oleh operasi query STACK EMPTY. Jika kita mencoba untuk memunculkan stack kosong, kita mengatakan stack underflow, yang biasanya merupakan kesalahan. Jika S.top melebihi n, stack overflows. Kita dapat mengimplementasikan setiap operasi stack hanya dengan beberapa baris kode:

STACK-EMPTY

if S.top = 0
     return TRUE
else return FALSE
PUSH(S,x)
S.top = S.top + 1
S[S.top]=x
POP(S)
if STACK-EMPTY(S)
   error “underflow”
else S.top = S.top – 1
return S[S.top + 1]