STACK & QUEUE
STACK
Dalam istilah bahasa Indonesia, berarti
tumpukan.
Dalam istilah struktur data, berarti setiap
akses data (baik penambahan atau
pengurangan data) hanya dapat dilakukan
pada satu ujung saja (TOP).
Ada 2 istilah dalam operasi stack
PUSH : penambahan data (insert / add)
POP : pengurangan / penghapusan data
(delete)
Contoh Stack
DELETE
TOP
TOP
TOP
PUSH A
PUSH B
POP
Proses Push dan Pop pada Stack
TOP
Penggunaan Vektor untuk Stack
Ada 2 data penting
Maxstack = data yang menunjukkan
jumlah maksimum elemen stack yang
dapat disimpan dalam vector
TOP, variabel yang bertujuan mencatat
lokasi puncak dari stack.
Penggunaan Vektor untuk Stack
INITIALIZE (S)
MaxStack = 3
Push (S,a)
Push (S,b)
Push (S,c)
Push (S,d)
Delete (S,x)
Delete (S,y)
Delete (S,z)
message
full stack
a
1
4
message
empty
stack
b
a
6
a
7
Procedure & Function dlm Stack
1.
2.
Function Full (S : Stacktype)
{untuk mengetahui apakah S sudah penuh atau belum}
BEGIN
Full := ([Link] = maxstack)
END
Jika Stack S full, maka nilai ini = true, atau jika S belum
penuh, maka nilai menunjukkan false.
Function Empty (S : Stacktype)
{untuk mengetahui apakah S sudah kosong atau belum}
BEGIN
Empty := ([Link] = 0)
END
Jika stack S empty, maka nilai = true, jika stack S tidak
kosong nilai = false.
Procedure & Function dlm Stack
3. Function Top Value : Tdata
BEGIN
Top_Value := [Link][[Link]]
END
4. Function Pop : Tdata
BEGIN
Pop := [Link] [[Link]];
[Link] := [Link] 1;
END
5. Procedure Push (Data :Tdata)
BEGIN
[Link] := [Link] + 1
[Link][[Link]] := Data
END
Queue
Dalam Bahasa Indonesia disebut antrian.
Contoh antrian di loket FIFO (First In
First Out)
Dalam struktur data, semua akses insert
mengambil tempat pada satu ujung akhir
(REAR), sedangkan semua akses delete
mengambil tempat pada ujung lainnya
(FRONT)
FRONT (head) : menunjuk pada elemen
pertama yang ada dalam queue.
REAR (tail) : menunjuk pada elemen
terakhir yang ada dalam queue.
Queue
Keadaan awal dari queue adalah
F=R=0 (queue dalam keadaan
kosong / empty queue)
Data yang masuk dalam queue, akan
masuk dari bagian belakang (REAR)
Data yang dihapus dari queue, akan
dihapus dari bagian depan (FRONT)
Contoh Queue
Delete
Insert
F = R =0
insert A
Delete
F=R=1
insert B
insert C
F=2 R=3
F=1
R=2
F=1
Delete
C
F=R=3
C
R=3
Delete
F=R=0
Kelemahan Queue
Walaupun masih ada tempat kosong
dalam queue, tetapi bila R=F=Max
queue, maka tidak dapat dilakukan
penambahan elemen ke dalam
queue.
Circular Queue
i
1
3
Pada Circular queue,
meskipun REAR =
maxqueue, tetap
dapat menambahkan
elemen lagi ke
dalamnya selama
masih ada tempat
yang tersedia dalam
queue, hal ini
menyebabkan nilai
REAR dapat lebih
kecil dari nilai FRONT.
Contoh Circular Queue
Misal : ada 4 elemen
(j1-j4 dengan n>4)
if R = n-1 then R 0
else R R+1
add: R (R+1) mod n
delete: F (F+1) mod n
if F = R, then full_queue
Polish Notation
Ada 3:
Infix : operand operator operand
Prefix : operator operand operand
Postfix : operand operand operator
Contoh Operasi
Infix
Prefix
Postfix
A+B
A+B
+AB
AB+
A+B-C
((A + B) C)
-+ABC
AB+C-
Konversi
Infix : 2 * 3 ^ 4 + 1 5
Prefix : 2 * (^34) + 1 5
(*2^34) + 1 5
(+*2^341) 5
+*2^3415
Postfix : 2 * (34^) + 1 5
(234^*) + 1 5
(234^*1+) 5
234^*1+5
Kalkulasi PostFix dengan Stack
Contoh : 234^*1+5-
4
3
81
162
163
Push 2,3,4
Push ^
Pop 4,3
Calculate
3^4 = 81
Push 81
Push *
Pop 81,2
Calculate
2*81
Push 162
Push 1
Push +
Pop 1,162
Calculate
162+1
Push 163
Push 5
Push -
158
Pop 5,163
Calculate
163-5
Push 158
Prefix
Kalo Prefix : operator di push dulu,
jika ketemu dua operand berjejer,
baru di pop, hasilnya dipush lagi, dst.
Latihan
Latihan:
A +
A +
A ^
B*C*DE
(B C) * D ^ E
B+C^D*E
buat notasi prefix & postfixnya
hitung hasilnya bila:
A = 5, B = 2, C = 1, D =4, E = 4.
Jawaban
Prefix
1. -+A**BCDE
2. +A*BC^DE
3. +^AB*^CDE
Postfix
1. ABC*D*+E2. ABC-DE^*+
3. AB^CD^E*+
Jawaban
Hasil :
1. 5 + 2 * 1 * 4 4 = 9
2. 5 + (2 1) * 4 ^ 4 = 5 + 1 * 16 =
21
3. 5 ^ 2 + 1 ^ 4 * 4 = 25 + 4 * 4 =
25 + 16 = 41
Tugas Kelompok
Buat Program
STACK
maxstack : 5
message (ada) : full/empty
dll
CIRCULAR QUEUE
Maxqueue : 5
Bentuk bisa memanjang
Kalkulasi Prefix
Misal diberikan:
Infix : 2^3 / 6 1
Prefix : -/^2361
Ketemu
Ketemu operator
operator
di-push
di-push
Ketemu
Ketemu 22 operand
operand berurutan
berurutan
pop
pop 22 operand,
operand, 11 operator,
operator,
lalu
lalu hitung
hitung hasilnya
hasilnya
3
2
8/6
Push -,/,^,2,3
Pop 3,2, ^
Calc: 2^3 = 8
Push 8,6
Pop 6,8,/
Calc: 8/6
Push 8/6, 1
Pop 1, 8/6, Calc: 8/6 1
2/6
Latihan
Latihan:
1. Diberikan polish notation sbb:
a. 4^2 / 8 +5 * 2 4
b. 73*52*-4+3/
c. /^+-*635215
i) Buat ke dalam bentuk 2 polish notation lainnya
ii) konversi ke bentuk stack dengan algoritma
prefix & hitung hasilnya
iii) konversi ke bentuk stack dengan algoritma
postfix & hitung hasilnya
iv) Buat tree untuk masing-masing polish notation
di atas
Latihan (2)
2. Misal maxqueue = 7
Ikuti perintah-perintah
berikut dan ilustrasikan
hasilnya (Linier Queue)
Initqueue
Insert L
Insert A
Insert T
Insert I
Insert H
Insert A
Insert N
Delete
Delete
Delete
Delete
Insert I
Insert H
Delete
Delete
Delete
3. Misal Maxstack = 5
Ikuti perintah-perintah di atas dan ilustrasikan hasilnya
Latihan
4. Diberikan segmen program berikut
Jika alamat awal pada
TYPE
lokasi 3100, Word = 2
tAlamat = RECORD
byte, Longint = 4
Jalan : STRING[30];
Byte, Integer = 2
Kota : STRING[20];
byte, tentukan alamat
Kodepos : Word;
dari:
END;
DataPeg [2,9]
tPegawai = RECORD
secara CMO
NIP : STRING[9];
Field Anak dari
Nama : STRING[20];
DataPeg[1,8]
Alamat : tAlamat;
secara RMO
Anak : Byte;
Tunjangan : Longint;
Field Kota dari
END;
DataPeg[1,7]
VAR
secara CMO
DataPeg : ARRAY [1..3,6..10] of tPegawai;