Hari ini ngambil jadwal kuliah malam (18.30 - 21.00). Mata Kuliahnya Struktur Data, pertemuan ke 4. Materi yang dibahas tentang Struktur Data STACK (tumpukan) dan ANTRIAN (queue).
Berikut resumenya:
STACK (Tumpukan)
A. Pengertian Stack (Tumpukan)
Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan
dalam satu lajur linear. Kumpulan elemen-elemen data hanya boleh diakses
pada satu lokasi saja yaitu posisi ATAS (TOP) tumpukan. Tumpukan
digunakan dalam algoritma pengimbas (parsing), algoritma penilaian
(evaluation) dan algoritma penjajahan balik (backtrack). Elemen-elemen
di dalam tumpukan dapat bertipe integer, real, record dalam bentuk
sederhana atau terstruktur.
Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO
(Last In First Out), benda yang terakhir masuk dalam stack akan menjadi
benda pertama yang dikeluarkan dari stack.
Tumpukan disebut juga “Push Down Stack” yaitu penambahan elemen baru
(PUSH)ndan penghapusan elemen dari tumpukann(POP). Contoh pada PDA (Push
Down Automaton). Sistem pada pengaksesan pada tumpukan menggunakn
system LIFO (Last In First Out), artinya elemen yang terakhir masuk itu
yang akan pertama dikeluarkan dari tumpukan (Stack). Ilustrasi tumpukan
(Stack) dapat digambarkan seperti tumpukan CD atau tumpukan sate. Stack
merupakan suatu susunan koleksi data dimana dapat ditambahkan dan
dihapus selalu dilakukan pada bagian akhir data, yang disebut dengan Top
Of Stack.
Sebelum struktur data tumpukan ini bisa digunakan, harus
dideklarasikan dahulu dalam kamus data. Ada beberapa cara pendeklarasian
struktur data ini, salah satunya dengan menggunakan tata susunan linear
(larik) dan sebuah variable, yang dikemas dalam tipe data record. Stack
(tumpukan) adalah struktur data bertipe record yang terdiri dari field
elemen, bertipe larik/array dengan indek dari 1 sampai dengan MaksTum
(Maksimum Tumpukan), atas, bertipe interger berkisar dari 0 (saat
kosong) sampai dengan MaksTum (Maksimum Tumpukan).
B. Operasi – operasi pada Stack (Tumpukan)
Operasi yang sering diterapkan pada struktur data Stack (Tumpukan)
adalah Push dan Pop. Operasi – operasi yang dapat diterapkan adalah
sebagai berikut :
1. Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.
2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan Stack.
4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.
5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.
Pada proses Push, Tumpukan (Stack) harus diperiksa apakah jumlah
elemen sudah mencapai masimum atau tidak. Jika sudah mencapai maksimum
maka OVERFLOW, artinya Tumpukan penuh tidak ada elemen yang dapat
dimasukkan ke dalam Tumpukan. Sedangkan pada proses Pop, Tumpukan harus
diperiksa apakah ada elemen yang hendak dikeluarkan atau tidak. Jika
tidak ada maka UNDERFLOW, artinya tumpukan kosong tidak ada elemen yang
dapat diambil.
C. Macam – macam Stack:
1. Stack dengan Array
Sesuai dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus dimulai dari elemen teratas.
2. Double Stack dengan Array
Metode ini adalah teknik khusus yang dikembangkan untuk menghemat
pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah
penggunaan hanya sebuah array untuk menampung dua stack.
Ilustrasi Stack pada saat Inisialisasi
Ilustrasi Stack pada saat full
CONTOH PROGRAM:
class StackApp
{
public static void main(String[] args)
{
StackX theStack = new StackX(10); // make new stack
theStack.push(20); // push items onto stack
theStack.push(40);
theStack.push(60);
theStack.push(80);
theStack.pop();
while( !theStack.isEmpty() ) // until it’s empty,
{ // delete item from stack
long value = theStack.pop();
System.out.print(value); // display it
System.out.print(” “);
} // end while
System.out.println(” “);
} // end main()
} // end class StackApp
////////////////////////////////////////////////////////////////
QUEUE (ANTRIAN)
A. Definisi Queue (Antrian)
Queue merupakan suatu struktur data linear. Konsepnya hampir sama
dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan
pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan (front)
dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di
dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana
atau terstruktur.
Tumpukan disebut juga “Waiting Line” yaitu penambahan elemen baru
dilakukan pada bagian belakang dan penghapusan elemen dilakukan pada
bagian depan. Sistem pada pengaksesan pada Queue menggunakan sistem FIFO
(First In First Out), artinya elemen yang pertama masuk itu yang akan
pertama dikeluarkan dari Queue.
Queue jika diartikan secara harfiah, queue berarti antrian. Queue
merupakan salah satu contoh aplikasi dari pembuatan double linked list
yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat
anda mengantri diloket untuk membeli tiket.
Istilah yang cukup sering dipakai apabila seseorang masuk dalam
sebuah antrian adalah enqueue. Sedang istilah yang sering dipakai bila
seseorang keluar dari antrian adalah dequeue.
B. Operasi-operasi pada Queue
1. Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.
2. Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.
3. EnQueue : berfungsi memasukkan data kedalam antrian.
4. DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.
5. Clear : Menghapus seluruh Antrian
6. IsEmpty : memeriksa apakah antrian kosong
7. IsFull : memeriksa apakah antrian penuh.
Operasi-operasi tersebut dapat dideklarasikan dalam kelas abstrak Queue sebagai berikut :
type int typeQueue
class abstrakQueue
{
public:
Queue() { };
virtual Queue() { };
virtual typeQueue EnQueue(typeQueue Elemen)= 0;
virtual typeQueue DeQueue() = 0;
virtual void Clear() = 0;
virtual bool IsEmpty() = 0;
virtual bool IsFull() = 0;
};
C. Implementasi Queue dengan Linear Array
1. Linear Array
Linear array adalah suatu array yang dibuat seakan-akan merupakan
suatu garis lurus dengan satu pintu masuk dan satu pintu keluar. Berikut
ini diberikan deklarasi kelas QueueLinear sebagai implementasi dari
Queue menggunakan linear array. Dalam prakteknya, kita dapat
menggantinya sesuai dengan kebutuhan kita. Data dikses dengan field
data, sedangkan indeks item pertama dan terakhir disimpan dalam field
Head dan Tail. Konstruktor akan menginisialisasi nilai Head dan Tail
dengan -1 untuk menunjukkan bahwa antrian masih kosong dan
mengalokasikan data sebanyak MAX_QUEUE yang ditunjuk oleh data.
Destruktor akan mengosongkan antrian kembali dan mendealokasikan memori
yang digunakan oleh antrian.
class QueueLinear: public Queue
{
private:
typeQueue* Data;
int Head;
int Tail;
public:
QueueLinear() // kontruktor
{
Head = -1;
Tail = -1;
Data = new typeQueue [MAX_QUEUE];
};
2. Implementasi Queue dengan Circular Array
Circular array adalah suatu array yang dibuat seakan-akan merupakan
sebuah lingkaran dengan titik awal(head) dan titik akhir (tail) saling
bersebelahan jika array tersebut masih kosong.
CONTOH PROGRAM
class QueueApp
{
public static void main(String[] args)
{
Queue theQueue = new Queue(5); // queue holds 5 items
theQueue.insert(10); // insert 4 items
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove(); // remove 3 items
theQueue.remove(); // (10, 20, 30)
theQueue.remove();
theQueue.insert(50); // insert 4 more items
theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);
while( !theQueue.isEmpty() ) // remove and display
{ // all items
long n = theQueue.remove(); // (40, 50, 60, 70, 80)
System.out.print(n);
System.out.print(” “);
}
System.out.println(“”);
} // end main()
} // end class QueueApp
D. Priority Queue
Priority queue adalah elemen queue yang terurut menurut suatu
prioritas tertentu. Priority queue ini sering dianggap modified queue.
Penambahan elemen berarti menambahkan elemen sesuai urutan prioritas,
dan menghapus elemen adalah menghapus elemen dengan prioritas tertinggi
atau terendah(pada bagian Head). Lebih jelasnya dapat dilihat pada
gambar berikut:
Contoh Program
(Masih dalam perbaikan)
Daftar Pustaka
http://oopweb.com/Java/Documents/ThinkCSJav/Volume/chap16.htm, diakses tanggal 9 Desember 2008, jam 12.53 WIB.
http://webmail.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik38.pdf, diakses tanggal 9 Desember 2008, jam 13.05 WIB.
Prijono, Agus dan Teddy Marcus Zakaria. 2006. Konsep dan Implementasi Struktur Data. Bandung : Informatika.
Tidak ada komentar:
Posting Komentar