Queues

Views:
 
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

CSCE 3110 Data Structures & Algorithm Analysis:

CSCE 3110 Data Structures & Algorithm Analysis Rada Mihalcea http://www.cs.unt.edu/~rada/CSCE3110 Queues Reading: Chap. 3 Weiss

Queue:

Queue Stores a set of elements in a particular order Stack principle: FIRST IN FIRST OUT = FIFO It means: the first element inserted is the first one to be removed Example The first one in line is the first one to be served cinemark

Queue Applications:

Queue Applications Real life examples Waiting in line Waiting on hold for tech support Applications related to Computer Science Threads Job scheduling (e.g. Round-Robin algorithm for CPU allocation)

PowerPoint Presentation:

A B A C B A D C B A D C B rear front rear front rear front rear front rear front First In First Out

PowerPoint Presentation:

Applications: Job Scheduling

objects: a finite ordered list with zero or more elements. methods: for all queue  Queue, item  element, max_ queue_ size  positive integer Queue createQ(max_queue_size) ::= create an empty queue whose maximum size is max_queue_size Boolean isFullQ(queue, max_queue_size) ::= if(number of elements in queue == max_queue_size) return TRUE else return FALSE Queue Enqueue(queue, item) ::= if (IsFullQ(queue)) queue_full else insert item at rear of queue and return queue :

objects: a finite ordered list with zero or more elements. methods: for all queue  Queue , item  element , max_ queue_ size  positive integer Queue createQ( max_queue_size ) ::= create an empty queue whose maximum size is max_queue_size Boolean isFullQ( queue, max_queue_size ) ::= if (number of elements in queue == max_queue_size ) return TRUE else return FALSE Queue Enqueue( queue, item ) ::= if (IsFullQ( queue)) queue_full else insert item at rear of queue and return queue Queue ADT

Boolean isEmptyQ(queue) ::= if (queue ==CreateQ(max_queue_size)) return TRUE else return FALSE Element dequeue(queue) ::= if (IsEmptyQ(queue)) return else remove and return the item at front of queue. :

Boolean isEmptyQ( queue ) ::= if ( queue ==CreateQ( max_queue_size )) return TRUE else return FALSE Element dequeue( queue ) ::= if (IsEmptyQ( queue )) return else remove and return the item at front of queue. Queue ADT (cont’d)

Array-based Queue Implementation:

Array-based Queue Implementation As with the array-based stack implementation, the array is of fixed size A queue of maximum N elements Slightly more complicated Need to maintain track of both front and rear Implementation 1 Implementation 2

Queue createQ(max_queue_size) ::= # define MAX_QUEUE_SIZE 100/* Maximum queue size */ typedef struct { int key; /* other fields */ } element; element queue[MAX_QUEUE_SIZE]; int rear = -1; int front = -1; Boolean isEmpty(queue) ::= front == rear Boolean isFullQ(queue) ::= rear == MAX_QUEUE_SIZE-1:

Queue createQ( max_queue_size ) ::= # define MAX_QUEUE_SIZE 100/* Maximum queue size */ typedef struct { int key; /* other fields */ } element; element queue[MAX_QUEUE_SIZE]; int rear = -1; int front = -1; Boolean isEmpty(queue) ::= front == rear Boolean isFullQ(queue) ::= rear == MAX_QUEUE_SIZE-1 Implementation 1: createQ, isEmptyQ, isFullQ

void enqueue(int *rear, element item) { /* add an item to the queue */ if (*rear == MAX_QUEUE_SIZE_1) { queue_full( ); return; } queue [++*rear] = item; } :

void enqueue(int *rear, element item) { /* add an item to the queue */ if (*rear == MAX_QUEUE_SIZE_1) { queue_full( ); return; } queue [++*rear] = item; } Implementation 1: enqueue

element dequeue(int *front, int rear) { /* remove element at the front of the queue */ if ( *front == rear) return queue_empty( ); /* return an error key */ return queue [++ *front]; } :

element dequeue(int *front, int rear) { /* remove element at the front of the queue */ if ( *front == rear) return queue_empty( ); /* return an error key */ return queue [++ *front]; } Implementation 1: dequeue

PowerPoint Presentation:

EMPTY QUEUE [2] [3] [2] [3] [1] [4] [1] [4] [0] [5] [0] [5] front = 0 front = 0 rear = 0 rear = 3 J2 J1 J3 Implementation 2: Wrapped Configuration Can be seen as a circular queue

PowerPoint Presentation:

FULL QUEUE FULL QUEUE [2] [3] [2] [3] [1] [4][1] [4] [0] [5] [0] [5] front =0 rear = 5 front =4 rear =3 J2 J3 J1 J4 J5 J6 J5 J7 J8 J9 Leave one empty space when queue is full Why? How to test when queue is empty? How to test when queue is full?

void enqueue(int front, int *rear, element item) { /* add an item to the queue */ *rear = (*rear +1) % MAX_QUEUE_SIZE; if (front == *rear) /* reset rear and print error */ return; } queue[*rear] = item; } :

void enqueue(int front, int *rear, element item) { /* add an item to the queue */ *rear = (*rear +1) % MAX_QUEUE_SIZE; if (front == *rear) /* reset rear and print error */ return; } queue[*rear] = item; } Enqueue in a Circular Queue

element dequeue(int* front, int rear) { element item; /* remove front element from the queue and put it in item */ if (*front == rear) return queue_empty( ); /* queue_empty returns an error key */ *front = (*front+1) % MAX_QUEUE_SIZE; return queue[*front]; } :

element dequeue(int* front, int rear) { element item; /* remove front element from the queue and put it in item */ if (*front == rear) return queue_empty( ); /* queue_empty returns an error key */ *front = (*front+1) % MAX_QUEUE_SIZE; return queue[*front]; } Dequeue from Circular Queue

List-based Queue Implementation: Enqueue:

void enqueue(pnode front, pnode rear, element item) { /* add an element to the rear of the queue */ pnode temp = (pnode) malloc(sizeof (queue)); if (IS_FULL(temp)) { fprintf(stderr, “ The memory is full\n”); exit(1); } temp->item = item; temp->next= NULL; if (front) { (rear) -> next= temp;} else front = temp; rear = temp; } List-based Queue Implementation: Enqueue

PowerPoint Presentation:

element dequeue(pnode front) { /* delete an element from the queue */ pnode temp = front; element item; if (IS_EMPTY(front)) { fprintf(stderr, “The queue is empty\n”); exit(1); } item = temp->item; front = temp->next; free(temp); return item; } Dequeue

Algorithm Analysis:

Algorithm Analysis enqueue O(?) dequeue O(?) size O(?) isEmpty O(?) isFull O(?) What if I want the first element to be always at Q[0] ?

authorStream Live Help