tumpukan (stack)
§ Secara sederhana di artikan dengan :
o Sebagai tumpukan dari benda
o Sekumpulan data yang diolah-olah diletakkan di atas data yang lain
o Koleksi dari objek-objek homogen
Dengan melihat definisi tersebut maka jelas bahwa pada stack berlaku aturan LIFO (last in first out) ,yaitu elemen yangterakhir masuk akan pertama kali diambil / dilayani
Ilustrasi stack
Salah satu yang dapat dikemukakan disini adalah tumpukan piring / barang lain. Pada saat kita hendak menumpuk piring-piring tersebut tentulah yang kita lakukan adalah meletakkan piring pertama pada tempatbya, selanjutnya meletakan piring kedua di atas piring pertama dan demikian seterusnya. Pada saat kita hendak mengambil satu piring dari tumpukan tersebut, tentu yang di ambil adalah piring teratas (yang terakhir kali di taruh ) bukan yang bawah ( yang pertama kali diletakkan) .
“ Operasi Pada Stack”
2 operasi dasar yang bisa dilaksanakan pada sebuah stack, yaitu :
o Operasi Push (Menyisipkan Data) memasukkan data kedalam stack .
o Operasi Pop ( Menghapus Data) menghapus elemen-elemen yang terletak pada posisi paling atas dari sebuah stack.
“Dibawah Ini Contoh Pemakaian Operasi Push 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
|
Mengambil data terisi ‘c’
|
Push (‘D’, S)
|
ABD
|
Mengambil data terisi ‘c’
|
Pop ( data, S )
|
AB
|
Data terisi ‘D’
|
Pop ( data, S )
|
A
|
Data terisi ‘B’
|
“Implementasi Stack Dalam Bahasa Pemrograman “
Implementasi dalam bahasa pascal dapat dilakukan dengan memanfaatkan struktur data record dan array . array dipergunakan untuk menyimpan elemen-elemen yang dimasukkan selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang ada di dalam array yang sekaligus menunjukkan TOS .
“Pada Implementasi Dibawah Ini : “
§ Konstanta maxelm menyatakan bahwa elemen maximum yang dapat di tampung oleh stack
§ Typeelemen adalah tipe data yang akan disimpan di dalam stack (bisa integar,word,real,boolean,char,string atau lainnya)
§ Banyak adalah field yang menyatakan banyaknya 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 di antaranya adalah fungsi PENUHS (untuk mengecek apakah stack penuh) fungsi kosongs (untuk mencetak apakah stack kosong) dan fungsi sizes (untuk mengatur banyaknya elemen di dalam stack ) masing-masingg sub program di atas dapat disajikan pseudocodenya sebagai berikut :
Ø Pseudocode
o Procedure inisialisasi ( var S : tumpukan );
Begin
S banyaknya – 0
End ;
o Function Penuhs (S : tumpukan) ; boolean ;
Begin
Jika S banyak = maxelm maka PENUH S-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”
1. 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 akhir : stack dalam keadaan kosong
2. Stack kosong (stack)-empaty
Fungsi untuk menentukan apakah stack dalam keadaan kosong/tidak.
Spesifikasi :
© Tujuan : mengecek apakah stack dalam keadaan kosong
© Input : stack
© Syarat awal : tidak ada
© Output stack : boolean
© Syarat akhir : stack kosong bernilai true jika stack dalam keadaan kosong
3. Stack penuh (stack)-full
Fungsi untuk memeriksa apakah stack yang ada sudah penuh.
Spesifikasi :
© Tujuan : mengecek apakah stack dalam keadaan penuh
© Input : stack
© Syarat awal : tidak ada
© Output : boolean
© Syarat akhir : stack penuh bernilai true jika stack dalam keadaan penuh
4. 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 bawah : stack tidak pernah
© Output : stack
© Syarat akhir : stack bertambah satu elemen
“Queue (antrian)”
§ Implementasi dalam bahasa pascal dapat dilakukan dengan memanfaatkan struktur data record dan array . array dipergunakan untuk menyimpan elemen-elemen yang di masukkan . selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang ada di dalam array.
§ Definisi
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 ]
o FRONT (Q) = Q1
o REAR (Q) = QT
§ Selanjutnya untuk menyatakan jumlah elemen dalam suatu . Queue Q digunakan notasi NOEL (Q) . catatan : suatu pengoperasian berlaku banyak untuk satu elemen
§ Pada queue prinsip yang digunakan adalah “ masuk pertama keluar pertama” atau FIFO ( first in first out)
Data-data di dalam antrian dapat bertipe integer, real, record.
OPERASI-OPERASI PADA QUEUE (Q)
§ Terdapat empat operasi dasar yang didefinisikan pada queue, yaitu :
ü CREATE
ü ISEMPTY
ü INSERT
ü REMOVE
PENJELASAN :
§ 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
§ 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
§ 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 :
v REAR(insert(E,Q)) = E
v 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);
§ 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;
0 komentar:
Posting Komentar