Struktur Data Linear

8 Maret 1999

Definisi

• 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

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

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

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

Contoh: Interpreter Postfix

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

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 );
   }
}