Stack dan
Queue
HERMAWAN ARIEF P
Stack
Stack merupakan struktur data yang mengikuti pola
tumpukan dari benda.
List (urutan) dimana penambahan dan pengambilan elemen
hanya dilakukan pada satu sisi yang disebut top (puncak)
dari stack.
Berlaku aturan LIFO (Last In First Out)
Dua operasi dasar pada stack adalah PUSH dan POP
Operasi dasar
1. Operasi menciptakan S sebagai stack kosong (Inisialisasi S -> stack)
2. Operasi menyisipkan elemen x ke stack S untuk memperbaharui stack S (Push
(S,x,t) -> stack) dimana t adalah indeks puncak (top of stack atau top pointer)
3. Operasi menghilangkan elemen puncak stack S (Pop (S,x,t) -> stack)
4. Operasi mengirimkan elemen puncak stack S tanpa memperbaharui/merubah
stack S (Top(S,x,t) -> item )
5. Operasi memeriksa jika stack S kosong (Empty (S) -> boolean (true/false))
6. Operasi memeriksa jika stack S penuh (Full (S) -> boolean (true/false))
7. Operasi menghitung jumlah elemen stack S (eNumber (S) -> integer)
Pseudocode-initialisasi
Procedure Inisialisasi(var S : tumpukan);
begin
S. banyak-> 0
end;
Pseudocode-cek penuh
Function PENUHS(S : tumpukan): boolean;
begin
Jika [Link] = maxelm maka PENUHS -> true
else PENUHS ->false
end;
Pseudocode-cek kosong
Function KOSONGS(S : tumpukan):boolean;
begin
If [Link] = 0 then KOSONGS -> true
else KOSONGS->false
end;
Pseudocode-PUSH
Procedure PUSH(data : tipeelemen; var S : tumpukan);
begin
If not KOSONGS(S) then
begin
[Link] -> [Link] +1
[Link][[Link]]¬data
end
else
Tampilkan pesan kesalahan "Stack Penuh"
end;
Pseudocode-POP
Procedure POP(var S : tumpukan; var data : typeelemen);
begin
If not KOSONGS(S) then
begin
Data->[Link][[Link]]
[Link] -> [Link] - 1
end
else
Tampilkan pesan kesalahan "Stack kosong"
End;
QUEUE
Queue jika diartikan secara harafiah berarti antrian
Konsep utamanya adalah FIFO atau FIFS ( First In First Out
atau First In First Serve ).
Dua operasi dasar: Enqueue dan Dequeue
Istilah pada queue
1. Elemen antrian : Item-item data yang terdapat/diorganisasikan pada antrian
2. Front: Elemen terdepan dari antrian
3. Tail: Elemen terakhir dari antrian
4. Panjang Antrian
Yaitu banyaknya (jumlah) elemen pada antrian, ada dua jenis panjang:
A. Panjang aktual : merepresentasikan banyak item data pada antrian pada
suatunsaat.
B. Kapasitas antrian : panjang maksimum yang diizinkan pada antrian
Istilah pada queue
5. Status
Kosong: Bila tidak ada elemen pada antrian, pada kondisi ini tidak mungkin
dilakukan operasi DeQueue terhadap antrian. DeQueue pada antrian/queue
kosong menyebabkan kondisi keselahan Underflow
Isi tapi tidak penuh: Bila paling sedikit terdapat satu elemen pada antrian dan
paling banyak (n-1) elemen, dimana n adalah kapasitas antrian.
Penuh: Bila jumlah elemen pada antrian mencapai kapasitas antrian. Pada
kondisi ini tidak mungkin dilakukan operasi EnQueue terhadap antrian.
Penambahan elemen baru (EnQueue) menyebabkan kondidi overflow.
Operasi Dasar
1) Create : menciptakan suatu antrian kosong
2) CekStatus : memeriksa status antrian pada suatu saat,
Ada dua kondisi penting pada CekStatus : Empty dan Full
3) EnQueue : menyisipkan sebuah elemen baru pada antrian
4) DeQueue : menghapus/mengeluarkan sebuah elemen dari antrian
5) Clear : mengosongkan antrian
Pseudocode-Create
Procedure Create;
Begin
Front := 1;
Tail := 0;
End;
Pseudocode-CekStatus
Function Empty : Boolean ; Function Full : Boolean ;
Begin Begin
If Tail = 0 If Tail = MaxQueue
then Empty := true then Full := true
else Empty := false else Full := false
end; end;
Pseudocode-EnQueue
Procedure EnQueue ( Databaru:TipeData )
Begin
If not Full then
begin
Tail := Tail + 1
Queue [ Tail ] := DataBaru
End;
End
Pseudocode-DeQueue
Procedure DeQueue For i := 1 to Tail - 1
( DataServe :TipeData )
Do
Begin
Queue [ i ] := Queue [ i +
If not Empty then 1 ]
begin Tail := Tail – 1
DataServe := Queue [ Front End;
]
End;
Pseudocode-Clear
Procedure Clear ;
Begin
Tail := 0;
End;