BAB 3
STACK DAN QUEUE
1.
STACK
A.
DAFTAR
LINEAR
Sebuah
daftar linear atau linear list, merupakan suatu struktur data umum yang
terbentuk dari barisan hingga (yang terurut) dari satuan data ataupun dari
record. Untuk mudahnya, elemen yang terdapat di dalam daftar disebut dengan
simpul atau node. Daftar disebut linear (lurus), karena elemen tampak seperti
berbaris, yakni bahwa setiap simpul, kecuali yang pertama dan yang terakhir,
selalu memiliki sebuah elemen penerus langsung (suksesor langsung) dan sebuah
elemen pendahulu langsung (predesesor langsung).
Di
sini, banyak simpul atau elemen, tersebut dapat berubah – ubah, berbeda dengan
array yang banyak elemennya selalu tetap. Kita menyatakan linear list A yang
mengandung T elemen pada suatu saat, sebagai A = [A1, A2, … AT]. Jika T = 0,
maka A disebut list hampa atau null list.
Suatu
elemen dapat dihilangkan atau dihapus (deletion) dari sembarang posisi dalam linear
list, dan suatu elemen baru dapat pula dimasukkan (insertion) sebagai anggota
list pada posisi sembarang (di mana saja).
File,
merupakan salah satu contoh dari daftar linear yang elemen-elemennya berupa
record. Selain file, contoh lain dari daftar linear adalah stack atau tumpukan,
queue atau antrean, dan daftar berkait atau linear linked list atau one-way
list. Pada Bab 3 ini kita bahas tentang stack tersebut.
B.
STACK
atau TUMPUKAN
Stack atau tumpukan adalah bentuk
khusus dari liniear list. Pada stack, penghapusan serta pemasukan elemennya
hanya dapat dilakukan di satu posisi, yakni posisi akhir dari list. Posisi ini
disebut puncak atau top dari stack. Elemen stack S pada posisi ini dinyatakan
dengan TOP(S).
Jelasnya, bila stack S [S1, S2, …,
ST], maka TOP(S) adalah ST. Banyaknya elemen stack S pada suatu saat tertentu
biasa kita sebut sebagai NOELS(S). Jadi untuk stack kita di atas, NOEL(S) =
T. Seperti halnya pada semua linear
list, pada stack dikenal operasi penghapusan dan pemasukan.
Operator penghapusan elemen pada
stack disebut POP, sedangkan operator pemasukan elemen, disebut PUSH. Untuk menggambarkan
kerja kedua operator di atas, berikut ini suatu contoh bermula dari stack hampa
S [], yang kita gambar sebagai :
Mula-mula
kita PUSH elemen A, diperoleh Stack S = [A]
Apabila
kemudian kita PUSH elemen B, diperoleh Stack S = [A, B]
Selanjutnya
bila PUSH elemen C, diperoleh Stack S = [A,B,C]
Kemudian
bila kita POP elemen C, diperoleh Stack S = [A.B]
Kita dapat
pula PUSH 2 elemen D dan E. Akan dihasilkan Stack S = [A,B,D,E]
Terlihat bahwa kedua operasi di
atas, pada stack adalah bersifat ‘terakhir masuk pertama keluar’ atau ‘last in
first out (LIFO)’. Pada hakekatnya kita tidak membatasi berapa banyak elemen
dapat masuk ke dalam stack. Untuk suatu stack S[S1, S2, …, SNOEL], kita katakana
bahwa elemen Si, berada di atas elemen Sj, jika I lebih besar dari j. Suatu
elemen tidak dapat kita POP ke luar, sebelum semua elemen di atasnya
dikeluarkan.
C.
OPERASI
PADA STACK
Terdapat empat operasi pada stack,
yakni CREATE (stack), ISEMPTY (stack), PUSH (elemen, stack), dan POP (stack).
CREATE(S) adalah operator yang menyebabkan stack S menjadi satu stack hampa.
Jadi NOEL (CREATE(S)) adalah 0, dan TOP (CREATE(S)) tak terdefinisi.
Sedangkan operator ISEMPTY(S)
bermaksud memeriksa apakah stack S hamper atau tidak. Operandnya adalah data
bertipe stack, sedangkan hasilnya merupakan data bertipe Boolean. ISEMPTY(S)
adalah true, jika S hampa, yakni bila NOELS(S) = 0, dan false dalam hal lain.
Jelas bahwa ISEMPTY(CREATE(S)) adalah true.
Operator PUSH (E,S) akan bekerja
menambahkan elemen E pada stack S. E ditempatkan sebagai TOP(S). Operator
POP(S) merupakan operator yang bekerja mengeluarkan elemen TOP(S) dari dalam
stack. POP(S) akan mengurangi nilai NOEL(S) dengan 1. Suatu kesalahan akan
terjadi apabila, kita mencoba melakukan POP(s) terhadap stack S yang hampa
Kesalahan overflow akan terjadi,
jika kita melakukan operasi pemasukan data (PUSH) pada stack yang sudah penuh
(dalam hal ini jika banyaknya elemen yang kita masukan ke dalam sebuah stack
sudah melampaui batas kemampuan memori atau telah didefinisikan sebelumnya).
Sebaliknya, kesalahan underflow akan
terjadi jika stack sudah dalam keadaan hampa, kita lakukan operasi pengeluaran
atau penghapusan (POP).
2. QUEUE
A.
PENGERTIAN
QUEUE (ANTREAN)
Struktur data antrean atau queue
adalah suatu bentuk khusus dari linear list, dengan operasi penyisipan
(insertion) hanya di perbolehkan pada salah satu sisi, yang disebut sisi
belakang (REAR), dan operasi penghapusan (deletion) hanya diperbolehkan pada
sisi lainnya, yang disebut sisi depan (FRONT), dari list.
Sebagai contoh dapat kita lihat
antrean (Q1, Q2, …, Qn). Kita notasikan bagian depan dari antrian Q sebagai
FRONT(Q) dan bagian belakang sebagai REAR(Q).
Jadi untuk antrean Q = [Q1, Q2, …,
Qn] :
FRONT(Q) = Q1 dan REAR(Q)=
Qn
Kita menggunakan notasi NOEL(Q)
untuk menyatakan jumlah elemen di dalam antrean Q. NOEL(Q) mempunyai harga
integer. Untuk antrean Q = [Q1Q2, . . ., Qn], maka NOEL(Q) = N.
Operator penyisipan (insertion)
disebut INSERT dan operator penghapusan (deletion) disebut REMOVE.
Sebagai contoh untuk memperjelas
bekerjanya antrean, kita perhatikan sederetan operasi berikut. Kita mulai
dengan antrean hampa Q. Antrean hampa Q, atau Q[] dapat di sajikan seperti
terlihat pada gambar di bawah ini :
Di sini
:
NOEL(Q) = 0
FRONT(Q) = tidak terdefinisi
REAR(Q) = tidak terdefinisi
Lalu
kita INSERT elemen A, diperoleh Q = [A], seperti terlihat di gambar ini :
Disini
:
NOEL(Q) = 1
FRONT(Q) = A
REAR(Q) = A
Dilanjutkan dengan INSERT elemen B,
sehingga diperoleh Q = [A,B], seperti terlihat di bawah ini :
Di sini
;
NOEL(Q) = 2
FRONT(Q) = A
REAR(Q) = B
Dilanjutkan dengan INSERT elemen C,
sehingga diperoleh Q = [A, B, C], seperti terlihat di bawah ini :
Di sini
:
NOEL(Q) = 3
FRONT(Q) = A
REAR(Q) = C
Dilanjutkan dengan DELETE satu
elemen dari Q, sehingga diperoleh Q = [B, C], seperti terlihat di bawah ini :
Di sini
:
NOEL(Q) = 2
FRONT(Q) = B
REAR(Q) = C
Demikian seterusnya, kita dapat
melakukan serangkaian INSERT dan DELETE yang lain. Suatu kesalahan underflow
dapat terjadi, yakni apabila kita melakukan penghapusan pada antrean hampa. Antrean
dikatakan beroprasi dalam cara FIRST-IN-FIRST-OUT (FIFO). Disebut demikian
karena elemen yang pertama masuk merupakan elemen yang pertama ke luar.
Model antrean, sangat sering
ditemukan dalam kejadian sehari-hari, seperti mobil yang menunggu untuk
pengisian bahan bakar, mobil pertama dari antrean merupakan mobil pertama yang
akan keluar dari antrean. Sebagai contoh lain adalah orang yang menunggu dalam
antrean di suatu bank. Orang pertama yang berada di dalam barisan tersebut akan
merupakan orang pertama yang akan dilayani.
B.
OPERASI
DASAR PADA ANTREAN
Ada 4
operasi dasar yang dapat dilakukan pada struktur data antrean, yakni :
a)
CREATE(antrean)
b)
ISEMPTY(antrean)
c)
INSERT(elemen,antrean)
d)
REMOVE(antrean)
Pandang
misalnya antrean Q = [Q1, Q2, …, QNOEL], maka :
CREAT(antrean)
:
CREAT(Q)
adalah suatu operator untuk membentuk dan menunjukkan suatu antrean hampa Q.
Berarti
:
NOEL(CREATE(Q))
= 0
FRONT(CREATE(Q))=
tidak terdefinisikan
REAR(CREATE(Q))
= tidak terdefinisikan
ISEMPTY
(antrean)
ISEMPTY(Q)
adalah operator yang menentukan apakah antrean Q hampa atau tidak. Operand dari
operator ini merupakan antrean, sedangkan hasilnya merupakan tipe data Boolean.
Di sini
:
ISEMPTY
(antrean) = true, jika Q hampa, yakni jika NOEL(Q)=0
=
false, dalam hal lain.
Maka, ISEMPTY(CREATE(Q))
= true
INSERT(elemen,
antrean)
INSERT(E,Q)
adalah operator yang memasukkan elemen E ke dalam antrean Q. Elemen E
ditempatkan di bagian belakang dari antrean. Hasil dari operasi ini adalah
antrean yang lebih panjang.
REAR(INSERT(E,Q)) = E
QNOEL adalah
E
ISEMPTY(INSERT(E,Q))
= false
REMOVE
(antrean)
REMOVE(Q)
adalah operator yang menghapus elemen bagian depan dari Antrean Q. Hasilnya
merupakan antrean yang lebih pendek. Pada setiap operasi ini, harga dari
NOEL(Q) berkurang satu, dan elemen kedua dari Q menjadi elemen terdepan.
Jika NOEL(Q) = 0, maka
REMOVE(Q) memberikan suatu kondisi error, yakni suatu underflow. Jelas bahwa
REMOVE(CREATE(Q)) juga memberikan kondisi underflow error.
