Karakteristik yang membedakan queue (antrian) dari stack adalah cara
menyimpan dan mengambil data dengan struktur first in first out (FIFO). Hal ini berarti elemen pertama yang ditempatkan pada queue adalah yang pertama dipindahkan.
Contoh yang paling populer untuk membayangkan sebuah queue adalah antrian
pada kasir sebuah bank. Ketika seorang pelanggan datang, akan menuju ke belakang
dari antrian. Setelah pelanggan dilayani, antrian yang berada di depan akan maju. Pada saat menempatkan elemen pada ujung (tail) dari queue disebut dengan enqueue, pada saat memindahkan elemen dari kepala (head) sebuah queue disebut dengan dequeue.
Pada Gambar 5.1 diperlihatkan sebuah queue serta proses enqueue dan dequeue.
Gambar 5.1 (1) Queue dengan 2 elemen; (2) Queue setelah proses enqueue C, D dan E;
(3) Setelah proses dequeue A dan B
4.1 Karakteristik Queue
Karakteristik penting dari antrian adalah :
B C D
D
head
A
A
B
E
C E
��
��
��
tail
head
head
tail
tail
30
1. Elemen antrian yaitu item-item data yang terdapat di elemen antrian
2. Front (elemen terdepan dari antrian)
3. Rear (elemen terakhir dari antrian)
4. Jumlah elemen pada antrian (Count)
5. Status antrian
Kondisi antrian yang menjadi perhatian adalah ;
1. Penuh
Bila elemen pada antrian mencapai kapasitas maksimum antrian. Pada kondisi ini,
tidak mungkin dilakukan penambahan ke antrian. Penambahan elemen
menyebabkan kondisi kesalahan Overflow.
2. Kosong
Bila tidak ada elemen pada antrian. Pada kondisi ini, tidak mngkin dilakukan
pengambilan elemen dari antrian. Pengambilan elemen menyebabkan kondisi
kesalahan Overflow.
4.2 Representasi Antrian
Representasi antrian secara sekuen relatif lebih sulit dibanding stack. Seperti
dijelaskan di atas bahwa antrian juga merupakan satu kumpulan data. Dengan demikian
tipe data yang sesuai untuk menyajikan antrian adalah menggunakan array atau linked
list.
4.2.1 Implementasi Antrian dengan Array
Seperti halnya pada tumpukan, maka dalam antrian kita juga mengenal ada dua
operasi dasar, yaitu menambah elemen baru yang akan kita tempatkan di bagian
belakang antrian dan menghapus elemen yang terletak di bagian depan antrian.
Disamping itu seringkali kita juga perlu melihat apakah antrian mempunyai isi atau dalam keadaan kosong.
Operasi penambahan elemen baru selalu bisa kita lakukan karena tidak ada
pembatasan banyaknya elemen dari suatu antrian. Tetapi untuk menghapus elemen,
maka kita harus melihat apakah antrian dalam keadaan kosong atau tidak. Tentu saja kita tidak mungkin menghapus elemen dari suatu antrian yang sudah kosong.
Untuk menyajikan antrian menggunakan array, maka kita membutuhkan deklarasi
antrian, misalnya sebagai berikut:
#define MAXQUEUE 100;
typedef int ItemType;
31
typedef struct{
int Count;
int Front;
int Rear;
ItemType Item[MAXQUEUE];
}Queue;
Front, menunjukkan item yang paling depan, yaitu elemen yang akan dihapus jika
dilakukan operasi penghapusan. Setelah kita melakukan penghapusan, kita melakukan
increment pada indeks Front, sehingga indeks menunjuk pada posisi berikutnya. Jika
indeks ini jatuh pada angka tertinggi, yaitu angka paling maksimum dari array (N), maka kita melakukan setting ulang ke 0.
Array Item[0:N-1] berisi N item yang merupakan isi dari antrian. Berada pada
posisi 0:N-1dimana pada posisi ini dapat diindikasikan dua pengenal, yaitu Front dan
Rear.
Count menunjukkan jumlah item dalam antrian. Rear menunjukkan posisi dimana
setelahnya dapat dimasukkan item berikutnya.
Representasi antrian lengkap dengan operasi-operasi yang merupakan
karakteristik antrian adalah sebagai berikut:
#include
#include
#define MAXQUEUE 100;
typedef int ItemType;
typedef struct{
int Count;
int Front;
int Rear;
ItemType Item[MAXQUEUE];
}Queue;
void InitializeQueue(Queue *Q)
{
Q->Count = 0;
Q->Front = 0;
Q->Rear = 0;
32
}
int Empty(Queue *Q)
{
return(Q->Count == 0);
}
int Full(Queue *Q)
{
return(Q->Count == MAXQUEUE);
}
void Insert(ItemType ins, Queue *Q)
{
if (Q->Count == MAXQUEUE)
printf("Tidak dapat memasukkan data! Queue Penuh!");
else {
Q->Item[Q->Rear] = ins;
Q->Rear = (Q->Rear + 1) % MAXQUEUE;
++(Q->Count);
}
}
void Remove(Queue *Q, ItemType *rm)
{
if (Q->Count == 0)
printf("Tidak dapat mengambil data! Queue Kosong!");
else {
*rm = Q->Item[Q->Front];
Q->Front = (Q->Front + 1) % MAXQUEUE;
--(Q->Count);
}
}
Jika kita meletakkan beberapa item yang baru dari antrian dalam sebuah array,
maka kita menambahkannya pada Rear dan memindah item dari Front. Dengan
penambahan dan pengurangan item ini, permasalahan akan terjadi jika ukuran dari array
habis. Kita bisa keluar dari permasalahan ini jika kita merepresentasikan antrian secara
circular. Cara mensimulasikan antrian secara circular dalam array linear menggunakan
arithmetic modular. Arithmetic modular menggunakan ekspresi rumus (X % N) untuk
menjaga besarnya nilai X pada range 0:N-1. Jika indeks telah sampai pada N dengan
penambahan atau pengurangan tersebut, maka indeks akan diset pada angka 0.
Hal yang sama juga dilakukan pada Front jika dilakukan pengambilan item dari
antrian. Setelah mengambil item dari antrian, kita melakukan increment terhadap Front
untuk penunjukan pada posisi sesudahnya. Apabila indeks telah berada pada N, maka
indeks diset juga pada angka 0.
Perintah di bawah ini merupakan perintah yang menunjukkan proses Arithmetic
Modular yang diterapkan pada antrian.
Front = (Front + 1) % N;
Rear = (Rear +1) % N;
4.2.2 Implementasi Antrian dengan Linked list
Antrian yang direpresentasikan dengan linked list mempunyai beberapa variasi.
Pada kesempatan kali ini hanya direpresentasikan satu macam saja. Linked list yang
digunakan di sini menggunakan struktur yang berisi pointer yang menunjuk pada simpul
Front dan Rear dari linked list. Masing-masing simpul berisi data dari antrian dan juga link
yang menunjuk pada simpul selanjutnya dari linked list, yang dinamakan Link.
#include
#include
typedef int ItemType;
typedef struct QueueNodeTag {
ItemType Item;
struct QueueNodeTag *Link;
}QueueNode;
typedef struct {
QueueNode *Front;
QueueNode *Rear;
}Queue;
34
void InitializeQueue(Queue *Q)
{
Q->Front = NULL;
Q->Rear = NULL;
}
int Empty(Queue *Q)
{
return(Q->Front == NULL);
}
int Full(Queue *Q)
{
return 0;
}
void Insert(ItemType R, Queue *Q)
{
QueueNode *Temp;
Temp = (QueueNode *) malloc(sizeof(QueueNode));
if (Temp == NULL) {
printf("Queue tidak dapat tercipta");
}else{
Temp->Item = R;
Temp->Link = NULL;
if (Q->Rear == NULL){
Q->Front = Temp;
Q->Rear = Temp;
}else{
Q->Rear->Link=Temp;
Q->Rear = Temp;
}
}
}
35
void Remove(Queue *Q, ItemType *F)
{
QueueNode *Temp;
if (Q->Front == NULL){
printf("Queue masing kosong!");
}else{
*F = Q->Front->Item;
Temp = Q->Front;
Q->Front = Temp -> Link;
free(Temp);
if(Q->Front == NULL) Q->Rear = NULL;
}
}
Program 4.2 Implementasi Antrian dengan Linked list
4.3 Antrian Berprioritas
Dalam antrian yang telah dibahas di atas, semua elemen yang masuk dalam
antrian dianggap mempunyai prioritas yang sama, sehingga elemen yang masuk lebih
dahulu akan diproses lebih dahulu. Dalam praktek, elemen-elemen yang akan masuk
dalam suatu antrian ada yang dikatakan mempunyai prioritas yang lebih tinggi dibanding
yang lain. Antrian yang demikian ini disebut dengan antrian berprioritas (priority queue). Dalam antrian berprioritas, setiap elemenn yang akan msuk dalam antrian sudah
ditentukan lebih dahulu prioritasnya. Dalam hal ini berlaku dua ketentuan, yaitu:
1. Elemen-elemen yang mempunyai prioritas lebih tinggi akan diproses lebih dahulu.
2. Dua elemen yang mempunyai prioritas sama akan dikerjakan sesuai dengan urutan
pada saat kedua elemen ini masuk dalam antrian.
Dengan memperhatikan kedua ketentuan di atas, akan berlaku ketentuan bahwa
elemen yang mempunyai prioritas lebih tinggi akan dikerjakan lebih dahulu dibanding
elemen yang mempunyai prioritas lebih rendah, meskipun elemen yang berprioritas tinggi masuknya sesudah elemen yang berprioritas rendah. Salah satu contoh antrian
berprioritas ini adalah pada sistem berbagi waktu (time-sharing system) dimana program yang mempunyai prioritas tinggi akan dikerjakan lebih dahulu dan program-program yang berprioritas sama akan membentuk antrian biasa.
Ada beberapa cara untuk mengimplementasikan antrian berprioritas. Salah satu
caranya adalah dengan menggunakan linked list. Jika kita menggunakan linked list,
khususnya single linked list atau double linked list, maka ada ketentuan lain yang perlu diperhatikan, yaitu:
1. Setiap node dari linked list terdiri tiga bagian, yaitu bagian informasi, angka
prioritas dan bagian-bagian penyambung ke simpul lain.
2. Simpul X mendahului (terletak di sebelah kiri) simpul Y, jika prioritas X lebih tinggi dibanding prioritas Y atau jika prioritas X dan Y sama, maka simpul X datang lebih dahulu dibanding dengan Y.
Biasanya dibuat suatu perjanjian bahwa angka prioritas yang lebih kecil
menunjukkan derajad prioritas yang lebih tinggi. Sebagai contoh, jika angka prioritas pada simpul X adalah 1 dan pada simpul Y adalah 2, maka dikatakan bahwa simpul X berprioritas lebih tinggi dibanding dengan simpul Y.
4.4 Kesimpulan
1. Antrian (qeue) adalah sebuah bentuk struktur yang berdasarkan pada proses
FIFO (First In First Out)
2. Antrian dapat diimplementasikan dengan menggunakan array atau linked list
Fungsi dalam Stack:
* Fungsi init: fungsi yang digunakan untuk inisialisasi atau membuat stack baru yang masih kosong.
* Fungsi full: digunakan untuk mengetahui stack penuh atau tidak.
* Fungsi empty: digunakan untuk mengetahui stack kosong atau tidak.
* Fungsi clear: digunakan untuk mengosongkan stack. Stack dianggap kosong apabila puncak stack berada pada posisi -1.
* Fungsi push: digunakan untuk menambahkan data ke dalam stack. Penambahan data tidak bisa dilakukan apabila stack sudah penuh. Urutan perintahnya adalah: menambahkan nilai top dan menambahkan data pada posisi nilai top. Jika dalam Linked List menggunakan method addLast
* Fungsi pop: digunakan untuk mengeluarkan data teratas stack dengan syarat bahwa stack tidak kosong. Urutan perintahnya adalah : menghapus data pada posisi nilai top dan menurunkan nilai top. Jika dalam Linked List menggunakan method removeLast
Queue adalah kumpulan data dengan penambahan data hanya melalui satu sisi, yaitu belakang (tail) dan penghapusan data hanya melalui sisi depan (head). Berbeda dengan stack yang bersifat LIFO maka queue bersifat FIFO(First In First Out), yaitu data yang pertama masuk akan keluar terlebih dahulu dan data yang terakhir masuk akan keluar terakhir.
Fungsi dalam Queue:
* Fungsi init : digunakan untuk membuat queue baru atau kosong, yaitu dengan memberi nilai awal (head) dan nilai akhir (tail) dengan -1.
* Fungsi full: digunakan untuk mengetahui apakah queue sudah penuh atau belum. Dilakukan dengan memeriksa nilai akhir (tail) apakah sudah sama dengan maksimal queue.
* Fungsi empty: digunakan untuk mengetahui apakah queue masih kosong atau tidak. Dilakukan dengan memeriksa nilai akhir (tail) bernilai -1 atau tidak.
* Fungsi enqueue : digunakan untuk menambahkan elemen ke dalam queue.
* Fungsi dequeue : digunakan untuk mengambil elemen dari queue, dengan cara memindahkan semua elemen satu langkah ke posisi depannya sehingga elemen yang paling depan tertimpa.
* Fungsi clear : digunakan untuk menghapus semua elemen dalam queue. Ada dua cara yang bisa digunakan, yaitu menuliskan fungsi seperti inisialisasi atau memanggil fungsi remove sampai queue kosong.
Sumber:
http://tutorialpemrograman.wordpress.com/2009/02/15/stack-tumpukan-dan-queue-antrian-dalam-bahasa-java/
http://www.google.co.id/#hl=id&cr=countryID&ei=5QKaS_6PD9C1rAeXkZHSCw&sa=X&oi=spell&resnum=0&ct=result&cd=1&ved=0CAUQBSgA&q=antrian/queue+dalam+struktur+data&spell=1&fp=a05003197864f75b
Queue Dengan Array
• Bersifat FIFO (First In First Out)
• Elemen yang pertama masuk ke antrian akan keluar pertama kalinya
• DEQUEUE adalah mengeluarkan satu elemen dari suatu Antrian
• Antrian dapat dibuat dengan menggunakan: Liniear Array dan Circular Array
Queue Linier Array
Queue (2)
Queue (3)
Queue (4)
• IsEmpty()
• Untuk memeriksa apakah Antrian sudah penuh atau belum
• Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty
• Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah
• Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail
Queue (5)
Queue (6)
Fungis IsFull
• Untuk mengecek apakah Antrian sudah penuh atau belum
• Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh
Queue (7)
Enqueue
• Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang
• Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu
Queue (8)
Queue (9)
• Dequeue()
• Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian
• Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1
• Penggeseran dilakukan dengan menggunakan looping
Queue (10)
Queue (11)
• Clear()
• Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1
• Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca
Queue (12)
Queue (13)
• Tampil()
• Untuk menampilkan nilai-nilai elemen Antrian
• Menggunakan looping dari head s/d tail
Sumber: http://www.google.co.id/#hl=id&cr=countryID&ei=eSCbS_CaMMbGrAeu6bn3Ag&sa=X&oi=spell&resnum=0&ct=result&cd=1&ved=0CAUQBSgA&q=antrian+dalam+struktur+data&spell=1&fp=e460265281e7954
I. STACK DAN QUEUE DENGAN LINKED LIST bagian ke 2
Pengertian Linked list :
• sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian
• struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori.
Bentuk Umum :
Infotype sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list
Next address dari elemen berikutnya (suksesor)
Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu dengan notasi :
Sebelum digunakan harus dideklarasikan terlebih dahulu :
Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :
Beberapa Definisi :
1. List l adalah list kosong, jika First(L) = Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena
Next(Last) = Nil
Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null
Single Linked List
Pada gambar di atas tampak bahwa sebuah data terletak pada sebuah lokasi memori area. Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).
Pembuatan Single Linked List dapat menggunakan 2 metode:
• LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
• FIFO (First In First Out), aplikasinya : Queue (Antrean)
Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.
Circular Double Linked List
Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.
Operasi-Operasi yang ada pada Linked List
• Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
• IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
• Find First
Fungsi ini mencari elemen pertama dari linked list
• Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
• Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
• Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
• Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
• Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
• Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.
A. STACK DENGAN SINGLE LINKED LIST
Selain implementasi stack dengan array seperti telah dijelaskan sebelumnya, stack daat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori.
Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack.
Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.
Operasi-operasi untuk Stack dengan Linked List
• IsEmpty
Fungsi memeriksa apakah stack yang adamasih kosong.
• Push
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.
• Pop
Fungsi ini mengeluarkan elemen teratas dari stack.
• Clear
Fungsi ini akan menghapus stack yang ada.
B. QUEUE DENGAN DOUBLE LINKED LIST
Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list.
Operasi-operasi Queue dengan Double Linked List
• IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.
• IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
• EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
• DeQueue
Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).
II. STACK DAN QUEUE DENGAN ARRAY
1. STACK DENGAN MENGGUNAKAN ARRAY
Pengertian Stack
• Stack atau tumpukan adalah suatu stuktur data yang penting dalam pemrograman
• Bersifat LIFO (Last In First Out)
• Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack
• Contohnya, karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo juga.
Operasi-operasi/fungsi Stack
• Push : digunakan untuk menambah item pada stack pada tumpukan paling atas
• Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas
• Clear : digunakan untuk mengosongkan stack
• IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong
• IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh
Stack with Array of Struct
• Definisikan Stack dengan menggunakan struct
• Definisikan MAX_STACK untuk maksimum isi stack
• Buatlah variabel array data sebagai implementasi stack secara nyata
• Deklarasikan operasi-operasi/function di atas dan buat implemetasinya
Deklarasi MAX_STACK
#define MAX_STACK 10 //hati-hati mulai dari 0 jadi 0-9
Deklarasi STACK dengan struct dan array data
typedef struct STACK{
int top;
char data[10][10]; //misalkan : data adalah array of string
//berjumlah 10 data, masing-masing string
//menampung maksimal 10 karakter
};
Deklarasi/buat variabel dari struct
STACK tumpuk;
Inisialisasi Stack
• Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah KOSONG!
• Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang. Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH!
• Ilustrasi stack pada saat inisialisasi:
Fungsi IsFull
• Untuk memeriksa apakah stack sudah penuh?
• Dengan cara memeriksa top of stack, jika sudah sama dengan
MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full
• Ilustrasi:
Fungsi IsEmpty
• Untuk memeriksa apakah stack masih kosong?
• Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong!
• Program:
Fungsi Push
• Untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack
• Tambah satu (increment) nilai top of stack terlebih dahulu setiap kali ada penambahan elemen stack, asalkan stack masih belum penuh, kemudian isikan nilai baru ke stack berdasarkan indeks top of stack setelah ditambah satu (diincrement)
• Ilustrasinya:
Fungsi Pop
• Untuk mengambil elemen teratas dari stack.
• Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan diambil terlebih dahulu, baru didecrement nilai top of stack sehingga jumlah elemen stack berkurang
• Ilustrasinya:
Programnya:
Fungsi Print
• Untuk menampilkan semua elemen-elemen stack
• Dengan cara looping semua nilai array secara terbalik, karena kita harusmengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil!
Program:
2. QUEUE DENGAN MENGGUNAKAN ARRAY
• Queue = Antrian
• Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya
• DEQUEUE adalah mengeluarkan satu elemen dari suatu Antrian
• Antrian dapat dibuat dengan menggunakan: Liniear Array dan Circular
Array
QUEUE DENGAN LINIEAR ARRAY
• Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar
di ujung satunya
• Sehingga membutuhkan variabel Head dan Tail
DEKLARASI QUEUE
OPERASI-OPERASI PADA QUEUE
- Create()
o Untuk menciptakan dan menginisialisasi Queue
o Dengan cara membuat Head dan Tail = -1
- IsEmpty()
o Untuk memeriksa apakah Antrian sudah penuh atau belum
o Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty
o Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala
antrian (elemen pertama dalam antrian) yang tidak akan berubahubah
o Pergerakan pada Antrian terjadi dengan penambahan elemen
Antrian kebelakang, yaitu menggunakan nilai Tail
- IsFull()
o Untuk mengecek apakah Antrian sudah penuh atau belum
o Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1
adalah batas elemen array pada C) berarti sudah penuh
- Enqueue(data)
o Untuk menambahkan elemen ke dalam Antrian, penambahan
elemen selalu ditambahkan di elemen paling belakang
o Penambahan elemen selalu menggerakan variabel Tail dengan cara
increment counter Tail
- Dequeue()
o Digunakan untuk menghapus elemen terdepan/pertama dari Antrian
o Dengan cara mengurangi counter Tail dan menggeser semua
elemen antrian kedepan.
o Penggeseran dilakukan dengan menggunakan looping
- Clear()
o Untuk menghapus elemen-elemen Antrian dengan cara membuat
Tail dan Head = -1
o Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus
arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai
-1 sehingga elemen-elemen Antrian tidak lagi terbaca
- Tampil()
o Untuk menampilkan nilai-nilai elemen Antrian
o Menggunakan looping dari head s/d tail
PEMBAHASAN
Perbandingan Antara
Stack-Queue Dengan Linked List Vs Stack-Queue Dengan Array
1. Stack Dengan Linked List VS Stack Dengan Array
Berikut ini adalah perbandingan algoritma pada operasi-operasi dasar dari Stack Dengan Linked List dan Stack Dengan Array, dengan menggunakan bahasa pemrograman Pascal
Stack Dengan Linked List Stack Dengan Array
operasi : create()
procedure create;
begin
top := nil ;
end; procedure create;
begin
top := 0;
end;
operasi : empty()
function empty : boolean;
begin
empty := false ;
if top = nil then empty := true ;
end; function empty : boolean;
begin
empty := false ;
if top = 0 then empty := true ;
end;
operasi : full()
tidak ada istilah full pada stack.
program tidak menentukan jumlah elemen stack yang mungkin ada. kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. tempat akan sesuai dengan banyaknya elemen yang mengisi stack. function full : boolean;
begin
full := false ;
if top = max then full := true ;
end;
operasi : push()
procedure push (elemen : typedata) ;
var now:point ;
begin
now(now) ;
now^.isi := elemen ;
if empty then
now^.next := nil ;
else
now^.next := top ;
top := now ;
end; procedure push (elemen : typedata) ;
begin
if not full then
begin
top := top + 1 ;
stack [top] := elemen ;
end;
end;
operasi : pop()
procedure pop (var elemen : typedata) ;
var now:point ;
begin
if not empty then
begin
elemen := now^.isi ;
now := top ;
top := top^.next ;
dispose(now) ;
end;
end; procedure pop (elemen : typedata) ;
begin
if not empty then
begin
elemen := stack [top] ;
top := top – 1 ;
end;
end;
operasi : clear
procedure clear ;
var trash : typedata ;
begin
while not empty do pop(trash) ;
end; procedure clear ;
begin
top := 0 ;
end;
PEMBAHASAN
Dari perbandingan diatas, dapat dilihat pada linked list tidak dikenal istilah full. Hal ini berkaitan dengan penggunaan alokasi memori pada linked list yang lebih dinamis jika dibandingkan dengan array, sehingga pemborosan memory dapat dihindari. Program tidak menentukan jumlah elemen stack yang mungkin ada. Kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. Tempat akan sesuai dengan banyaknya elemen yang mengisi stack.
2. Queue Dengan Linked List VS Queue Dengan Array
Implementasi queue menggunakan array
• Implementasi sederhana
• Ukuran memori harus ditentukan ketika sebuah objek queue dideklarasikan
• Pemborosan tempat (memori) ketika menggunakan jumlah data yang lebih sedikit dari alokasi memori
• Tidak dapat menambahkan data melebihi maksimal ukuran array yang telah dideklarasikan
Implementasi queue menggunakan linked list
• Pengalokasian memori dinamis
• Menggunaka 2 buah pionter, qFront dan qRear, untuk menandai posisi depan dan belakang dari queue
Perbandingan implementasi queue, array VS linked list (contoh 1)
• Memory requirements
o Array-based implementation
Diasumsikan ukuran queue 100 (string @80bytes)
Diasumsikan index membutuhkan 2 bytes
Total memory: (80 bytes x 101 slots) + (2 bytes x 2 indexes) = 8084 bytes
o Linked-list-based implementation
Diasumsikan pointers membutuhkan 4 bytes
Total memory per node: 80 bytes + 4 bytes = 84 bytes
Gambar :
Perbandingan implementasi queue, array VS linked list (contoh 2)
• Memory requirements
o Array-based implementation
Diasumsikan ukuran queue 100 (string @2bytes)
Diasumsikan index membutuhkan 2 bytes
Total memory: (2 bytes x 101 slots) + (2 bytes x 2 indexes) = 206 bytes
o Linked-list-based implementation
Diasumsikan pointers membutuhkan 4 bytes
Total memory per node: 2 bytes + 4 bytes = 6 bytes
Gambar :
KESIMPULAN
Perbandingan Antara Stack-Queue Dengan Linked List Vs Stack-Queue Dengan Array
• Untuk stack dan queue yang berukuran besar, terutama jumlah maksimal data tidak diketahui, lebih baik menggunakan linked list.
• Untuk perangkat yang memiliki memori terbatas, seperti small handheld devices, linked list memiliki performa yang lebih bagus.
Sumber: http://www.google.co.id/#hl=id&cr=countryID&ei=xpWtS-HXII23rAfsuPGmAQ&sa=X&oi=spell&resnum=0&ct=result&cd=1&ved=0CAUQBSgA&q=contoh+penerapan+aplikasi+queue&spell=1&fp=983862b504061180
Tidak ada komentar:
Posting Komentar