praktikum struktur data queueelearning.amikom.ac.id/.../2014/04/20140403_prak_5_queue.ppsqueue...

PRAKTIKUMSTRUKTUR DATA

QUEUE

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.

1234567891011121314

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 PopB. Input and RemoveC. Enqueue and DequeueD. 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 StackB. A Stack and A QueueC. A Linked list and A QueueD. 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=-1B. Head=0 and Tail=0C. Head<=0 and Tail<=0D. Head<1 and Tail<1

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