PRAKTIKUM
STRUKTUR DATA QUEUE
SULIDAR FITRI, M.Sc
QUEUE • Secara harafiah, queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehiduypan sehari-hari, misalnya saat Anda mengantri di loket untuk membeli tiket.
• Queue merupakan kumpulan data dengan penambahan data hanya melalui satu sisi, yaitu belakang (tail) dan penghapusan data hanya melalui sisi depan (head).
• Queue bersifat FIFO(First In First Out), • yaitu data yang pertama masuk akan keluar terlebih dahulu dan data yang terakhir masuk akan keluar terakhir.
Beberapa Operasi Pada QUEUE • IsEmpty • IsFull • Enqueue • Dequeue • Clear • View
: Mengecek apakah queue kosong atau tidak : Mengecek apakah queue sudah penuh atau belum : Menambahkan data di queue : Mengambil data dari queue : Menghapus data dalam antrian : melihat data dalam antrian
1. Deklarasi Awal Queue • Variabel yang akan digunakan adalah data (array sebagai tempat queue), head, tail. • Sama seperti Stack, Nilai dari head dan tail dimulai dari -1 yang menandakan queue kosong. • Sebagai contoh kita akan membuat queue dengan data maksimal sebanyak 7 data. 1#define max 7 2 3int data[max]; 4int head=-1, tail=-1;
2. IsEmpty • Berguna untuk mengecek apakah queue kosong atau tidak. • Indikator bahwa queue kosong adalah nilai dari head dan tail bernilai -1. • Sehingga kita tinggal buat fungsi nya sebagai berikut :
1bool IsEmpty(){ 2 if(head == -1 && tail == -1) 3 return true; 4 else 5 return false; 6}
3. IsFull • Mengecek apakah queue sudah penuh atau belum. • Indikator kalau queue penuh adalah nilai tail = max – 1. Mengapa? • Karena nilai maksimal pada array yang mempunyai index 7 pada saat diakses akan mempunyai nilai maksimal 6. Sehingga fungsi yang terbentuk seperti ini bool IsFull(){ if(tail == max-1) return true; else return false; }
4. Enqueue • Enqueue digunakan untuk memasukkan data kedalam queue. • Mengecek terlebih dahulu apakah queue / antrian sudah penuh atau belum. • Kalau belum maka kita harus mengecek apakah head sudah berada pada nilai 0 atau belum. • nilai head tidak akan lebih dari 0. • Yang akan bergerak terus adalah tail, sedangkan head hanya penunjuk urutan paling depan, sehingga nilainya tidak pernah lebih dari 0. • Kecuali antrian kosong, maka posisi head dan tail akan kembali menjadi -1.
void Enqueue(){ 1 if(IsFull()) { 2 cout<<"Antrian sudah penuh, mohon tunggu 3 beberapa saat lagi "; 4 getch(); 5 } else { 6 if (IsEmpty()){ 7 head=tail=0; 8 cout<<"Masukkan data : ";cin>>data[tail]; 9 } else { 10 tail++; 11 cout<<"Masukkan data : ";cin>>data[tail]; 12 } 13 } 14 }
5. Dequeue • Digunakan untuk mengambil data yang sudah masuk di urutan pertama. • Sehingga kita tinggal membaca data yang ada di posisi head. • Jangan lupa kita cek dulu apakah queue kosong atau tidak. • Tapi jika ada isinya, setelah data diambil, data dibelakangnya digeser ke depan.
1void Dequeue(){ 2 if(IsEmpty()){ 3 cout<<"Antrian kosong ! "; 4 getch(); 5 } else { 6 cout<<"Data yang diambil : "<
6. Clear • Operasi clear digunakan untuk menghapus data yang ada di dalam queue. • Caranya cukup merubah nilai pada head dan tail menjadi -1. • Tidak perlu diperhatikan data yang ada di dalam array. Nantinya data data tersebut juga akan ditimpa. void Clear(){ 1 head=tail=-1; 2 cout<<"Antrian sudah 3 dikosongkan ! ";getch(); 4 }
7. View • Operasi ini digunakan untuk melihat data yang ada didalam queue. • Caranya adalah dengan membaca data pada index yang terdapat diantara head sampai tail 1void 2 3 4 5 6 7 8 9 10}
View(){ if(IsEmpty()){ cout<<"Antrian kosong ! "; getch(); } else { for(a=head;a<=tail;a++) cout<<"Data pada antrian ke "<
1main(){ 2int jawab; 3do{ 4clrscr(); 5cout<<"--------- Program Queue by adeethunix ------------"<<endl; 6cout<<"1. Enqueue "<<endl; 7cout<<"2. Dequeue "<<endl; 8cout<<"3. Clear "<<endl; 9cout<<"4. View "<<endl; 10cout<<"5. Exit "<<endl; 11cout<<"Masukkan pilihan Anda : "; 12cin>>jawab; 13switch(jawab){ 14case 1: 15Enqueue();break; 16case 2: 17Dequeue();break; 18case 3: 19Clear();break; 20case 4: 21View();break; 22} 23}while (jawab != 5); 24}
3.
4. The keyword used to place an item into a stack is ______ remove an item from a stack is ________ A. B. C. D.
Push and Pop Input and Remove Enqueue and Dequeue IsFull and IsEmpty
5. An example of a FIFO data strucure is________ and An example of a LIFO data structure is _______ A. B. C. D.
A Queue and A Stack A Stack and A Queue A Linked list and A Queue A Stack and A Linked list
6. Which of the following is not a basic operation that can be performed on a queue? • (a) Inserting an item at the back of the queue • (b) Removing an item from the front of the queue • (c) Accessing an item from the front of the queue • (d) Inserting an item into the second position of the queue
7. Consider the following sequence of operations applied to an empty queue: Insert element with value 3 Insert element with value 8 Remove element Insert element with value 1 Remove element Insert element with value 7
The next element removed from this queue will have which of the following values?
• (a) 8 • (b) 1 • (c) 7 • (d) 3
8. What is the similar operation in Queue and Stack operation about Pushing and Popping ? • (a) Input and Remove • (b) Enqueue and Dequeue • (c) IsFull and IsEmpty • (d) Whatever
9. Consider the following program, what is the output of first element and last element? queue q; for( int i = 0; i < 5; i++ ) { q.push(i); } cout << "The first element is " << q.front() << " and the last element is " << q.back() << endl;
• (a) 0 and 4 • (b) 0 and 5 • (c) 1 and 5 • (d) 1 and 4
10. How to declare the beginning of Queue? When the first time is empty A. B. C. D.
Head=-1 and Tail=-1 Head=0 and Tail=0 Head<=0 and Tail<=0 Head<1 and Tail<1
• Source code : http://masiyak.com/queue-antrian-di-struktur-data/
