DIG1G3 Implementasi Struktur Data

DIG1G3 Implementasi Struktur Data Program Studi Diploma III Teknik Informatika Fakultas Ilmu Terapan Telkom University Dosen: Cahyana, S.T., M.Kom. Indra Azimi, S.T., M.T.

2 Queue/rmb

• • • •

30/10/'06

Apa yang dimaksud queue ? Apa kegunaan queues ? Properti apa saja yang dimiliki queues ? Bagaimana implementasinya?

3 Queue/rmb

30/10/'06

Apa yang dimaksud queue ? • Queue adalah list yang memiliki “aturan main” dalam proses inserted dan removed data. • Konsep queue adalah FIFO (first in first out) • Insertion/Enqueue atau penambahan data hanya dilakukan di salah satu ujung list (rear) dan deletions/dequeue hanya dilakukan di ujung lainnya (front) • Queue menyerupai sebuah antrian dalam dunia nyata

4 Queue/rmb

30/10/'06

Apa kegunaan queue ? • Mengatur layanan terhadap suatu task dalam suatu sistem agar tercipta “fair treatment” ▫ client-server systems ▫ operating systems: antrian task, contoh antrian untuk mencetak (printing). ▫ simulation and modeling: contoh air traffic control, urban transport .

5 Queue/rmb

30/10/'06

Queue ADT Operasi yang mungkin ada pada Queue: 1. 2. 3. 4. 5.

Inisialisasi queue Q menjadi empty queue. Menentukan sebuah queue kosong atau tidak, Q, is empty. Menentukan sebuah queue penuh atau tidak, Q, is full. Jika Q tidak penuh, sisipkan item baru pada ujung belakang (rear) queue, Q. Jika Q tidak kosong, hapus sebuah item pada ujung depan (front) queue, Q.

6 Queue/rmb

30/10/'06

Queue ADT interface /* File: Queue.h */ #define MAXQUEUESIZE 100 struct Queue { int Count, Front, Rear; char Items[MAXQUEUESIZE]; }; /* Defined Operations */ Queue *QueueNew (); /* Initialize the queue Q to be the empty queue. */ int QueueEmpty ( Queue *Q ); /* Returns 1 (True) if (and only if) the queue Q is empty*/ int QueueFull ( Queue *Q ); /* Returns 1 (True) if (and only if) the queue Q is full */ void QueueInsert (char R, Queue *Q ); /* If Q is not full, insert new item R onto the end of Q */ void QueueRemove ( Queue *Q, char *F ); /* If Q is not empty, remove its first item, put it in F. */

7 Queue/rmb

30/10/'06

Implementasi Queue Untuk representasi sekuensial menggunakan array:

8 Queue/rmb

30/10/'06

Queues dengan Circular Track

9 Queue/rmb

30/10/'06

Queues dengan Circular Track Bagaimana implementasi dalam program? • Menggunakan linear array berukuran N. • Menggunakan modular arithmetic: ekspresi X % N menghasilkan nilai X tetap dalam range 0..N-1. ▫ Set Rear: tambahkan nilai rear lama dengan 1; jika rear=N, set dengan 0. ▫ Rear = (Rear + 1) % N; ▫ Hal yang sama untuk Front: Front = (Front + 1) % N;

10 Queue/rmb

30/10/'06

Sequential Queue Representation (I) • Definisikan MAXQUEUESIZE sebagai konstanta. • Sebuah queue merupakan struct yang mengandung: ▫ ▫ ▫ ▫

number of items pada queue sebagai Count member Array item queue sebagai Items member Array indeks (Front) Array indeks (Rear)

• File Queue.c berisi definisi dan operasi QueueNew, QueueEmpty, QueueFull, QueueInsert dan QueueRemove (slide sebelumnya)

11 Queue/rmb

30/10/'06

Sequential Queue Representation (I) Initialization: • inisialisasi queue Q menjadi queue kosong. • sebuah queue disebut empty jika Count =0. – Count diset = 0. – indeks Front diset = 0. – indeks Rear diset = 0.

12 Queue/rmb

30/10/'06

Sequential Queue Representation /* Initialize the queue Q to be the empty queue. */ Queue * QueueNew () { Queue *Q = new Queue; Q->Count = 0; Q->Front = 0; Q->Rear = 0; return Q ; }

13 Queue/rmb

30/10/'06

Sequential Queue Representation • Empty test: menentukan sebuah queue kosong atau tidak, Q, is empty. ▫ Sebuah queue didefinisikan empty jika Count =0. /* Returns 1 (True) if (and only if) * the queue Q is empty. */ int QueueEmpty ( Queue *Q ) { return ( Q->Count == 0 ); }

14 Queue/rmb

30/10/'06

Sequential Queue Representation • Full test: menentukan sebuah queue penuh atau tidak, Q, is full. ▫ sebuah queue didefinisikan full jika Count = MAXQUEUESIZE.

/* Returns 1 (True) if (and only if) * the queue Q is full. */ int QueueFull ( Queue *Q ) { return ( Q->Count == MAXQUEUESIZE ); }

15 Queue/rmb

30/10/'06

Sequential Queue Representation Insert a new item onto the rear of the queue, Q. /* If Q is not full, insert a new item R onto rear of Q by: * 1. storing R in the item array at position Rear; * 2. incrementing Rear by one (WRAP AROUND!); * 3. incrementing Count by one. */ void QueueInsert (char R, Queue *Q) { if (Q->Count == MAXQUEUESIZE) { cout<<"INSERT:Not allowed on full queue.“<<endl; } else { Q->Items[Q->Rear] = R; Q->Rear = (Q->Rear + 1) % MAXQUEUESIZE; Q->Count++; } }

16 Queue/rmb

30/10/'06

Sequential Queue Representation Jika queue Q is not empty, remove sebuah item dari front sebuah Q. /* If Q is not empty, remove first item and put it in F by: * 1. taking F from the item array at position Front; * 2. incrementing Front by one (WRAP AROUND!); * 3. decrementing Count by one. */ void QueueRemove ( Queue *Q, char *F ) { if ( Q->Count == 0 ) { cout<<“REMOVE:Not allowed on empty q.“<<endl; } else { *F = Q->Items [Q->Front]; Q->Front = (Q->Front + 1) % MAXQUEUESIZE; Q->Count--; } }

17 Queue/rmb

30/10/'06

Using the Queue interface #include "QueueInterface.h" /* Assume ItemType is char.*/ /* Access operations and types for stacks.*/ int main () { Queue *tq; /* char C; tq = QueueNew QueueInsert ( QueueInsert ( QueueInsert ( QueueRemove ( QueueRemove ( QueueInsert ( ... }

Variable TestQueue of type Queue. */ ( ); /* Make tq empty. */ ’a’, tq ); ’b’, tq ); ’c’, tq ); tq, &C ); printf ( "Just got: %c.\n", C ); tq, &C ); printf ( "Just got: %c.\n", C ); ’d’, tq );

Orang lain dapat menulis kode di atas tanpa mengetahui bagaimana queue tersebut diimplementasikan.

18 Queue/rmb

30/10/'06

Using the Queue interface #include "QueueInterface.h" /* Assume ItemType is char.*/ /* Access operations and types for stacks.*/ int main ( void ) { Queue *tq; /* Variable TestQueue of type Queue. */ char C; tq = QueueNew ( ); /* Make tq empty. */ QueueInsert ( ’a’, tq ); QueueInsert ( ’b’, tq ); QueueInsert ( ’c’, tq ); QueueRemove ( tq, &C ); printf ( "Just got: %c.\n", C ); QueueRemove ( tq, &C ); printf ( "Just got: %c.\n", C ); QueueInsert ( ’d’, tq ); ... }

Queue: Empty

19 Queue/rmb

30/10/'06

Using the Queue interface #include "QueueInterface.h" /* Assume ItemType is char.*/ /* Access operations and types for stacks.*/ int main ( void ) { Queue *tq; /* Variable TestQueue of type Queue. */ char C; tq = QueueNew QueueInsert ( QueueInsert ( QueueInsert ( QueueRemove ( QueueRemove ( QueueInsert ( ... }

Queue: a

( ); /* Make tq empty. */ ’a’, tq ); ’b’, tq ); ’c’, tq ); tq, &C ); printf ( "Just got: %c.\n", C ); tq, &C ); printf ( "Just got: %c.\n", C ); ’d’, tq );

20 Queue/rmb

30/10/'06


Queue: a, b

21 Queue/rmb

30/10/'06


Queue: a, b, c

22 Queue/rmb

30/10/'06


Queue: b, c Print: Just got: a.

23 Queue/rmb

30/10/'06


Queue: c Print: Just got: b.

24 Queue/rmb

30/10/'06


Queue: c, d

25 Queue/rmb

30/10/'06

Linked Queue Representations • Representasi berikut menggunakan pointer pada front dan rear. • Setiap node terdiri atas item queue yaitu item member dan links ke node berikutnya pada list, menggunakan pointer pada link member.

26 Queue/rmb

30/10/'06

Linked Queue Implementation Conditional checks untuk kondisi tertentu pada linked queue implementation:

27 Queue/rmb

30/10/'06

Linked Queue Representations /*File: queueTypes.h*/ typedef struct tQueueNode{ char item; tQueueNode *address; } QueueNode; typedef struct tQueue { QueueNode *front; QueueNode *rear; } Queue;

28 Queue/rmb

30/10/'06

Linked Queue Implementation #include “QueueInterface.h” /*Initialize the queue Q to be the empty queue*/ void InitializeQueue(Queue *Q) { Q->front=NULL; Q->rear=NULL; }

29 Queue/rmb

30/10/'06

Linked Queue Implementation • Empty test: menentukan sebuah queue kosong atau tidak, Q, is empty. ▫ Sebuah queue didefinisikan empty jika front = NULL. boolean Empty(Queue *Q) { return (Q->front==NULL); }

30 Queue/rmb

30/10/'06

Linked Queue Implementation • Full test: menentukan sebuah queue penuh atau tidak, Q, is full. boolean Full(QueueNode *nB) { return (nB==NULL); }

31 Queue/rmb

30/10/'06

Linked Queue Implementation Insert item baru ke ujung rear suatu queue, Q. void Insert(char R, Queue *Q) { QueueNode *temp = new QueueNode; if (Full(temp)) { systemError(“system storage is exhausted”) } else{ temp->item = R; temp->address=NULL; if (Q->rear==NULL){ Q->front=temp; Q->rear=temp; }else{ Q->rear->address=temp; Q->rear=temp; } } }

32 Queue/rmb

30/10/'06

Linked Queue Implementation Terdapat Q tidak kosong, remove sebuah item dari front sebuah queue Q. void remove(Queue *Q, char *F) { QueueNode *temp; if (Q->front==NULL){ systemErr(“attempt to remove item from empty queue”); }else{ *F=Q->front->item; temp=Q->front; Q->front=temp->address; free(temp); if (Q->front==NULL) Q->rear=NULL; } }

33 Queue/rmb

30/10/'06

Queue Applications • Queues pada operating systems ▫ Menggunakan queues sebagai memory buffers

• Queues pada simulation experiments ▫ Clients - servers ▫ Simulating supermarket checkout lines

34 Queue/rmb

30/10/'06

References • Lectures stacks and queues. Dept of Computer Science, University of Bristol, 2004 • Thomas A. Standish,“Data Structures, Algorithms & Software Principles in C” AddisonWesley, 1995 p. 253 ff (Chapter 7) • Tjokorda Agung Budi Wirayuda, “PI1043 Struktur Data: Queue Data Structure”.

DIG1G3 Implementasi Struktur Data

Recommend Documents