Struktur Data (Pertemuan 3)
STACK (TUMPUKAN)
Secara sederhana diartikan dengan :
· Sebagai tumpukan dari benda
· Sekumpulan data yang seolah-olah diletakkan di atas data yang lain
· Koleksi dari objek-objek
Dengan melihat definisi tersebut maka jelas bahwa pada
stack berlaku aturan LIFO (First In Firs Out) yaitu elemen yang terakhir masuk
akan pertama kali diambil atau dilayani.
ILUSTRASI STACK
Salah satu analogi yang dapat dikemukakan di sini adalah tumpukan piring atau
barang lain. Pada saat kita hendak menumpuk piring-piring tersebut tentulah
yang kita lakukan adalah meletakkan piring pertama pada tempatnya, selanjutnya
meletakkan piring kedua di atas piring pertama dan demikian seterusnya. Pada
saat kita akan mengambil satu piring maka yang diambil piring yang paling atas.
ILUSTRASI STACK-CONT
OPERASI PADA STACK
2 operasi dasar
yang dapat dilaksanakan pada sebuah stack, yaitu :
ü Operasi Push
(menyisipkan data) memasukkan data ke dalam stack.
ü Opersi Pop
(menghapus data) menghapus elemen yang terletak pada
posisi paling atas dari sebuah stack.
Contoh pemakaian operasi pust dan pop dan isi stack
untuk setiap selesai eksekusi satu operasi.
Operasi yang
dilakukan
|
Isi stack
|
Keterangan
|
Kondisi awal
|
Kosong
|
-
|
PUSH (‘A’,S)
|
A
|
-
|
PUSH (‘B’,S)
|
AB
|
-
|
PUSH (‘C’,S)
|
ABC
|
-
|
POP (Data,S)
|
AB
|
Data Berisi ‘C’
|
PUSH (‘D’,S)
|
ABD
|
-
|
POP (Data,S)
|
AB
|
Data Berisi ‘D’
|
POP (Data,S)
|
A
|
Data Berisi ‘B’
|
IMPLEMENTASI STACK DALAM BAHASA PEMOGRAMAN
· Implementasi dalam bahasa Pascal dapat dilakukan denagnmemanfaatkan
struktur data record dan array. Arraydipergunakan untuk menyimpan
elemen-elemen yang dimasukkan. Selain itu diperlukan pula suatu variabel untuk
mencatat banyaknya elemen yang ada di dalam array yang sekaligus menggunakan
IOS.
Pada Implementasi di bawah Ini :
· Konstanta maxelm menyatakan banyaknya elemen maksimum yang
dapat ditampung oleh stack.
· Typeelemen adalah tipe
data yang akan disimpan di dalam stack (bisa integer, word, real, boolean,
char, string, atau lainnya). Banyak field yang menyatakan elemen dalam stack
saat itu, yang sekaligus menyatakan TOS (Top of the stack)
DEKLARASI TIPE UNTUK TUMPUKAN (STACK)
Type tumpukan = record
Banyak
: 0..maxelm;
Elemen
: array[1..maxelm] of typeelemen;
End;
CONT
· Selain prosedur untuk POP dan PUSH, kita
dapat pula menambahkan sejumlah fungsi untuk membantu penanganan kesalahan
diantaranya adalah fungsi PENUHS (untuk mengecek apakah stack
penuh) fungsi KOSONGS (untuk mengecek apakah stack kosong)
fungsi SIZES (untuk mengetahui banyaknya elemen di dalam
stack). Masing-masing sub program di atas dapat disajikan pseudocode-nya
sebagai berikut :
Ø PSEUDOCODE
o Procedure
Inisialisasi(var S : tumpukan);
begin
S. banyak-0
end;
o Function
PENUHS(S : tumpukan): boolean;
begin
Jika S.banyak =
maxelm maka PENUHS - true
else PENUHS - false
end;
Ø PSEUDOCODE CONT
o Function
KOSONGS(S : tumpukan):boolean;
begin
If S.banyak = 0 then KOSONGS - true
else KOSONGS - false
end;
o Procedure
PUSH(data : tipelemen; var S : tumpukan);
begin
If not KOSONGS(S) then
begin
S.banyak
- S.banyak + 1
S.elemen[S.banyak]- data
end
else
Tampilan pesan kesalahan “Stack Penuh”
end;
o Procedure
POP(var S : tumpukan; var data : typeelemen);
begin
if not KOSONGS(S) then
begin
data --S.elemen[S.banyak]
S.banyak --S.banyak -1
end
else
Tampilan pesan
kesalahan “Stack Kosong”
End:
PENJELASAN OPERASI PADA STACK
v Buat stack (stack) – create
Membuat sebuah stack baru yang masih kosong.
#Spesifikasi
§ Tujuan :
mendefinisikan stack yang kosong
§ Input :
stack
§ Syarat
awal : tidak ada
§ Output
stack : - (kosong)
§ Syarat
aktif : stack dalam keadaan kosong
v Stack kosong (stack) – empty
Fungsi untuk menentukan apakah stack dalam keadaan kosong atau tidak.
#Spesifikasi
§ Tujuan :
mengecek apakah stack dalam keadaan kosong
§ Input :
stack
§ Syarat awlal : tidak ada
§ Output :
boolean
§ Syarat akhir : stack kosong
bernilai true jika stack dalam keadaan kosong.
v Stack penuh (stack) – full
Fungsi untuk memeriksa apakah stack yang ada sudah penuh.
#Spesifikasi
§ Tujuan :
mengecek apakah stack dalam keadaan penuh
§ Input :
stack
§ Syarat awlal : tidak ada
§ Output :
boolean
§ Syarat akhir : stack kosong
bernilai true jika stack dalam keadaan penuh.
v Push (stack, info baru)
Menambahkan sebuah elemen ke dalam
stack
#Spesifikasi
§ Tujuan :
menambahkan elemen, info baru pada stack pada posisi paling atas.
§ Input :
stack dan info baru
§ Syarat awlal : stack tidak
penuh
§ Output :
stack
§ Syarat akhir : stack bertambah
satu elemen.
QUEUE (ANTRIAN)
DEFINISI
o Queue adlah
suatu linear lish dimana operasi DELETE terjadi pada sisi
depan (FRONT) dan operasi INSERT terjadi pada
sisi belakang(REAR).
Jika diberikan suatu Queue Q dengan elemen-elemennya
yang terdiri atas Q1, Q2, ...., QT maka
queue Q dituliskan :
Q
= [ Q1, Q2, ...., QT ]
· FRONT (Q) = Q1
· REAR (Q) = QT
o Selanjutnya
untuk menyatakan jumlah elemen dalam suatu queue Q digunakan notasi NOEL (Q).
o Catatan : Satu pengoperasian berlaku hanya untuk satu elemen.
CONT.
o Pada queue
prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (Firs In
Firs Out).
o Data-data di
dalam antrian dapat bertipe integer, real, record
ILUSTRASI QUEUE
OPERASI-OPERASI PADA QUEUE (Q)
o Terdapat empat
operasi dasar yang didefinisikan pada queue, yaitu :
1. CREATE
Bentuk
umum :
CREATE (Queue)
Suatu operasi CREATE (Q) akan menghasilkan suatu queue kosong dengan nama
Q, dan didefinisikan bahwa :
NOEL
(CREATE
(Q)) =
0
FRONT
(CREATE (Q)) =
tidak terdefinisi
REAR (CREATE
(Q)) =
tidak terdefinisi
2. ISEMPTY
Bentuk umumnya adalah : INEMPTY (queue)
Jika Q adalah Queue, maka ISEMPTY(Q) adalah suatu operasi yang digunakan
untuk memeriksa apakah Queue Q adalah queue kosong. Jika hasil dari operasi ini
akan berjenis data boolean (true/false),dengan bentuk sebagai berikut :
ISEMPTY(Q) =
True, jika Q adalah queue kosong
=
False, jika Q bukan queue kosong
3. INSERT
Bentuk Umumnya : INSERT (Elemen, Queue)
INSERT(E,Q), dimana E = elemen dan Q = queue, adalah suatu operasi yang
digunakan untuk memasukkan elemen E ke dalam queue Q.
Didefinisikan, bahwa elemen E akan menjadi elemen yang berada pada posisi
REAR dan queue Q. Akibat dari operasi ini adalah :
- REAR(insert(E,Q))
= E
- NOEL(Q)
bertambah satu dan QNOEL adalah E
Jika Q adalah queue kosong,
maka :
ISEMPTY(INSERT(E,Q))
= False
Dalam bentuk statemen Pascal, biasanya dituliskan :
IF
ISEMPTY(Q) Then front (insert(E,Q)) = E
Else
front(insert(E,Q = front(Q);
4. REMOVE
Bentuk umum : REMOVE(elemen, queue)
REMOVE(Q) berarti mengeluarkan elemen Q yang berada pada posisi FRONT.
Akibat dari operasi ini, elemen Q akan berkurang satu dan elemen kedua (elemen
yang berada disebelahnya) akan menjadi elemen yang berada pada posisi FRONT
dari queue Q ini.
Selanjutnya, jika Q adalah queue kosong, maka REMOVE(Q) akanmenghasilkan
suatu Error.
IF
NOEL(Q) = 0 Then Remove(Q) = erroe_condition
Remove(create(Q))
= error_condition
DEKLARASI QUEUE DALAM PASCAL
· Dalam bahasa pemrograman biasanya tidak ada fasilitas queue (built in
queue). Untuk itu setiap programmer harus mendefinisikan sendiri dengan
bantuan fasilitas yang ada. Pada umumnya fasilitas yang digunakan untuk
mendeklarasikan queue adalah Array, Bentuk deklarasinya dalam bahasa sebagai
berikut :
TYPE
StrukQueue = Record
Q
: Array[1...100] of integer;
Front,
Rear : Integer;
End;
VAR Q : StrukQueue;
