PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA

BAB. 6 QUEUE
6.1. Definisi Queue
Queue disebut juga antrian dimana data masuk di satu sisi dan keluar di sisi yang lain. Queue bersifat FIFO
(First In First Out). Antrian (Queue) merupakan suatu kumpulan data yang penambahan elemennya (masuk
antrian) hanya bisa dilakukan pada suatu ujung (disebut dengan sisi belakang/rear) atau disebut juga
enqueue yaitu apabila seseorang masuk ke dalam sebuah antrian dan keluar dari antrian adalah dequeue.

Gambar antrian penuh dengan 6 elemen

Gambar antrian dengan 2 data sudah keluar (dequeue).

Struktur data queue setidaknya harus memiliki operasi-operasi sebagai berikut :

EnQueue : Memasukkan data ke dalam antrian
DeQueue : Mengeluarkan data terdepan dari antrian
Clear : Menghapus seluruh antrian
IsEmpty : Memeriksa apakah antrian kosong
IsFull : Memeriksa apakah antrian penuh

6.2. Implementasi Queue dengan Linear Array

Contoh Program 22
1. #include <iostream> 21. void printQueue() {
2. #define MAX 20 //maksimum data queue 22. if (isEmpty()) {
3. using namespace std; 23. cout << "Antrian kosong"<<endl;
4. 24. }
5. //Deklarasi struct antrian 25. else {
6. struct Queue { 26. cout << "QUEUE : ";
7. int front, rear, data[MAX]; 27. for (int i = [Link]; i < [Link]; i++)
8. }Q; 28. cout << [Link][i] << (([Link]-
9. 1 == i) ? "" : ",");
10. //cek apakah antrian penuh 29. cout << endl;
11. bool isFull() { 30. }
12. return [Link] == MAX; 31. }
13. } 32.
14. 33. //manambahkan data ke antrian
15. //cek apakah antrian kosong 34. void enqueue() {
16. bool isEmpty() { 35. if (isFull())
17. return [Link] == 0; 36. {
18. } 37. cout << "Antrian penuh!"<<endl;
19. 38. }
20. //Menampilkan Queue 39. else {

PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA TEKINIK INFORMATIKA 24

 PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA

40. int data; 67.

41. //menambahkan data ke antrian 68. int main() {
42. cout << "Masukkan Data : ";cin >> data; 69. int choose;
43. [Link][[Link]] = data; 70. do
44. //menempatkan tail pada elemen data terakhir 71. {
yang ditambahkan 72. //Tampilan menu
45. [Link]++; 73. cout << "-------------------\n"
46. cout << "Data ditambahkan\n"; 74. << " Menu Pilihan\n"
47. printQueue(); 75. << "-------------------\n"
48. } 76. << " [1] Enqueue \n"
49. } 77. << " [2] Dequeue\n"
50. 78. << " [3] Keluar \n\n"
51. // mengambil data dari antrian 79. << "-------------------\n"
52. void dequeue() { 80. << "Masukkan pilihan : "; cin >> choose;
53. if (isEmpty()) 81. switch (choose)
54. { 82. {
55. cout << "Antrian masih kosong"<<endl; 83. case 1:
56. } 84. enqueue();
57. else{ 85. break;
58. cout << "Mengambil data \"" << [Link][[Link] 86. case 2:
t] << "\"..." << endl; 87. dequeue();
59. //menggeser antrian data ke head 88. break;
60. for (int i = [Link]; i < [Link]; i++) 89. default:
61. [Link][i] = [Link][i + 1]; 90. cout << "Pilihan tidak tersedia";
62. //menempatkan tail pada data terakhir yang d 91. break;
igeser 92. }
63. [Link]--; 93. } while (choose !=3);
64. printQueue(); 94. return 0;
65. } 95. }
66. }

Hasil output programnya adalah :

------------------- [2] Dequeue
Menu Pilihan [3] Keluar
-------------------
[1] Enqueue -------------------
[2] Dequeue Masukkan pilihan : 1
[3] Keluar
Masukkan Data : 45
------------------- Data ditambahkan
Masukkan pilihan : 1 QUEUE : 23,33,45
-------------------
Masukkan Data : 23 Menu Pilihan
Data ditambahkan -------------------
QUEUE : 23 [1] Enqueue
------------------- [2] Dequeue
Menu Pilihan [3] Keluar
-------------------
[1] Enqueue -------------------
[2] Dequeue Masukkan pilihan : 2
[3] Keluar
Mengambil data "23"...
------------------- QUEUE : 33,45
Masukkan pilihan : 1 -------------------
Menu Pilihan
Masukkan Data : 33 -------------------
Data ditambahkan [1] Enqueue
QUEUE : 23,33 [2] Dequeue
------------------- [3] Keluar
Menu Pilihan
------------------- -------------------
[1] Enqueue Masukkan pilihan :

6.3. Implementasi Queue dengan Circular Array

PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA TEKINIK INFORMATIKA 25

 PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA

Contoh Program 23
1. #include <iostream> 62.
2. #define MAX 5 63. void display()
3. using namespace std; 64. {
4. 65. int front_pos = front, rear_pos = rear;
5. class Circular_Queue 66. if (front == -1)
6. { 67. {
7. private: 68. cout<<"Queue elements : Kosong..!\n";
8. int *cqueue_arr; 69. return;
9. int front, rear; 70. }
10. public: 71. cout<<"Queue elements :\n";
11. Circular_Queue() 72. if (front_pos <= rear_pos)
12. { 73. {
13. cqueue_arr = new int [MAX]; 74. while (front_pos <= rear_pos)
14. rear = front = -1; 75. {
15. } 76. cout<<cqueue_arr[front_pos]<<" ";
16.
17. void insert(int item) 77. front_pos++;
18. { 78. }
19. if ((front == 0 && rear == MAX- 79. }
1) || (front == rear+1)) 80. else
20. { 81. {
21. cout<<"Queue Penuh \n"; 82. while (front_pos <= MAX - 1)
22. return; 83. {
23. } 84. cout<<cqueue_arr[front_pos]<<" ";
24. if (front == -1) 85. front_pos++;
25. { 86. }
26. front = 0; 87. front_pos = 0;
27. rear = 0; 88. while (front_pos <= rear_pos)
28. } 89. {
29. else 90. cout<<cqueue_arr[front_pos]<<" ";
30. { 91. front_pos++;
31. if (rear == MAX - 1) 92. }
32. rear = 0; 93. }
33. else 94. cout<<endl;
34. rear = rear + 1; 95. }
35. } 96. };
36. cqueue_arr[rear] = item ; 97.
37. display(); 98. int main()
38. } 99. {
39. 100. int choice, item;
40. void del() 101. Circular_Queue cq;
41. { 102. do
42. if (front == -1) 103. {
43. { 104. cout<<"[Link]\n";
44. cout<<"Queue elements : Kosong..!\n"; 105. cout<<"[Link]\n";
45. return ; 106. cout<<"[Link]\n";
46. } 107. cout<<"Input pilihan : ";
47. cout<<"Element deleted from queue is : "<<c 108. cin>>choice;
queue_arr[front]<<endl; 109. switch(choice)
48. if (front == rear) 110. {
49. { 111. case 1:
50. front = -1; 112. cout<<"Ketik nilai yang akan di queu
51. rear = -1; e : ";
52. } 113. cin>>item;
53. else 114. [Link](item);
54. { 115. break;
55. if (front == MAX - 1) 116. case 2:
56. front = 0; 117. [Link]();
57. else 118. break;
58. front = front + 1; 119. case 3:
59. } 120. break;
60. display(); 121. default:
61. } 122. cout<<"Pilihan salah.!\n";

PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA TEKINIK INFORMATIKA 26

 PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA

123. } 126. return 0;

124. } 127. }
125. while(choice != 3);

Hasil output programnya adalah :

[Link] [Link]
[Link] [Link]
[Link] [Link]
Input pilihan : 1 Input pilihan : 2
Ketik nilai yang akan di queue : 4 Element deleted from queue is : 4
Queue elements : Queue elements :
4 7 6

[Link] [Link]
[Link] [Link]
[Link] [Link]
Input pilihan : 1 Input pilihan : 2
Ketik nilai yang akan di queue : 7 Element deleted from queue is : 7
Queue elements : Queue elements :
4 7 6
[Link]
[Link]
[Link] [Link]
Input pilihan : 1 [Link]
Ketik nilai yang akan di queue : 6 [Link]
Queue elements : Input pilihan : 2
4 7 6 Element deleted from queue is : 6
Queue elements : Kosong..

6.4. Implementasi Queue dengan Double Linked List

Contoh Program 24
1. #include <iostream> 31. tail = pointer;
2. using namespace std; 32. cout << "Element has been inserted in the qu
3. struct Node { eue!" << endl;
4. int data; 33. }
5. Node* next; 34. void Queue::deQueue() {
6. }; 35. if(head == NULL){
7. class Queue { 36. cout << "Queue is empty!" << endl;
8. struct Node* head,* tail; 37. }
9. public: 38. Node* temp = head;
10. Queue() { 39. head = head -> next;
11. head = tail = NULL; 40. delete temp;
12. } 41. }
13. void enQueue(); 42. void Queue::displayQueue() {
14. void deQueue(); 43. Node* pointer1 = head;
15. void displayQueue(); 44. if(head == NULL) {
16. void menu(); 45. cout << "Queue is empty!" << endl;
17. int elem; 46. }
18. int choice; 47. else
19. }; 48. cout << "Elements of your QUEUE!" << endl;
20. void Queue::enQueue() { 49. while (pointer1 != NULL) {
21. cout << "Enter your element to be inserted t 50. cout << pointer1 -> data << endl;
he queue: "; 51. pointer1 = pointer1 -> next;
22. cin >> elem; 52. }
23. Node* pointer = new Node; 53. cout << "End" << endl;
24. pointer -> data = elem; 54. }
25. pointer -> next = NULL; 55. void Queue::menu() {
26. if(head == NULL) { 56. while(1)
27. head = pointer; 57. {
28. } 58. cout<<"==================="<<"\n";
29. else 59. cout<<" 1. Queue"<<"\n";
30. tail -> next = pointer; 60. cout<<" 2. Dequeue"<<"\n";

PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA TEKINIK INFORMATIKA 27

 PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA

61. cout<<" 3. Display Queue"<<"\n"; 75. displayQueue();

62. cout<<" 4. Exit"<<"\n"; 76. break;
63. cout<<"==================="<<"\n"; 77. case 4:
64. cout<<"\nEnter your choice: "; 78. break;
65. cin>>choice; 79. default:
66. switch(choice) 80. cout<<"Enter choice(1-4)";
67. { 81. break;
68. case 1: 82. }
69. enQueue(); 83. }
70. break; 84. }
71. case 2: 85. int main () {
72. deQueue(); 86. Queue frank;
73. break; 87. [Link]();
74. case 3: 88. }
89.

Hasil output programnya adalah :

=================== =====================
1. Queue
2. Dequeue Enter your choice: 3
3. Display Queue Elements of your QUEUE!
4. Exit 8
===================== 6
9
Enter your choice: 1 End
Enter your element to be inserted the ===================
queue: 8 1. Queue
Element has been inserted in the queue! 2. Dequeue
=================== 3. Display Queue
1. Queue 4. Exit
2. Dequeue =====================
3. Display Queue
4. Exit Enter your choice: 2
===================== ===================
1. Queue
Enter your choice: 1 2. Dequeue
Enter your element to be inserted the 3. Display Queue
queue: 6 4. Exit
Element has been inserted in the queue! =====================
===================
1. Queue Enter your choice: 3
2. Dequeue Elements of your QUEUE!
3. Display Queue 6
4. Exit 9
===================== End
===================
Enter your choice: 1 1. Queue
Enter your element to be inserted the 2. Dequeue
queue: 9 3. Display Queue
Element has been inserted in the queue! 4. Exit
=================== =====================
1. Queue
2. Dequeue Enter your choice:
3. Display Queue
4. Exit

PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA TEKINIK INFORMATIKA 28