Data Structures & Algorithm Queues T. Souad alonazi 1-What is a queue? Stores a set of elements in a particular order Queue 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 What is a queue? A queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (called the rear of the queue) Queues vs.stacks In a stack, all insertions and deletions occur at one end, the top, of the list(LIFO (last in, first out)). In the queue all deletions occur at the head of the list. However, all insertions to the queue occur at the tail of the list. Introduction to Queues Basically, data enters the queue at one end and exits at the other end. A B C Front Rear B Front C Rear Applications Ticketing counter Bus stop line Bank Customers Job scheduling (e.g. Round-Robin algorithm for CPU allocation) Applications: Job Scheduling front rear Q[0] Q[1] Q[2] Q[3] -1 -1 -1 0 J1 -1 1 J1 J2 -1 2 J1 J2 J3 0 2 J2 J3 1 2 J3 Comments queue is empty Job 1 is added Job 2 is added Job 3 is added Job 1 is deleted Job 2 is deleted First In First Out A rear front B A C rear B front A D rear C B front A rear D C front B rear front 2-queue Implementation Queue Operations Two BASIC operations Enqueue(add element to a Queue) Dequeue(delete element from a Queue) Additional operations initializeQueue, isEmptyQueue, isFullQueue. queueFront, queueRear pointers( initially=-1) Keep track of front and rear 11 A. Implementation of Queues as Arrays Four member variables Array to store queue elements Variables queueFront, queueRear Variable maxQueueSize Using queueFront, queueRear to access queue elements queueFront: first queue element index queueRear: last queue element index • queueFront changes after each dequeue operation • queueRear changes after each enqueue operation 12 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 Implementation 1: createQ, isEmptyQ, isFullQ 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: enqueue 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: dequeue 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]; } 1) Initially f=-1,r=-1(f= = r=>empty) 2) enqueue(16) => f=-1,r=0 16 3) enqueue(13) => f=-1,r=1 16 13 4) enqueue(6) => f=-1,r=2 16 13 6 5) enqueue(5) => f=-1,r=3 16 13 6 5 6) dequeue => f=0,r=3 × 16 13 6 5 7) dequeue => f=1,r=3 6 × ×13 16 5 8) enqueue(1) => f=1,r=4 6 × ×13 16 5 1 9) Dequeue Three times=> f=4, r=4 (f= = r=>empty) × ×13 16 × 6 5 × × 1 10) enqueue(20,2) => f=4, r=6 × ×13 × 16 6 5 × × 1 11) Dequeue twice=> × ×13 × 16 6 5 × ×13 × 6 5 × × 2 f=6, r=6(empty queue) × ×20 1 12) enqueue(3,5,7) => 16 20 2 f=6, × ×20 1 × r=9(full=>r=size-1)?? 2 × 3 5 7 Implementation issues There is a problem in the first implementation: we can’t enqueue any element because the queue is full although there are empty spaces, so we need a solution?? Circular implementation Implement the queue as a circular structure. How do we know if a queue is full or empty? Initialization of front and rear. Testing for a full or empty queue. Implementation 2: Wrapped Configuration EMPTY QUEUE [2] [1] [3] [4] Can be seen as a circular queue Circular Queue 13) f=6, r=9(full=>r=size-1) 3 14) enqueue(20,4,2) r 20 4 2 5 7 f=6 3 5 7 How to make this If r=size-1 r=0 Else r++ OR r=r+1 mod size 14) dequeue(three times) r 20 4 2 Dequeue => if f=size-1 F=0 Else f++ Or f=(f+1) mod size f 3 × 5 × × 7 14) Suppose our q=3,5,7,20,4,2 then we enqueue(1,8,9,6)=>our q=3,5,7,20,4,2,1,8,9,6 r f 20 4 2 1 8 9 6 3 So, queue is full when: front=rear OR when f= -1 and r=size-1(old case) Before we said f=r =>Empty?? (how to solve) Empty=> f=r= -1 and full=>f=r ≠ -1 5 7 Enqueue in a Circular Queue 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; } Dequeue from 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]; } B.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)) { cout<< “ The memory is full\n”; exit(1); } temp->item = item; temp->next= NULL; if (front) { (rear) -> next= temp;} else front = temp; rear = temp; } Dequeue element dequeue(pnode front) { /* delete an element from the queue */ pnode temp = front; element item; if (IS_EMPTY(front)) { cout<<“The queue is empty\n”; exit(1); } item = temp->item; front = temp->next; free(temp); return item; }

© Copyright 2018