Algoritma dan Struktur Data

Queue
Umi Sa’adah
Tita Karlita
Entin Martiana K
Arna Fariza
2021
 Materi
 Definisi Queue
 Operasi pada Queue
 Representasi Queue

2
 Apakah Queue ?

 Abstract Data Type yang

menerapkan konsep antrian.
 Merupakan konsep First In First
Out (FIFO).
 Data yang disimpan pertama
akan diambil lebih dahulu. Image source [Link]

3
Karakteristik Queue

 Elemen antrian yaitu A B C D

data yang terdapat di
elemen antrian. elemen
 Elemen queue: A, B, C,
dan D.
 Karakteristik Queue
• Front : penunjuk count = 4

elemen terdepan dari

antrian. A B C D
• Rear : penunjuk
elemen terakhir dari front rear

antrian.
• Count : jumlah
elemen pada antrian.
 Karakteristik Queue

Kondisi Penuh
Kondisi : penuh atau kosong
A B C D E F G

count = MAX
Kondisi Kosong

count = 0
 Representasi Queue
 Menggunakan:
 array
 linked list
 Pada implementasi queue dengan array, kemungkinan
queue bisa penuh
 Pada implementasi queue dengan linked list, queue tidak
pernah penuh

7
 Operasi Queue
 enqueue: memasukkan data ke antrian
 dequeue: mengeluarkan data dari antrian

Kondisi Kosong Enqueue

Dequeue

front=rear
Operasi Queue

Enqueue(A)

A
Operasi Queue

Enqueue(B)
A B
Operasi Queue

Enqueue(C)
A B C
Operasi Dequeue

Dequeue()

A B C
Operasi Dequeue

Dequeue()

B C
Operasi Dequeue

Dequeue()

C
 Representasi Queue dengan Array

15
 Representasi Queue dengan Array

#define MAX 7
typedef char itemType
typedef struct {
itemType item[MAX];
int count;
int front;
int rear;
} Queue;

16
 Operasi pada Queue
 enqueue : menyimpan item ke Queue
 dequeue : menghapus item dari Queue
 inisialisasi : inisialisasi awal Queue
 penuh : mengecek apakah queue dalam kondisi penuh
 kosong : mengecek apakah queue dalam kondisi kosong

17
 Operasi Inisialisasi
Menginisialisasi void inisialisasi (Queue *q){
 count sama dengan 0. q->count=0;
 front menunjuk ke q->front = 0;
indeks 0. q->rear = 0;
}
 rear menunjuk ke indeks
0. count = 0

front=rear=0

18
 Operasi Penuh
 Melakukan pengecekan apakah Queue
 penuh (count bernilai = MAX), atau
 tidak penuh (count bernilai < MAX),
 Jika penuh return value=1, sebaliknya return value=0
 Digunakan saat melakukan operasi ENQUEUE
Kondisi Penuh
int penuh (Queue *q){
if (q->count==MAX)
A B C D E F G return 1;
else
count = MAX return 0;
}
19
 Operasi Kosong
 Melakukan pengecekan apakah queue
 Kosong (count bernilai = 0),
 Tidak kosong (Jika kosong return value=1, sebaliknya return value=0)
 Digunakan bila melakukan operasi DEQUEUE
int kosong (Queue *q){
Kondisi Kosong
if(q->count==0);
return 1;
else
return 0;
count = 0 }
20
 Operasi ENQUEUE
 Jika array penuh (count=MAX), tidak dapat
melakukan operasi Enqueue. front=rear=0 count = 0
 Menyimpan data pada posisi rear.
 Setelah dilakukan penyimpanan, posisi rear di- x=A A
increment. (rear++).
 Circular queue  (rear++) % MAX.
 Jumlah elemen diincrement (count++). front=0 rear=1 count = 1

void Enqueue (Queue *q, itemType x){

if(penuh(q))
printf(“Queue Penuh, data tidak dapat disimpan\n”);
else {
q->item[q->rear]=x;
q->rear =(q->rear+1) % MAX
q->count++;
}
}
21
 A B C
Operasi DEQUEUE
 Jika array Kosong (count=0), tidak dapat dilakukan
operasi Dequeue. front=0 rear=2 count = 3
 Mengambil data pada posisi front. B C
 Setelah mengambil data posisi front di-increment
(front++)
 Circular queue  (front++) % MAX. temp=A front=1 rear=2 count =2
 Jumlah elemen di-decrement (count--).
itemType Dequeue(Queue *q){
itemType temp;
if(Kosong(q)) {
printf(“Queue Kosong, tidak dapat mengambil data\n”);
return ‘ ‘;
}else {
temp=q->item[q->front];
q->front = (q->front+1) % MAX;
q->count--;
return(temp);
}
}

22
 Circular Queue
Enqueue(A)
Enqueue(B)
Enqueue(C) A B C D E
Enqueue(D)
Enqueue(E) front rear

Dequeue()
Dequeue() C D E

front rear
Linier Queue Circular Queue

Enqueue(F) C D E F C D E

front rear Posisi item baru front rear

23
Image source: [Link]
ENQUEUE
q->item[q->rear]=x;
q->rear = (q->rear+1) % MAX;
q->count++;

front
rear
item[0]=7 item[1]=8
front=0, rear=0+1%3=1 front=0, rear=1+1%3=2
count=1 count=2
front=rear=0
count=0

item[2]=6 temp=item[0]7
front=0, rear=2+1%3=0 front=0+1%3=1, rear=0 DEQUEUE
count=3 count=2 temp=q->item[q->front];
q->front = (q->front+1)%MAX;
q->count--;
return(temp);
temp=item[1]8 item[0]=4
front=1+1%3=2, rear=0 front=2, rear=0+1%3=1
count=1 count=2

item[1]=10 temp=item[2]6 item[2]=13

front=2, rear=1+1%3=2 front=2+1%3=0, rear=2 front=0, rear=2+1%3=0
count=3 count=2 count=3

24
Rangkuman
 Queue merupakan konsep penyimpanan elemen secara FIFO.
 Elemen yang masuk lebih awal akan keluar lebih dahulu
 Komponen pada Queue terdiri dari :
 Elemen yang disimpan di penyimpan
 penunjuk depan (front)
 penunjuk belakang (rear)
 jumlah item (count)
 Operasi pada Queue : ENQUEUE dan DEQUEUE
 Operasi tambahan pada Queue : Inisialisasi, Penuh, Kosong
 Representasi queue:
 Array
 Linked list
 Referensi
1. Brian W. Kerninghan, Dennis M. Ritchie (2012): The C Programming
Language : Ansi C Version 2 Edition, PHI Learning
2. Byron Gottfried (2010) : Programming with C, Tata McGraw - Hill
Education
3. Kochan Stephen (20040 : Programming in C, 3rd Edition, Sams
4. K. N. King (2008) : C Programming: A Modern Approach, 2nd Edition, W.
W. Norton & Company
5. Abdul Kadir (2012) : Algoritma & Pemrograman Menggunakan C & C++,
Andi Publisher, Yogyakarta
6. [Link]
7. [Link]
8. [Link]

26