Jenis Data Abstrak — stack, queue, linked list
| English | Bahasa Indonesia |
|---|---|
| queue/kjuː/ | antrean |
| push/pʊʃ/ | dorong |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | tipe data abstrak |
| stack/stæk/ | tumpukan |
| linked list/lɪŋkt lɪst/ | daftar linked |
| LIFO/ˈlaɪfəʊ/ | LIFO |
| pop/pɒp/ | pop |
| pointer/ˈpɔɪntə/ | pointer |
| FIFO/ˈfaɪfəʊ/ | FIFO |
| enqueue/enˈkjuː/ | enqueue |
| dequeue/diːˈkjuː/ | dequeue |
| node/nəʊd/ | simpul |
| traverse/trəˈvɜːs/ | traversing |
Tombol Kembali dan antrean printer
- Setiap halaman yang Anda kunjungi didorong ke tumpukan; tombol Kembali mengambil salah satu dari atas. Halaman yang paling baru Anda tinggalkan adalah yang pertama Anda kembalikan.
- Di sepanjang koridor, sebuah printer memproses pekerjaan sesuai urutan kedatangannya. Dokumen yang dikirim pertama keluar pertama, sekecil apa pun dokumen yang ada di belakangnya.
- Dua struktur, aturan berlawanan, dan Anda menggunakan keduanya sebelum istirahat. Tidak ada yang mengatakan bagaimana cara penyimpanannya; masing-masing hanya menjelaskan apa yang dilakukan operasi mereka.
- Itu adalah tipe data abstrak. Pelajaran ini adalah tiga yang disebutkan silabus, operasi pada masing-masing, dan bagaimana membenarkan satu untuk suatu situasi.
Apa itu ADT
- Tipe data abstrak (ADT) adalah kumpulan data bersama dengan sekumpulan operasi pada data tersebut. Satu kalimat ini adalah definisi bernilai satu poin.
- Didefinisikan oleh apa yang dilakukan operasi, bukan bagaimana data disimpan. Implementasinya disembunyikan, sehingga dapat berubah tanpa mempengaruhi kode yang menggunakannya.
- Tumpukan, antrian, daftar terhubung, pohon biner, dan array semuanya adalah ADT.
Tipe Data Abstrak (ADT) didefinisikan oleh:
ADT menentukan operasi (antarmuka); implementasinya disembunyikan dan dapat berubah bebas.
Tumpukan
- Tumpukan adalah daftar di mana item ditambahkan dan dihapus dari ujung yang sama, yaitu atas, sehingga item terakhir yang ditambahkan adalah yang pertama dihapus: LIFO.
- Operasi: push menambahkan ke atas, pop menghapus dari atas, peek melihat ke atas, dan menguji apakah kosong atau penuh.
- Kegunaan: riwayat undo, tombol Kembali, alamat pengembalian pemanggilan fungsi, pengecekan kurung, penelusuran mundur.
Semua hal terjadi di bagian atas
Stack bekerja dalam urutan mana?
Stack bersifat LIFO: item yang paling baru ditambahkan (dorong) adalah yang pertama kali dikeluarkan (pop).
Contoh terpecahkan: telusuri tumpukan
- Tumpukan berisi, dari bawah,
'P' 'N' 'Z' 'X' 'Y' 'W'; pointer atas berada di'W'. OperasiPOP,POP,PUSH 'A',PUSH 'B',POPdilakukan. Apa yang dipegang tumpukan, dan di mana letak pointer? - Dua kali pop menghilangkan
'W'kemudian'Y'. Pushes menempatkan'A'kemudian'B'di tempat mereka. Pop terakhir menghilangkan'B'. - Tumpukan berisi
'P' 'N' 'Z' 'X' 'A', dengan pointer di'A'. Item yang paling lama ada di tumpukan adalah yang paling bawah,'P'; lima kali pop lebih lanjut dimungkinkan, dan pop keenam akan menjadi kesalahan, itulah sebabnya pop menguji apakah kosong terlebih dahulu.
Sebuah stack berisi P N Z X Y W (atas adalah W). Setelah POP, POP, PUSH 'A', PUSH 'B', POP, item mana yang berada di atas?
W dan Y dikeluarkan, A kemudian B ditambahkan, B dikeluarkan. Atas adalah A, di atas X.
Antrian
- Antrian adalah daftar di mana item ditambahkan di belakang dan dihapus dari depan, sehingga item pertama yang ditambahkan adalah yang pertama dihapus: FIFO.
- Operasi: enqueue menambahkan di belakang, dequeue menghapus dari depan, dan menguji apakah kosong atau penuh.
- Kegunaan: pencetakan spooling, buffer keyboard, penjadwalan, pelanggan di toko, pencarian breadth-first.
Bergabung di belakang, keluar dari depan
Stacks, queues & linked lists
LIFO vs FIFO
A tumpukan bersifat last-in-first-out; operasi dorong dan pop terjadi di ujung yang sama (atas).
Antrian (antrean) bersifat first-in-first-out: item diambil dari ______ dan ditambahkan di bagian belakang.
FIFO: dequeue dari depan, enqueue di belakang — seperti antrean orang.
Contoh terpecahkan: jelaskan penambahan dan penghapusan dari antrian
- Menambah: periksa bahwa antrian tidak penuh; simpan item pada posisi yang ditentukan oleh pointer belakang; geser pointer belakang (dan tambahkan satu ke jumlah).*
- Menghapus: periksa bahwa antrian tidak kosong; baca item pada pointer depan; geser pointer depan (dan kurangi satu dari jumlah).
- Nyatakan konvensi yang Anda gunakan: jika pointer belakang menandai ruang bebas berikutnya, simpan terlebih dahulu lalu geser; jika menandai item terakhir, geser terlebih dahulu lalu simpan. Keduanya mendapat nilai, jika Anda konsisten.
Susun langkah-langkah menambahkan item ke dalam antrian secara berurutan (pointer rear menandai ruang kosong berikutnya).
Pengecekan dilakukan terlebih dahulu; kemudian simpan, lalu geser, sesuai konvensi ini. Sebutkan konvensi yang Anda gunakan.
Daftar terhubung
- Daftar terhubung adalah daftar di mana setiap node menyimpan item data dan pointer ke node berikutnya, dengan pointer awal ke node pertama. Pointer node terakhir adalah sentinel seperti
NULL. - Operasi: sisipkan, hapus, cari, dan traversing, mengikuti pointer dari kepala untuk mengunjungi setiap node secara berurutan.
- Keunggulan dibanding array: menyisipkan atau menghapus murah, cukup sambung ulang pointer, dan daftar tumbuh sesuai kebutuhan. Kerugian: tidak ada akses acak; mencapai node kesepuluh berarti mengikuti sembilan pointer.
Sebuah nilai dan panah, diulang
Daftar terhubung (*linked list*): node-node yang dihubungkan oleh pointer
Setiap node menyimpan nilai dan pointer ke node berikutnya. Menyisipkan atau menghapus hanya menghubungkan ulang pointer — tidak ada item bergeser, berbeda dengan array.
Setiap node dalam daftar terhubung menyimpan:
Node menyimpan nilainya plus pointer (referensi) ke node berikutnya; kepala menandai awal, NULL menandai akhir.
Daftar terhubung membuat penyisipan/penghapusan murah (hanya merakit ulang pointer) tetapi akses acak lambat (harus mengikuti pointer dari kepala).
Itulah kompromi antara array dan daftar: array memberikan akses indeks O(1); daftar memberikan penyisipan/penghapusan yang murah.
Contoh terpecahkan: tambah node secara berurutan
- Jelaskan bagaimana nilai baru disisipkan ke dalam daftar terhubung yang dijaga dalam urutan menaik. [4]
- Traversing daftar dari kepala, mengikuti pointer, hingga node sebelum posisi ditemukan: node terakhir yang nilainya lebih kecil dari yang baru.
- Ambil node bebas dan simpan nilai baru di dalamnya. Atur pointer node baru ke alamat yang saat ini ditunjuk oleh node sebelumnya.
- Kemudian atur pointer node sebelumnya ke node baru. Jika nilai baru berada di depan, maka pointer kepala yang berubah sebagai gantinya.
Susun langkah-langkah menyisipkan nilai ke dalam daftar terhubung yang terurut secara berurutan.
Temukan, isi, arahkan node baru ke depan, lalu rakit ulang node sebelumnya. Membalik dua langkah terakhir akan kehilangan sisa daftar.
Membenarkan pilihan
- Item harus ditangani sesuai urutan kedatangannya, cetak job, penekan tombol, pelanggan: sebuah antrean, karena pertama masuk, pertama keluar.
- Item terbaru harus ditangani terlebih dahulu, undo, kembali, panggilan bersarang: sebuah tumpukan, karena terakhir masuk, pertama keluar.
- Item sering disisipkan atau dihapus di tengah koleksi yang terurut, dan ukurannya tidak diketahui: sebuah daftar terhubung, karena hanya pointer yang berubah dan tidak ada yang digeser.
- Sebutkan struktur, sebutkan aturannya, hubungkan aturan dengan situasi.
Cocokkan setiap ADT dengan aturannya dan penggunaan tipikalnya.
Stack = last-in-first-out; antrian = first-in-first-out; daftar terhubung merantai node dengan pointer.
Job pencetakan harus dicetak sesuai urutan kiriman. ADT manakah, dan mengapa?
Ur kedatangan adalah aturan FIFO. Stack akan mencetak job terbaru terlebih dahulu.
ADT versus implementasi
- ADT adalah perilaku: push dan pop, enqueue dan dequeue, insert dan traverse.
- Implementasi adalah penyimpanan: dalam kursus ini, array ditambah beberapa variabel pointer (pelajaran berikutnya).
- Pertanyaan tentang ADT meminta operasi dan aturan; pertanyaan tentang implementasi meminta array, pointer dan pengecekan.
⟦⟧ Nilai yang sering terlewat
- Push dan enqueue menguji penuh terlebih dahulu; pop dan dequeue menguji kosong terlebih dahulu. Tulis pengecekan ke dalam deskripsi.
- Menyisipkan ke dalam daftar terhubung: atur pointer node baru sebelum mengubah pointer node sebelumnya, atau sisa daftar akan hilang.
- Tumpukan berubah di satu ujung, antrean di kedua ujung. "Hapus dari atas antrean" adalah jawaban tumpukan.
- Jabarkan singkatan sekali: LIFO, last in first out; FIFO, first in first out.
Anda telah memahaminya
- ADT adalah kumpulan data bersama dengan serangkaian operasi di atasnya; perilaku, bukan penyimpanan
- tumpukan: tambah dan hapus di atas, LIFO, push dan pop · antrean: tambah di belakang, hapus di depan, FIFO, enqueue dan dequeue
- daftar terhubung: node nilai + pointer dari pointer kepala; murah insert dan delete, lambat random access; traversing dengan mengikuti pointer
- membenarkan dengan aturan: urutan kedatangan → antrean; terbaru dulu → tumpukan; penyisipan sering di tengah → daftar terhubung