Queue Priority Queue STRUKTUR DATA. JULIO ADISANTOSO Departemen Ilmu Komputer IPB. Pertemuan 6 : 7 Juli 2015

Queue Priority Queue

STRUKTUR DATA JULIO ADISANTOSO Departemen Ilmu Komputer IPB

Pertemuan 6 : 7 Juli 2015

JULIO ADISANTOSO Departemen Ilmu Komputer IPB

STRUKTUR DATA


Pengertian Implementasi

QUEUE


STRUKTUR DATA



Queue Beberapa pengertian Queue pada Struktur Data: antrian dari objek deretan objek dimana penambahan hanya bisa dilakukan pada suatu ujung (disebut sisi belakang atau rear), dan penghapusan dilakukan lewat ujung yang lain (disebut dengan sisi depan atau front).


STRUKTUR DATA



Sifat Queue FIFO : First In First Out Objek yang pertama masuk ke dalam Queue akan menjadi yang pertama keluar dari Queue Beberapa contoh penggunaan Queue: Print spooler Beberapa algoritme Search, misal BFS


STRUKTUR DATA



Operasi dasar Queue ⇒ Spesifikasi PRIMITIF push(objek) : memasukkan objek ke dalam Queue pop() : menghapus objek dari Queue front() : akses objek front back() : akses objek rear empty() : memeriksa Queue kosong size() : ukuran Queue full() : memeriksa Queue penuh (in array)


STRUKTUR DATA



Implementasi Queue Queue dapat diimplementasikan dengan menggunakan tipe data apa pun, asalkan memenuhi sifat dan kaidah Queue, yaitu FIFO. Contoh implementasi: Array Linked List

Tiap implementasi memiliki plus dan minus. Apa saja?


STRUKTUR DATA



Queue Menggunakan DLL (p06a.cpp) typedef struct node { int value; struct node *prev, *next; } NODE; class Queue { NODE *Front, *Rear; public: Queue() { Front=NULL; Rear=NULL; } bool empty() { return (Front==NULL); } void push(int nilai); int front(); int back(); void pop(); }; JULIO ADISANTOSO Departemen Ilmu Komputer IPB

STRUKTUR DATA



Queue Menggunakan DLL Contoh Driver int main() { Queue antrian; antrian.push(10); antrian.push(20); antrian.push(15); antrian.push(7); cout << "Queue awal:\n"; cout << antrian; cout << "\nFront: " << antrian.front() << endl; cout << "\nRear: " << antrian.back() << endl; antrian.pop(); antrian.pop(); cout << "\nQueue akhir:\n"; cout << antrian; return 0; }


STRUKTUR DATA



Queue Menggunakan DLL Fungsi push(nilai) void Queue::push(int nilai) { NODE *temp=new(NODE); temp->value=nilai; temp->prev=NULL; temp->next=NULL; if (empty()) { Front=temp; Rear=temp; } else {Rear->next=temp; temp->prev=Rear; Rear=temp;} }

Fungsi pop() – tidak mengambil nilai void Queue::pop() { if (empty()) cout << "Queue is empty\n"; else Front=Front->next; } JULIO ADISANTOSO Departemen Ilmu Komputer IPB

STRUKTUR DATA



Queue Menggunakan DLL Fungsi front() dan back() hanya meng-copy nilai dari Queue. Fungsi front() int Queue::front() { if (empty()) {cout << "Queue is empty\n"; return -1;} else return Front->value; }

Fungsi back() int Queue::back() { if (empty()) {cout << "Queue is empty\n"; return -1;} else return Rear->value; }


STRUKTUR DATA



Queue Menggunakan Array Dalam driver terdapat pernyataan cout<next) out << ptr->value << endl; } return out; }


STRUKTUR DATA



Queue Menggunakan STL queue (p06b.cpp) Spesifikasi TYPE #include <stack> typedef queue Queue; Fungsi operator<< ostream& operator<< (ostream &out, Queue q) { if (q.empty()) out << "Stack is empty\n"; else { while (!q.empty()) { out << q.front() << endl; q.pop(); } } return out; } JULIO ADISANTOSO Departemen Ilmu Komputer IPB

STRUKTUR DATA


Priority Queue (pq) Queue ini tidak bersifat FIFO murni tetapi biasanya didasarkan pada suatu prioritas tertentu. Data paling atas adalah data dengan prioritas paling tinggi. Contoh: pq.push(30); pq.push(100); pq.push(25); pq.push(40);


STRUKTUR DATA


PQ Menggunakan DLL (p06c.cpp) Fungsi push(nilai) void Queue::push(int nilai) { NODE *temp=new(NODE); temp->value=nilai; temp->prev=NULL; temp->next=NULL; if (empty()) { Front=temp; Rear=temp; } else { NODE *ptr=Front; if (Front->valuevaluenext; } if (ptr==NULL) { // push back } else { // insert before ptr } } } } JULIO ADISANTOSO Departemen Ilmu Komputer IPB STRUKTUR DATA


PQ Menggunakan STL priority queue (p06d.cpp) Fungsi push(nilai) #include typedef priority_queue Queue; int main() { Queue antrian; antrian.push(30); antrian.push(100); antrian.push(25); antrian.push(40); cout << "Queue awal:\n"; cout << antrian; antrian.pop(); antrian.pop(); cout << "\nQueue akhir:\n"; cout << antrian; return 0; } JULIO ADISANTOSO Departemen Ilmu Komputer IPB

STRUKTUR DATA


Latihan (p06e.cpp) Gunakan struktur priority queue untuk memasukkan data NIM, gender, dan tinggi berikut. Priority berdasarkan nilai tinggi. 5 G64090120 G64090160 G64090140 G64090050 G65090025

1 2 1 2 1

165.4 169.7 170.2 168.3 167.9


STRUKTUR DATA


Latihan (p06e.cpp) Spesifikasi Type #include <string> #include using namespace std; struct record { string nim; int gender; double tinggi; }; typedef struct record Record; typedef priority_queue PQ;


STRUKTUR DATA


Latihan (p06e.cpp) Karena queue memiliki prioritas yang ditunjukkan oleh nilai variabel tinggi, maka harus dibuat operator overloading untuk tanda < secara khusus. Fungsi operator< bool operator<(const Record a, const Record b) { return a.tinggi < b.tinggi; }


STRUKTUR DATA


Latihan (p06e.cpp) Program Driver int main() { PQ antrian; int n; cin >> n; Record t; while (n--) { cin >> t.nim >> t.gender >> t.tinggi; antrian.push(t); } cout << "PQ awal:\n"; cout << antrian; return 0; } JULIO ADISANTOSO Departemen Ilmu Komputer IPB

STRUKTUR DATA

Queue Priority Queue STRUKTUR DATA. JULIO ADISANTOSO Departemen Ilmu Komputer IPB. Pertemuan 6 : 7 Juli 2015

Recommend Documents