Queues in Computer Science

QUEUE Aqueue is an ordered collection of items. Also, a one-dimension array (linear list) Similar in structure to a stack Data items can be inserted and deleted at different ends FIFO (First In First Out) The items may be deleted at one end (called the Front [F] of the queue). Items may be inserted at the other end (called the Rear [R] of the queue). The figure illustrates a queue containing three elements A, B, and C;

F A B C R When an element has been deleted from the queue, there is only from the front of the queue,Ais removed, and B is now at the front. F B C R When items D and E are inserted , they may be inserted at the rear of the queue. F B C D E R

QUEUE PROBLEM Problem: After a few insert and delete operations, the rear might reach the end of the queue and no more items can be inserted although the items from the front of the queue have been deleted and there is space in the queue. Solution: F A B C D E R

In the figure below, when items F are inserted, they may be inserted at the rear of the queue. Circulation was done when inserted G (at the beginning of the queue), F G A B C D E F R R R R R

QUEUE REPRESENTATION As we now understand that in the queue, we access both ends for different reasons. The following diagram given below tries to explain queue representation as a data structure As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers, and Structures. For the aim of simplicity, we shall implement queues using a one- dimensional array.

THE QUEUE ABSTRACT DATA TYPE Queue is an ADT data structure like stack, except that the first item to be inserted is the first one to be removed. This mechanism is called First-In-First-Out (FIFO). Placing an item in a queue is called insertion or enqueue , which is done at the end of the queue called rear or R . Removing an item from a queue is called deletion or dequeue , which is done at the other end of the queue called front or F . Used extensively in Operating Systems (OS).

THE QUEUE ABSTRACT DATA TYPE Class specification The queue abstract data type (ADT) supports the following Methods: ADT: Queue { Data: a non-zero positive integer number representing MaxSize and an array of object elements representing the QueueArray. Operations: A constructor(queue): initialize the data to some Data object certain value. enqueue (element): Insert the object element at the rear of the queue. Input: Object; Output: None. dequeue(): Remove and return from the queue the object at the front; an error occurs if the queue is empty. Input: None; Output: Object. Notice that, as with the stack pop() operation, the dequeue() operation returns the object that was removed (an alternative to avoid unnecessary copying by defining dequeue() so that no value is returned). Queue -MaxSize:int -QueueArray[]:object -front:int -rear:int +Queue(int) +enqueue (object):void +dequeue():object +Front():object +IsFull():bool +IsEmpty():bool +Size():int

THE QUEUE ABSTRACT DATA TYPE The queue ADT also includes the following supporting member methods: Front(): Return, but do not remove, a reference to the front element in the queue; an error occurs if the queue is empty. Input: None; Output: Object. Size(): Return the number of objects in the queue. Input: None; Output: Integer. peek(): Returns the object at the top of the current queue, without removing it. If the queue is empty this method returns null. Input: None; Output: Object. IsEmpty(): Return a Boolean value indicating if the queue is empty. Input: None; Output: Boolean. IsFull(): Return a Boolean value indicating if the queue is full. Input: None; Output: Boolean. } end ADT Queue

QUEUE EXAMPLE Ex The following table shows a series of queue operations and their effect on an initially empty queue Q of an integer. Queue q=new Queue [6];

Operation Output Front (F) 0 0 0 1 1 2 2 3 3 0 0 0 0 0 0 1 Rear (R) -1 0 1 1 2 2 2 2 2 -1 0 1 1 2 3 3 Queue enqueue(5) enqueue(3) dequeue() enqueue(7) dequeue() Front() dequeue() dequeue() IsEmpty() enqueue(9) enqueue(2) Size() enqueue(3) enqueue(5) dequeue() - - 5 - 3 7 7 (5) (5 | 3) ( | 3) ( | 3 | 7) ( | | 7) ( | | 7) ( | | ) ( ) ( ) (9) (9 | 2) (9 | 2 ) (9 | 2 | 3 ) (9 | 2 | 3 | 5) ( | 2 | 3 | 5) error True - - 2 - - 9

In the queue, we always dequeue (or access) data, pointed by the front pointer (F), and while enqueing (or storing) data in the queue we take the help of the rear pointer (R).

class Queue { // data member or data value private int F, R, MaxSize ; private object[] QueueArray; // Constructer or default Constructer public Queue(int n) { MaxSize = n; QueueArray = new object[MaxSize]; R = -1; F = 0; } }

ALGORITHMSFOR QUEUEPROCEDURES This function helps to see the data at the front of the queue. The algorithm of the peek() function is as follows peek() begin procedure peek return QueueArray[F] end procedure

isfull() As we are using a single dimension array to implement a queue, we just check for the rear pointer (R) to reach MAXSIZE to determine that the queue is full. In case we maintain the queue in a circular linked list, the algorithm will differ. Algorithm of isfull() function; begin procedure isfull if R equals (MAXSIZE-1) return true else return false endif end procedure

isempty() begin procedure isempty if F is greater than R, OR ((F = 0) AND (R = -1)) return true else return false endif end procedure If the value of front F is equal to 0 and R=-1, it tells that the queue is not yet initialized, hence empty.

Enqueue Operation Queues maintain two data pointers, front (F) and rear (R). Therefore, its operations are comparatively more difficult to implement than that of stacks. The following steps should be taken to enqueue (insert) data into a queue Step 1 Check if the queue is full. Step 2 If the queue is full, produce an overflow error and exit. Step 3 If the queue is not full, increment the rear pointer (R) to point to the next empty space. Step 4 Add data element to the queue location, where the rear (R) is pointing. Step 5 return success.

procedure enqueue(data) if QueueArray is full return overflow endif R R + 1 QueueArray [R] data return true end procedure

Dequeue Operation Accessing data from the queue is a process of two tasks access the data where the front (F) is pointing and remove the data after access. The following steps are taken to perform dequeue operation Step 1 Check if the queue is empty. Step 2 If the queue is empty, produce an underflow error and exit. Step 3 If the queue is not empty, access the data were front (F) is pointing. Step 4 Increment front pointer (F) to point to the next available data element. Step 5 Return success.

procedure dequeue if QueueArrayis empty return underflow end if data = QueueArray [F] F F + 1 return true end procedure

IMPLEMENTATION ARRAY-BASED QUEUE To Summarize the discussion of Queues, let us list all the methods we have discussed for implementing queues: 1 The physical model: A linear array with the front always in the first position and all entries moved up the array whenever the front is removed. This is generally a poor method for use in computers, ( O(n)).

Pseudocode dequeue Physical mode c.f. if isEmpty() then Throw a queueEmpty exception else { item QueueArray[0] for (i 0 to (size() -2)) { QueueArray[i] QueueArray[i+1] } R R-1 return item } 1 1 1 n n 1 1 =2n+5 = O(n)

2- A linear array with two indices always increasing. This is a good method if the queue can be emptied all at once. (all methods O(1)) Pseudocode Size() return ( R F + 1) Pseudocode IsEmpty() if (F greater than R ) { F 0; R -1; return true } else return false

Pseudocode Front() if IsEmpty() then Throw a QueueEmpty Exception Return Queue[F] Pseudocode dequeue() if IsEmpty() then Throw a queueEmpty Exception else { item QueueArray [F] F F+1 return item }

Pseudocode IsFull() if ( R equal (Maxsize-1)) return true else return false Pseudocode enqueue(element) if IsFull() then Throw a queueFullException else { R R+1 QueueArray [R] } element

3- A circular array with use a gap cell within the array to check for fullness or emptiness B A F R F A R F D R a b c F=2, R=2 F=3, R=2 F=3, R=1 In figure(a) removing the last element (A), leaves the queue empty (F>R), figure (b). In figure(c) adding an element to the last free slot in the queue leaves the queue full (F>R). The value of the front and rear in the two situations are identical. C

One solution is to use a gap cell within the array to check for fullness or emptiness; Pseudocode Size() return (MaxSize - F + R + 1) mod MaxSize Pseudocode IsEmpty() if (F greater than R ) { F 0 ; R -1 ; return true } else return false

Pseudocode Front() if IsEmpty() then Throw a QueueEmpty Exception Return QueueArray[F] Pseudocode dequeue() if IsEmpty() then Throw a QueueEmpty Exception else { item QueueArray [F] F (F + 1) mod MaxSize return item }

Pseudocode IsFull() if ((R+1)% MaxSize equal F) return true else return false Pseudocode enqueue(element) Circular Queue (gap cell) if IsFull () then Throw a queueFullException else { R (R+1) mod MaxSize QueueArray [R] } item

EXAMPLE Ex1: Consider the following operations on a circular queue data structure that stores integer values. Queue Q1=new Queue [10]; for (int i=0; i< 7 ; i++) Q1.enqueue (i) ; for (int i=1; i< 5 ; i++) Q1.enqueue(Q1.dequeue ()) ; What queue will look like after the code above executes( what position of rear and front)?

Sol: 0 0 0 3 1 1 1 2 2 2 3 3 3 4 4 5 5 6 6 7 0 8 1 9 2 F R R R F F F F F F F F R R R R R R R R R R R R R R R R R R R=-1

EXAMPLE Ex: Consider the following operations on a circular queue data structure that stores integer values. Queue q=new Queue(9); q.enqueue(6); q.enqueue(1); q.enqueue(8); q.enqueue(q.dequeue()); q.enqueue(q.dequeue()); q.enqueue(5); q.enqueue(q.dequeue()); q.enqueue(q.dequeue());q.enqueue(3); what q will look like after the code above executes (what position of rear and front)? Sol: q.enqueue(9); 0 3 R 1 2 3 4 1 F 5 5 6 9 7 8 8 6 q

The table show the running times of methods in realization of a queue by an array Method Time O(1) O(1) O(1) O(1) O(1) Size isEmpty Front Enqueue Dequeue

Stack Queue EXERCISES The stack is based on LIFO(Last In First Out) principle Insertion Operation is called Push Operation Deletion Operation is called Pop Operation The queue is based on FIFO(First In First Out) principle. Insertion Operation is called Enqueue Operation Deletion Operation is called Dequeue Operation Enqueue and Dequeue Operation takes place from a different end of the queue The insertion end is called Rear End and the deletion end is called the Front End. Complex implementation in comparison to stack Two pointers are used to perform operations Empty condition is checked using Push and Pop Operation takes place from one end of the stack The most accessible element is called Top and the least accessible is called the Bottom of the stack Simple Implementation Only one pointer is used for performing operations Empty condition is checked using Top=-1 Front=0 || Rear=-1 Full condition is checked using Full condition is checked using Top=Max-1 Rear=Max-1 There are three types of variants i.e., circular queue, double-ended queue, and priority queue Can be considered a horizontal collection of visual Used to solve the problem of having sequential processing There are no variants available for stack Can be considered a vertical collection of visual Used to solve the recursive type problems

EXERCISES Q1/ Write method to print Queue? Q2/ Write method to print Circular Queue? Q3/ Consider the following operations on a circular queue data structure that stores integer values? Queue q=new Queue [10]; q.enqueue(6); q.enqueue(1); q.enqueue(q.dequeue()); q.enqueue(8); q.enqueue(2); q.enqueue(5); q.enqueue(9); q.enqueue(q.dequeue()); q.enqueue(q.dequeue()); what q will look like after the code above executes?

Consider the following operations on a circular queue data structure that stores integer values? Queue q=new Queue [6]; q.enqueue(9); q.enqueue(3); q.enqueue(5); q.enqueue(q.dequeue()); q.enqueue(4); q.enqueue(2); q.enqueue(q.dequeue()); q.enqueue(q.dequeue()); q.enqueue(8); what q will look like after the code above executes?

Q5/ Describe the output for the following sequence of queue operation. Queue q=new Queue [7]; q.enqueue(5); q.enqueue(3); q.dequeue() q.enqueue(2); q.enqueue(8); q.dequeue(); q.dequeue(); q.enqueue(7);

Q6/ Describe the output for the following sequence of circular queue operation. Queue [] q=new Queue [6];; q.enqueue(15); q.enqueue(13); q.dequeue() q.enqueue(21); q.enqueue(8); q.dequeue(); q.dequeue(); q.enqueue(7); q.enqueue(9); q.enqueue(1); q.enqueue(8);