Definisi
Struktur data linear adalah kumpulan komponen-komponen yang tersusun membentuk satu garis linear. Bila komponen-komponen ditambahkan (atau dikurangi), maka struktur-struktur tersebut berkembang (atau menyusut).
* Stack: struktur data linear dimana penambahan atau pengurangan komponen dilakukan di satu ujung saja.
* Queue: struktur data linear dimana penambahan komponen dilakukan di satu ujung, sementara pengurangan dilakukan di ujung lain (yang satu lagi).
Kedua struktur tersebut merupakan struktur data abstraks dimana implementasi pada tingkat lebih rendah dapat menggunakan struktur sikuensial (array) atau struktur berkait (linear linked-list).
Manfaat Stack:
* pengolahan struktur yang "nested" (berisi salinan dirinya sendiri di dalam dirinya), misalnya pengolahan ekspresi aljabar, himpunan dari himpunan.
* implementasi algoritma parsing, evaluasi dan backtracking.
* digunakan OS untuk memungkinkan pemanggilan prosedur secara nested.
* digunakan untuk memungkinkan konversi program rekursif menjadi non-rekursif.
* untuk mendukung mekanisme Pushdown Automata (PDA)
* untuk medukung kompailer mengkonversi infix menjadi postfix dan kemudian mengevaluasi postfix menjadi atomic (assembly) command
Manfaat Queue
* digunakan OS untuk mengatur eksekusi task dalam suatu sistem untuk mencapai perlakuan yang "adil" (seringkali queue disebut waiting line)
* untuk mailbox dalam komunikasi antar proses
* untuk buffer dalam mekanisme printspooler, komunikasi data
* untuk simulasi dan modeling (misalnya simulasi sistem pengendali lalu lintas udara) dalam memprediksi performance
Spesifikasi ADT Stack
* Membuat dan menginisialisasi stack S
S = new Stack(); Pemeriksaan boolean yang benar jika stack S kosong
*
S.empty(); Menaruh item X paling atas dalam stack S
*
S.push(X); Mengambil item paling atas dari stack S dan merefernya oleh X
*
X = S.pop();
* Mendapatkan salinan dari item teratas dari stack S dan merefernya oleh X
X = S.peek();
Spesifikasi ADT Queue
* Membuat dan menginisialisasi queue Q
Q = new Queue(); Pemeriksaan boolean yang benar jika queue S kosong
*
Q.empty(); Menaruh item X di belakang queue Q
*
Q.insert(X); Mengambil item paling depan dari queue Q dan merefernya oleh X
*
X = Q.remove();
Implementasi ADT Stack
Spesifikasi stack tsb dapat diimplementasikan di level yang lebih rendah baik dengan array ataupun linear linked-list. Selain obyek array itu sendiri, dalam implementasi array diperlukan suatu variabel yang menunjukkan jumlah sel dalam array yang telah terisi. Variabel ini (kita namakan count) diinisialisasi 0 dan akan bertambah setiap metoda push() dijalankan, dan akan berkurang satu setiap metoda pop() dijalankan. Variable count ini juga menunjukkan sel mana dalam array yang akan diisi berikutnya. Untuk memungkinkan array bersifat unbounded (tak berbatas) maka perlu ditambahkan suatu mekanisme untuk memperbesar kapasitas Stack saat count mencapai panjang array saat itu. Perbesaran kapasitas stack dilakukan dengan men-create array yang lebih panjang dari yang sekarang, mengcopy isi array yang sekarang ke yang baru lalu yang baru menggantikan yang lama.
Dalam implementasi linear linked-list, operasi push() dan pop() adalah operasi penyisipan dan penghapusan di awal linked-list. Untuk mengetahui dengan cepat jumlah item yang tersimpan dalam stack maka variabel count dapat pula digunakan disini.
Coding implementasi selengkapnya:
* implementasi array
* implementasi linked list
Implementasi ADT Queue
Seperti halnya stack spesifikasi queue tsb dapat diimplementasikan di level yang lebih rendah baik dengan array ataupun linear linked list. Dalam implementasi array, konsep circular-array dapat diaplikasikan untuk menghindari operasi penggeseran isi array saat dilakukan pop(). Dalam konsep circular array, inkrementasi indeks array yang panjangnya n, selalu di modulo dengan panjang array tsb. sehingga variabel indeks yang semula berharga n-1 jika diinkremen akan "wrap-around" ke 0. Untuk mengetahui posisi ujung-ujung dari item data yang disimpan dalam array, digunakan variabel indeks front (menunjuk ke posisi item yang akan diambil berikutnya) dan rear (posisi elemen array berikutnya yang akan ditempati). Suatu variabel count digunakan untuk mengetahui kasus khusus: apakah queue kosong atau penuh. Jika penuh maka mekanisme memperbesar kapasitas queue dapat diaplikasikan (lihat penjelasan Stack di atas).
Dalam implementasi linera linked-list, maka bagian muka dari queue adalah awal dari list (di-pop dengan delete-first) dan bagian belakang adalah akhir dari list (di-push dengan insert-last). Mengingat operasi insert-last sering dilakukan maka digunakan dua variabel referensi yang digunakan sebagai pointer: front untuk node pertama dari list dan rear utuk node paling akhir.
Coding implementasi selengkapnya:
* implementasi array
* implementasi linked list
Contoh penggunaan Stack: memeriksa keseimbangan tanda kurung dalam ekspresi aljabar
Dalam metematika penulisan ekpresi aljabar bisa menggunakan tanda-tanda kurung untuk memungkinkan struktur yang nested. Suatu substruktur di batasi oleh pasangan tanda kurung "(" dengan ")", atau "{" dengan "}", atau "[" dengan "]". Kesalahan penulisan ekspresi terjadi jika pasangan tanda tersebut tidak cocok atau salah satu dari pasangan tidak ada.
Pemeriksaan dilakukan dengan menyimpan kurung buka hingga muncul kurung buka pasangannya. Karena suatu substruktur selalu berada di dalam suprastrukturnya sehingga
* kurung buka substruktur akan muncul setelah kurung buka suprastrukturnya, dan
* kurung tutup substruktur akan muncul sebelum kurung tutup suprastrukturnya
Maka, stack digunakan untuk menyimpan kurung buka suatu struktur hingga diperoleh pasangan kurung tutupnya.
Untuk selengkapnya lihat source code class program utamanya nya yang menggunakan class yang melakukan proses tersebut.
Contoh: Interpreter Postfix
Contoh lain penggunaan stack adalah pemeriksaan dan eksekusi ekpresi postfix. Ekspresi postfix merupakan ekpresi dengan aturan L R B dengan L adalah operand kiri, R operand kanan dan B adalah operatornya. Ekspresi yang kita biasa gunakan sehari-hari adalah ekspresi infix dengan aturan L B R. Contoh, jika ekspresi infixnya "6*7-2" maka ekspresi postfixnya adalah "6 7 * 2 -".
Ekspresi postfix ini memiliki kelebihan, yaitu menyimpan urutan eksekusi secara nested sementara pada ekspresi infix urutan eksekusi ini dinyatakan dengan bantuan tanda kurung serta adanya tingkatan/orde dari operand. Kenyataan ini menjadikan ekspresi postfix digunakan oleh compiler sebagai representasi ekspresi aljabar sebelum diterjemahkan ke dalam unit-unit perintah level bawah. Jadi biasanya copiler melakukan konversi dari infix ke postfix dan kemudian ke assembler (atau langsung ke bahasa mesin).
Karena strukturnya "nested" maka stack digunakan untuk menyimpan operand L dan R dan mengambilnya kembali saat ketemu operator B, mengeksekusinya kemudian hasilnya (karena juga bisa merupakan operand pada supra strukturnya) dikembalikan ke stack untuk memeriksa relasi postfix berikutnya.
Berikut ini adalah program code-nya.
Contoh: Program membaca & menulis pencetakan isi buffer
Buffer adalah queue yang akan menerima setiap apa yang "dituliskan" ke bagian paling belakang dari queue sementara jika "dibaca" maka item yang paling depan yang diambil.
void writeLineToBePrinted() { // the CPU's task
if ( (there is a line L to print) &&
(the print buffer is neither full nor busy) ) {
printBufferQueue.insert(L);
}
}
void readLineToBePrinted() { // the Printer's task
if (the print buffer is neither empty nor busy) {
L = printBufferQueue.remove();
(print line L on the Printer);
}
}
Bagaimana OS menangani pemanggilan rekursif
Berikut ini adalah suatu metoda rekursif.
double factorial( int n) {
if (n <= 1) {
return 1.0;
} else {
return n * factorial( n - 1 );
}
}
