Mengimplementasikan ADT menggunakan array
| English | Bahasa Indonesia |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | overflow |
| underflow/ˌʌndəˈfləʊ/ | underflow |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | array melingkar |
| free list/friː lɪst/ | daftar bebas |
Tidak ada tumpukan di memori
- Buka komputer dan carilah tumpukan. Anda tidak akan menemukannya. Memori adalah satu array besar sel bernomor, dan itu semua yang ada.
- Setiap tumpukan, setiap antrean, setiap daftar terhubung adalah array itu ditambah dua atau tiga variabel integer yang mengingat di mana letaknya. Push adalah "tambah satu ke angka dan simpan"; dequeue adalah "baca sel dan tambah satu ke angka berbeda".
- Keseluruhan pelajaran ini adalah pencatatan: pointer mana, pengecekan mana, dan apa yang terjadi di tepi.
- Ujian meminta Anda untuk mendeskripsikan deklarasi, berjalan melewati pointer melalui beberapa operasi, dan mengatakan mengapa pengecekan ada di sana.
Tumpukan dalam array
- Pegang item dalam
Stack[1:MaxSize]dengan integerTop, 0 ketika tumpukan kosong. - Push(x): jika
Top = MaxSizetumpukan penuh, overflow; sebaliknyaTop ← Top + 1danStack[Top] ← x. - Pop(): jika
Top = 0tumpukan kosong, underflow; sebaliknya kembalikanStack[Top]danTop ← Top − 1.
Array tidak pernah bergerak; hanya Top yang
Menyisipkan item ke dalam stack yang sudah penuh menyebabkan tumpukan ______.
Overflow = dorong saat Top = MaxSize; mengambil dari stack kosong (Top = 0) adalah underflow.
Cocokkan setiap kondisi array-stack dengan artinya.
Top menghitung jumlah item: 0 = kosong, MaxSize = penuh; dua kasus error adalah underflow dan overflow.
Contoh terpecahkan: deklarasikan dan inisialisasi tumpukan
- Jelaskan deklarasi dan inisialisasi yang diperlukan untuk mengimplementasikan tumpukan hingga 50 bilangan bulat menggunakan array. [5]
- Array 50 elemen tipe
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, untuk menyimpan item. - Konstanta atau variabel
MaxSizediatur ke 50, sehingga push dapat menguji apakah penuh. - Sebuah
INTEGERpointer atas-tumpukan,Top, diinisialisasi ke 0 untuk menunjukkan tumpukan kosong; pop mengujinya untuk underflow, dan push membandingkannya denganMaxSizeuntuk overflow.
Manakah yang termasuk dalam deklarasi dan inisialisasi stack berbasis array? Pilih semua yang berlaku.
Stack memerlukan satu pointer, Top. Pointer depan milik antrian.
Antrean dalam array biasa
- Dua pointer:
Frontuntuk item berikutnya yang keluar,Rearuntuk ruang bebas berikutnya. Enqueue menyimpan diReardan memindahkannya; dequeue membaca diFrontdan memindahkannya. - Kedua pointer hanya ever bergerak maju, jadi setelah beberapa operasi mereka melangkah menjauhi akhir array sementara sel-sel di awal duduk kosong dan tidak terpakai.
- Solusinya adalah membiarkan pointer membungkus kembali.
Array melingkar
- Array melingkar membungkus pointer kembali ke sel pertama ketika melewati yang terakhir: dengan indeks 1-based,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): periksa tidak penuh;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): periksa tidak kosong; kembalikanQueue[Front];Front ← (Front MOD MaxSize) + 1. - Jaga count terpisah: ketika antrean benar-benar penuh dan ketika benar-benar kosong, dua pointer berada dalam posisi relatif yang sama, sehingga pointer saja tidak bisa membedakan keduanya.
Setelah sel terakhir datang sel pertama
Mengimplementasikan ADT dengan array
FIFO
Antrian (antrean) bersifat first-in-first-out — enqueue di belakang, dequeue dari depan.
Mengapa menggunakan array melingkar untuk antrian?
Antrian linear membuang sel-sel di awal saat Front maju; melingkari dengan MOD mengisinya kembali.
Antrian melingkar menggunakan MOD agar pointer front/rear melingkari dan mengisi kembali sel-sel yang dibebaskan di awal array.
(pointer MOD MaxSize) + 1 melingkari indeks kembali ke sel pertama, sehingga antrian linear tidak lagi membuang sel-sel yang telah dilewati Front.
Contoh terpecahkan: berjalan pada pointer
- Dengan
MaxSize = 6: jikaRear = 5, maka(5 MOD 6) + 1 = 6, sehingga item berikutnya masuk ke sel 6. JikaRear = 6, maka(6 MOD 6) + 1 = 1: pointer membungkus ke sel 1. - Antrian melingkar disimpan dalam array berukuran 5, indeks 0 hingga 4, dengan
Front = 3,Rear = 3dan satu item tersimpan. Dua item ditambahkan, kemudian dua dihapus. Dengan indeks berbasis-0, setiap perpindahan adalah(pointer + 1) MOD 5. - Menambah dua kali menggerakkan
Rear: 3 → 4, lalu 4 → 0, karena (4 + 1) MOD 5 = 0. Menghapus dua kali menggerakkanFront: 3 → 4 → 0. Satu item tersisa, pada indeks 0, dan antrian menggunakan kembali sel yang dibebaskan di awal array.
Antrian melingkar menggunakan sel 1 sampai 6 dan Rear = 6. Setelah Rear ← (Rear MOD 6) + 1, ke mana item berikutnya masuk?
6 MOD 6 = 0, ditambah 1 menghasilkan 1. Pointer melingkari ke awal array.
Contoh terpecahkan: algoritma enqueue dengan kata-kata
- Jelaskan algoritma untuk menambahkan item ke dalam antrian melingkar. [4]
- Jika count sama dengan size, laporkan bahwa antrian penuh dan hentikan.
- Jika tidak, tambahkan satu pada rear pointer; jika sekarang melebihi indeks terakhir, atur menjadi indeks pertama.
- Simpan item pada rear pointer dan tambahkan satu pada count.
Susun langkah-langkah menambahkan ke dalam antrian melingkar secara berurutan.
Periksa, geser, lingersi, simpan, hitung. Penglingeran inilah yang menjadikan array tersebut melingkar.
Daftar terhubung dalam array
- Gunakan array dari record node, masing-masing memiliki
Nextindeks;-1menandai akhir.Headindeks menandai node pertama,-1jika list kosong. - Slot yang tidak terpakai dirantai ke dalam free list dari
FreeListHead, persis seperti bagaimana data list merantai yang digunakan.
TYPE TNode
DECLARE Value : INTEGER
DECLARE Next : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- Sisipkan: ambil slot di
FreeListHead, aturValuedanNext-nya, lalu sambung ulangNextnode sebelumnya atauHead. Hapus: putuskan tautan node dan kembalikan slotnya ke depan free list.
Dua list berbagi satu array: data list dan free list
Dalam daftar linked berbasis array, daftar kosong (free list):
Daftar kosong menghubungkan slot-slot cadangan, sehingga saat insert dapat mengambil satu dan saat delete dapat mengembalikannya — seperti daftar linked kedua dari slot kosong.
Contoh terpecahkan: sisipkan ke dalam list yang disimpan array
- Array
DatadanPointermenyimpan list 1 → 3 → 4, denganStart = 1; indeks 1 memegangD40, indeks 3 memegangD32, indeks 4 memegangD11dengan pointer null. Free list dimulai dari indeks 2 dan berlanjut 2 → 5. SisipkanD6antaraD32danD11. - Ambil node bebas pertama, indeks 2, dan atur
FreeStartke pointer-nya, yaitu 5. SimpanD6diData[2]. - Atur
Pointer[2]ke nilaiPointer[3]yang dipegang, yaitu 4. Kemudian aturPointer[3]ke 2. - List kini terbaca 1 → 3 → 2 → 4 dan free list adalah 5 → null. Implementasi, jika diminta: array untuk data, array paralel (atau field record) untuk pointer, pointer start, dan pointer free-list.
Pada contoh terpecahkan, setelah D6 disisipkan, daftar kosong dimulai pada indeks ____.
Indeks 2 diambil dari daftar kosong, sehingga FreeStart berpindah ke apa yang ditunjuk oleh indeks 2, yaitu 5.
Saat menyisipkan ke dalam daftar, pointer node sebelumnya harus diubah sebelum pointer node baru ditetapkan.
Tetapkan pointer node baru ke node berikutnya lama terlebih dahulu. Mengkabel ulang node sebelumnya terlebih dahulu akan kehilangan alamat sisa daftar.
⟦⟧ Nilai yang sering terlewat
- Pemeriksaan dilakukan terlebih dahulu: penuh sebelum push atau enqueue, kosong sebelum pop atau dequeue. Jelaskan pemeriksaan; mereka memberikan poin.
- Rumus pembungkus bergantung pada indeks:
(Rear MOD MaxSize) + 1untuk berbasis-1,(Rear + 1) MOD Sizeuntuk berbasis-0. Sesuaikan dengan batas pertanyaan. - Count adalah apa yang membedakan antrian melingkar penuh dari kosong. Pointer saja tidak dapat melakukannya.
- Atur
Nextnode baru sebelum menyambung ulang node sebelumnya, dan kembalikan slot node yang dihapus ke free list, atau array perlahan akan terisi dengan sel yang tidak terjangkau.
Anda telah memahaminya
- stack dalam array:
Stack[1:MaxSize]dan pointerTopdimulai dari 0;Top = MaxSizeadalah overflow,Top = 0adalah underflow - antrian melingkar:
FrontdanRearmembungkus denganMOD; count terpisah membedakan penuh dari kosong - daftar terhubung dalam array: record node dengan indeks
Next,Head, dan free list yang merantai slot cadangan - setiap operasi adalah pemeriksaan, lalu aritmatika pointer, lalu simpan atau baca; perilaku ADT tidak berubah oleh cara penyimpanannya