isd uas 2 queue.ppt
TRANSCRIPT
-
8/14/2019 ISD UAS 2 QUEUE.ppt
1/38
CS2014 Data Structure andAlgorithm
Queue Data Structure
-
8/14/2019 ISD UAS 2 QUEUE.ppt
2/38
30/10/'06 Queue/rmb 2
Apa yang dimaksud queue ?
Apa kegunaan queues ?
Properti apa saja yang dimiliki queues ? Bagaimana implementasinya?
-
8/14/2019 ISD UAS 2 QUEUE.ppt
3/38
30/10/'06 Queue/rmb 3
Apa yang dimaksud queue ?
Queue adalah list yang memiliki aturanmain dalam proses inserted dan removeddata. Istilah lain: FIFO (first in first out)
Insertion atau penambahan data hanyadilakukan di salah satu ujung list (rear) dandeletions hanya dilakukan di ujung lainnya(front)
Queue menyerupai sebuah antrian dalamdunia nyata
-
8/14/2019 ISD UAS 2 QUEUE.ppt
4/38
30/10/'06 Queue/rmb 4
-
8/14/2019 ISD UAS 2 QUEUE.ppt
5/38
30/10/'06 Queue/rmb 5
Apa kegunaan queue ?
Mengatur layanan terhadap suatu taskdalam suatu sistem agar tercipta fairtreatment
client-server systems
operating systems: antrian task, contohantrian untuk mencetak (printing).
simulation and modeling: contoh air trafficcontrol, urban transport .
-
8/14/2019 ISD UAS 2 QUEUE.ppt
6/38
30/10/'06 Queue/rmb 6
Desain abstrak
Abstract Data Type (ADT):
Kumpulan struktur data bersamaan dengan
Kumpulan operasi terhadap struktur data
tersebut
Data structures:
Biasanya bertipe komposit
Formasi dari structs, arrays, strings, dll. Struktur data berkait dengan menggunakan
pointer
-
8/14/2019 ISD UAS 2 QUEUE.ppt
7/38
30/10/'06 Queue/rmb 7
Queue ADT
State abstractly what the operations do,without saying in detail how they areaccomplished.
-
8/14/2019 ISD UAS 2 QUEUE.ppt
8/38
30/10/'06 Queue/rmb 8
Queue ADT
Sebuah queueQ, dari item-item bertipe T adalah deretanitem bertipe T yang memiliki operasi-operasi sebagaiberikut:
1. Inisialisasi queueQ menjadi emptyqueue.2. Menentukan sebuah queue kosong atau tidak,Q, is
empty.
3. Menentukan sebuah queue penuh atau tidak,Q, isfull.
4. Menyisipkan item baru pada ujung belakang (rear)queue,Q.
5. JikaQ tidak kosong, hapus sebuah item pada ujungdepan queue,Q,(front).
-
8/14/2019 ISD UAS 2 QUEUE.ppt
9/38
30/10/'06 Queue/rmb 9
Queue ADT interface
/* File: Queue.h */
typedef char ItemType ;
typedef struct Queue Queue ;
/* Defined Operations */
extern Queue *QueueNew ( void );
/* Initialize the queue Q to be the empty queue. */
extern int QueueEmpty ( Queue *Q );
/* Returns 1 (True) if (and only if) the queue Q is empty*/
extern int QueueFull ( Queue *Q );
/* Returns 1 (True) if (and only if) the queue Q is full */
extern void QueueInsert ( ItemType R, Queue *Q );/* If Q is not full, insert new item R onto the end of Q */
extern void QueueRemove ( Queue *Q, ItemType *F );
/* If Q is not empty, remove its first item, put it in F. */
-
8/14/2019 ISD UAS 2 QUEUE.ppt
10/38
30/10/'06 Queue/rmb 10
Implementasi Queue
Untuk representasi sekuensial menggunakan array:
-
8/14/2019 ISD UAS 2 QUEUE.ppt
11/38
30/10/'06 Queue/rmb 11
Queues dengan Circular
Track
-
8/14/2019 ISD UAS 2 QUEUE.ppt
12/38
30/10/'06 Queue/rmb 12
Queues dengan Circular
TrackBagaiman 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; jikarear=N, set dengan 0.
Rear = (Rear + 1) % N;
Hal yang sama untuk Front: Front = (Front + 1) %N;
-
8/14/2019 ISD UAS 2 QUEUE.ppt
13/38
30/10/'06 Queue/rmb 13
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 danQueueRemove (slide sebelumnya)
-
8/14/2019 ISD UAS 2 QUEUE.ppt
14/38
30/10/'06 Queue/rmb 14
Sequential Queue Representation (I)
/* File: Queue.c */
#include
#include
#include "Queue.h"#define MAXQUEUESIZE 100
struct Queue {
int Count, Front, Rear;
ItemType Items[MAXQUEUESIZE];
} ;
-
8/14/2019 ISD UAS 2 QUEUE.ppt
15/38
30/10/'06 Queue/rmb 15
Sequential Queue Representation (I)
Initialization:
inisialisasi queueQ menjadi queue kosong.
sebuah queue disebut empty jika Count=0.
indeks Front diset = 0.
indeks Rear diset = 0.
-
8/14/2019 ISD UAS 2 QUEUE.ppt
16/38
30/10/'06 Queue/rmb 16
Sequential Queue Representation
/* Initialize the queue Q to be the emptyqueue. */
Queue * QueueNew ( void )
{
Queue *Q = calloc( 1, sizeof( Queue ) ) ;
Q->Count = 0;
Q->Front = 0;
Q->Rear = 0;
return Q ;
}
-
8/14/2019 ISD UAS 2 QUEUE.ppt
17/38
30/10/'06 Queue/rmb 17
Sequential Queue Representation
Empty test: menentukan sebuah queue kosongatau 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 );
}
-
8/14/2019 ISD UAS 2 QUEUE.ppt
18/38
30/10/'06 Queue/rmb 18
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 );
}
-
8/14/2019 ISD UAS 2 QUEUE.ppt
19/38
30/10/'06 Queue/rmb 19
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 (ItemType R, Queue *Q)
{
if (Q->Count == MAXQUEUESIZE) {
printf("INSERT:Not allowed on full queue.\n");exit(1);
} else {
Q->Items[Q->Rear] = R;
Q->Rear = (Q->Rear + 1) % MAXQUEUESIZE;++ (Q->Count);
}
}
-
8/14/2019 ISD UAS 2 QUEUE.ppt
20/38
30/10/'06 Queue/rmb 20
Sequential Queue Representation
Jika queueQ is not empty, remove sebuah item dari front sebuahQ.
/* If Q is not empty, remove first item and put it in Fby:
* 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, ItemType *F )
{
if ( Q->Count == 0 ) {
printf("REMOVE:Not allowed on empty q.\n");exit(1);
} else {
*F = Q->Items [Q->Front];Q->Front = (Q->Front + 1) % MAXQUEUESIZE;
-- (Q->Count);
}
}
-
8/14/2019 ISD UAS 2 QUEUE.ppt
21/38
30/10/'06 Queue/rmb 21
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 );
...
}
= tulis kode tersebut tanpa mengetahui bagaimanaqueue tersebut diimplementasikan.
-
8/14/2019 ISD UAS 2 QUEUE.ppt
22/38
30/10/'06 Queue/rmb 22
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
-
8/14/2019 ISD UAS 2 QUEUE.ppt
23/38
30/10/'06 Queue/rmb 23
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: a
-
8/14/2019 ISD UAS 2 QUEUE.ppt
24/38
30/10/'06 Queue/rmb 24
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: a, b
-
8/14/2019 ISD UAS 2 QUEUE.ppt
25/38
30/10/'06 Queue/rmb 25
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: a, b, c
-
8/14/2019 ISD UAS 2 QUEUE.ppt
26/38
30/10/'06 Queue/rmb 26
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: b, c Print:Just got: a.
-
8/14/2019 ISD UAS 2 QUEUE.ppt
27/38
30/10/'06 Queue/rmb 27
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: c Print:Just got: b.
-
8/14/2019 ISD UAS 2 QUEUE.ppt
28/38
30/10/'06 Queue/rmb 28
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: c, d
-
8/14/2019 ISD UAS 2 QUEUE.ppt
29/38
30/10/'06 Queue/rmb 29
Linked Queue Representations
Representasi berikut menggunakan pointer padafrontdan rear.
Setiap node terdiri atas item queue yaitu item memberdan links ke node berikutnya pada list, menggunakan
pointer pada link member.
-
8/14/2019 ISD UAS 2 QUEUE.ppt
30/38
30/10/'06 Queue/rmb 30
Linked Queue Implementation
Conditional checks untuk kondisi tertentupada linked queue implementation:
-
8/14/2019 ISD UAS 2 QUEUE.ppt
31/38
30/10/'06 Queue/rmb 31
Linked Queue Representations
/*File: queueTypes.h*/
typedef arbitrary itemType; /*theitemType can be arbitraty*/
typedef struct tQueueNode{
itemType item;struct tQueueNode *address;
}QueueNode;
typedef struct {
QueueNode *front;QueueNode *rear;
}Queue;
-
8/14/2019 ISD UAS 2 QUEUE.ppt
32/38
30/10/'06 Queue/rmb 32
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;
}
-
8/14/2019 ISD UAS 2 QUEUE.ppt
33/38
30/10/'06 Queue/rmb 33
Linked Queue Implementation
Empty test: menentukan sebuah queuekosong atau tidak,Q, is empty.
Sebuah queue didefinisikan empty jika front
= NULL.
int Empty(Queue *Q)
{return (Q->front==NULL);
}
-
8/14/2019 ISD UAS 2 QUEUE.ppt
34/38
30/10/'06 Queue/rmb 34
Linked Queue Implementation
Full test: menentukan sebuah queue penuh atau tidak,Q, is full.
/* we assume an already constructed
queue, Q, is not full, since itcould potentially grow as a linkedstructured */
int Full(Queue *Q)
{
return 0;
}
-
8/14/2019 ISD UAS 2 QUEUE.ppt
35/38
30/10/'06 Queue/rmb 35
Linked Queue Implementation
Insert item baru ke ujung rear suatu queue,Q.void Insert(itemType R, Queue *Q)
{
QueueNode *temp;
/*attempt to allocate a new node*/
temp=(QueueNode*)malloc(sizeof(QueueNode));
if (temp==NULL){
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;
}
}
}
-
8/14/2019 ISD UAS 2 QUEUE.ppt
36/38
30/10/'06 Queue/rmb 36
Linked Queue Implementation
TerdapatQ tidak kosong, remove sebuah itam dari front sebuah queueQ.
void remove(Queue *Q,itemType *F)
{
QueueNode *temp;
if (Q->front==NULL){
systemErr(attempt to remove item from emptyqueue);
}else{
*F=Q->front->item;
temp=Q->front;
Q->front=temp->address;free(temp);
if (Q->front==NULL) Q->rear=NULL;
}
}
-
8/14/2019 ISD UAS 2 QUEUE.ppt
37/38
30/10/'06 Queue/rmb 37
Queue Applications
Queues pada operating systems
Menggunakan queues sebagai memorybuffers
Queues pada simulation experiments
Clients - servers
Simulating supermarket checkout lines
-
8/14/2019 ISD UAS 2 QUEUE.ppt
38/38
30/10/'06 Queue/rmb 38
References
Lectures stacks and queues. Dept ofComputer Science, University of Bristol,2004
Thomas A. Standish,Data Structures,
Algorithms & Software Principles in C
Addison-Wesley, 1995 p. 253 ff (Chapter
7)