praktikum struktur data queue -...

PRAKTIKUM

STRUKTUR DATAQUEUE

SULIDAR FITRI, M.Sc

QUEUE

• Secara harafiah, queue berarti antrian, queue merupakan salahsatu contoh aplikasi dari pembuatan double linked list yang cukupsering kita temui dalam kehiduypan sehari-hari, misalnya saatAnda 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 : Mengecek apakah queue kosong atau tidak

• IsFull : Mengecek apakah queue sudah penuh atau belum

• Enqueue : Menambahkan data di queue

• Dequeue : Mengambil data dari queue

• Clear : Menghapus data dalam antrian

• View : 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.

1234

#define max 7

int data[max];int 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 :

123456

bool IsEmpty(){if(head == -1 && tail == -1)

return true;else

return false;}

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.

123456789

1011121314

void Enqueue(){if(IsFull()) {

cout<<"Antrian sudah penuh, mohon tunggu beberapa saat lagi ";

getch();} else {

if (IsEmpty()){head=tail=0;cout<<"Masukkan data : ";cin>>data[tail];

} else {tail++;cout<<"Masukkan data : ";cin>>data[tail];

}}

}

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.

12345678910111213

void Dequeue(){if(IsEmpty()){

cout<<"Antrian kosong ! ";getch();

} else {cout<<"Data yang diambil : "<<data[head];for(a=head;a<=tail-1;a++)

data[a]=data[a+1];tail--;if(tail == -1)

head = -1;}

}

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.

1234

void Clear(){head=tail=-1;cout<<"Antrian sudah

dikosongkan ! ";getch();}

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

12345678910

void View(){if(IsEmpty()){

cout<<"Antrian kosong ! ";getch();

} else {for(a=head;a<=tail;a++)

cout<<"Data pada antrian ke "<<a<<" = "<<data[a]<<endl;getch();

}}

123456789101112131415161718192021222324

main(){int jawab;do{clrscr();cout<<"--------- Program Queue by adeethunix ------------"<<endl;cout<<"1. Enqueue "<<endl;cout<<"2. Dequeue "<<endl;cout<<"3. Clear "<<endl;cout<<"4. View "<<endl;cout<<"5. Exit "<<endl;cout<<"Masukkan pilihan Anda : ";cin>>jawab;switch(jawab){case 1:Enqueue();break;case 2:Dequeue();break;case 3:Clear();break;case 4:View();break;}}while (jawab != 5);}

3.

A. Push and Pop

B. Input and Remove

C. Enqueue and Dequeue

D. IsFull and IsEmpty

4. The keyword used to place an item into a stack is ______ remove an item from a stack is ________

A. A Queue and A Stack

B. A Stack and A Queue

C. A Linked list and A Queue

D. A Stack and A Linked list

5. An example of a FIFO data strucure is________

and An example of a LIFO data structure is _______

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 8Remove elementInsert element with value 1Remove elementInsert 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<int> 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. Head=-1 and Tail=-1

B. Head=0 and Tail=0

C. Head<=0 and Tail<=0

D. Head<1 and Tail<1

• Source code : http://masiyak.com/queue-antrian-di-struktur-data/