Queue atau antrian adalah suatu kumpulan data yang penambahan elemennyahanya bisa dilakukan pada suatu ujung (disebut dengan sisi belakang atau rear), dan penghapusan atau pengambilan elemen dilakukan lewat ujung yang lain (disebut dengan sisi depan atau front).
Kalau tumpukan dikenal dengan menggunakan prinsip LIFO (Last In First Out), maka pada antrian prinsip yang digunakan adalah FIFO (First In First Out).
Antrian banyak dijumpai dalam kehidupan sehari-hari, misal kalau kita menonton bioskop maka kita harus antri untuk membeli tiketnya.
BAB I. IMPLEMENTASI ANTRIAN DENGAN ARRAY
Karena antrian merupakan sustu kumpulan data, maka tipe data yang sesuai untuk menyajikan antrian adalah menggunakan array atau list (senarai berantai).
Perhatikan gambar berikut ini:
 |
Gambar 1.1 Contoh antrian dengan 6 elemen
Gambar 1.1 diatas menunjukkan contoh penyajian antrian menggunakan array. Antrian diatas berisi 6 elemen, yaitu A,B,C,D,E dan F. Elemen A terletak di bagian depan antrian dan elemen F terletak di bagian belakang antrian. Dengan demikian, jika ada elemen baru yang akan masuk, maka elemen tersebut akan diletakkan di sebelah kanan F. Dan jika ada elemen yang akan dihapus, maka A akan dihapus terlebih dahulu.
Elemen A terletak di bagian depan, kemudian disusul elemen B dan elemen yang paling akhir atau paling belakang adalah elemen F. Misalkan ada elemen baru yang akan masuk maka akan terletak di belakang elemen F, sehingga elemen baru akan menempati posisi yang paling belakang.
Gambar 1.2 menunjukkan antrian di atas dengan penambahan elemen G dan H, sehingga gambar 1.1 menjadi seperti berikut:
Gambar 1.2 Contoh penambahan antrian dengan 2 elemen
Gambar 1.3 menunjukkan antrian di atas dengan penghapusan elemen A dan B, sehingga gambar 1.1 menjadi seperti berikut:
Gambar 1.3 Contoh penghapusan antrian dengan 2 elemen
Seperti halnya pada tumpukan atau stack, maka di dalam antrian juga dikenal dua operasi dasar yaitu menambah elemen baru yang akan diletakkan di bagian belakang antrian dan menghapus elemen yang terletak di bagian depan antrian. Selain itu kita juga harus melihat antrian itu mempunyai isi atau masih kosong.
Untuk memahami penggunaan antrian dalam array, kita membutuhkan deklarasi antrian, misalnya sebagai berikut:
#define MAXN 6
typedef enum {NOT_OK, OK} Tbooloean;
typedef struct {
Titem array [MAXN];
int first;
int last;
int number_of_items;
} Tqueue;
Dengan deklarasi di atas, elemen antrian dinyatakan dalam tipe integer yang semuanya terdapat dalam struktur. Variabel first menunjukkan posisi elemen pertama dalam array, dan variabel last menunjukkan posisi elemen terakhir dalam array.
Algoritma dari penggalan program di atas adalah:
1. Tentukan elemen yang akan dimasukkan ke dalam antrian (dalam hal ini adalah 6 elemen).
2. Deklarasikan struktur untuk menampung elemen pada antrian.
3. Selesai.
Untuk menambah elemen baru dan mengambil elemen dari antrian dalam antrian, diperlukan deklarasi sebagai berikut ini:
Void initialize_queue (Tqueue *Pqueue)
{ Pqueue->first = 0;
Pqueue->last = -1;
Pqueue->number_of _items = 0;
}
Tboolean enqueue(Tqueue *Pqueue, Titem item)
{ if (Pqueue->number_of_items >= MAXN)
Return(NOT_OK);
Else {
Pqueue->last++;
if (Pqueue->last > MAXN – 1)
Pqueue->last = 0;
Pqueue->array[Pqueue->last] = item;
Pqueue->number_of_items++;
return (OK);
}
}
Tboolean dequeue(Tqueue *Pqueue, Titem *Pitem)
{ if (Pqueue->number_of_items == 0)
return (NOT_OK);
else {
*Pitem = Pqueue->array[Pqueue->first++];
if (Pqueue->first > MAXN – 1)
Pqueue->first = 0;
Pqueue->number_of_items--;
return (OK);
} }
Adapun penggalan program di atas, apabila dikelompokkan berdasarkan fungsinya adalah sebagai berikut:
1. Deklarasi antrian
void initialize_queue (Tqueue *Pqueue)
{ Pqueue->first = 0;
Pqueue->last = -1;
Pqueue->number_of_items = 0;
2. Fungsi untuk memasukkan elemen pada antrian adalah sebagai berikut:
Tboolean enqueue (Tqueue *Pqueue, Titem item)
{ if (Pqueue->number_of_items >= MAXN)
return(NOT_OK);
else {
Pqueue->last++;
If (Pqueue->last > MAXN -1)
Pqueue->last = 0;
Pqueue->array[Pqueue->last] = item;
Pqueue->number_of_items++;
return (OK);
}
}
3. Fungsi untuk mengapus elemen dari antrian adalah sebagai berikut:
if (Pqueue->number_of_items == 0)
return (NOT_OK);
else {
*Pitem = Pqueue->array[Pqueue->first++];
if (Pqueue->first > MAXN – 1)
Pqueue->first = 0;
Pqueue->number_of_items--;
return (OK);
}
}
Untuk memperjelas masing-masing fungsi pada deklarasi di atas, perhatikan ilustrasi pada gambar 1.4.
Gambar 1.4. Contoh deklarasi antrian dengan 6 ukuran.
Dari gambar 1.4. bisa dilihat last dibuat = 0 dan first dibuat = 1 serta antrian dikatakan kosong jika last < first. Banyaknya elemen yang ada dalam antrian dinyatakan sebagai last-first+1.
Perhatikan gambar 1.5.
Gambar 1.5. Contoh deklarasi antrian penambahan 4 buah elemen.
Dari gambar tersebut menunjukkan array dengan 6 elemen untuk menyajikan sebuah antrian (dalam hal ini MAXN = 6). Pada saat permulaan antrian dalam keadaan kosong (Gambar 1.4.). Pada gambar 1.5. terdapat 4 buah elemen yang ditambahkan. Dalam hal ini first = 1 dan last = 4.
Perhatikan gambar 1.6. berikut ini.
Gambar 1.6. Contoh deklarasi antrian penghapusan 2 buah elemen.
Gambar di atas menunjukkan antrian setelah 2 elemen yaitu elemen A dan B dihapus. Perhatikan gambar 1.7. berikut ini.
Gambar 1.7. Contoh deklarasi antrian penambahan 2 buah elemen.
Gambar di atas menunjukkan antrian baru setelah E dan F ditambahkan. Banyaknya elemen dalam antrian adalah 6-3+1=4 elemen. Karena array terdiri daru 6 elemen, maka sebenarnya kita masih bisa menambah elemen lagi. Tetapi, jika ingin ditambah elemen baru, maka nilai last harus ditambah 1 menjadi 7. Padahal array antrian hanya terdiri dari 6 elemen, sehingga tidak mungkin ditambah lagi, meskipun sebenarnya array tersebut masih kosong di dua tempat.
BAB II. IMPLEMENTASI ANTRIAN DENGAN POINTER
Di atas telah disajikan bagaimana antrian dengan menggunakan array dengan berbagai keterbatasannya, antara lain adalah jumlah elemen yang bisa diisi dalam antrian terbatas pada ukuran array yang digunakan.
Pada bagian ini akan dibahas cara lain untuk mengimplementasikan antrian yaitu dengan menggunakan pointer. Pada ilustrasi penambahan (yang selalu dilakukan di sebelah belakang antrian) dan penghapusan (yang selalu dilakukan pada elemen pada posisi paling depan), maka antrian sebenarnya juga merupakan bentuk khusus dari suatu senarai berantai (linked list).
Untuk memanipulasi sebuah antrian bisa digunakan dua buah variabel yang menyimpan posisi elemen paling depan dan elemen paling belakang. Dengan cara yang sama, apabila antrian diimplementasikan menggunakan senarai berantai maka cukup dua pointer yang bisa dipakai yaitu elemen paling depan (kepala) dan elemen paling belakang (ekor).
Untuk mengimplementasikan antrian dengan menggunakan pointer, perhatikan algoritma berikut ini:
1. Tentukan struktur untuk menampung node yang akan dimasukkan pada antrian. Deklarasi struktur pada penggalan program berikut ini:
struct queueNode {
char data;
struct queueNode *nextPtr;
};
typedef struct queueNode QUEUENODE;
typedef QUEUENODE *QUEUENODEPTR;
QUEUENODEPTR headPtr = NULL, tailPtr = NULL;
2. Deklarasikan penambahan elemen baru pada antrian, dimana letaknya adalah paling belakang. Deklarasi penambahan elemen baru tersebut dapat dilihat pada penggalan program berikut ini:
void enqueue ( QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr, char value )
{
QUEUENODEPTR newPtr = malloc( sizeof ( QUEUENODE ) );
if ( newPtr != NULL ) {
newPtr -> data = value;
newPtr -> nextPtr = NULL;
if ( isEmpty ( *headPtr ) )
*headPtr = newPtr;
else
( *tailPtr ) -> nextPtr = newPtr;
*tailPtr = newPtr;
}
3. Lakukan pengecekan terhadap antrian, apakah antrian dalam kondisi kosong atau tidak. Kalau kosong, maka elemen bisa dihapus. Penggalan program berikut ini akan menunjukkan kondisi tersebut.
int isEmpty ( QUEUENODEPTR headPtr ) {
return headPtr == NULL;
}
Tidak ada komentar:
Posting Komentar