DATA STRUCTURE

INTRODUCTION TO QUEUE [12 Marks]

INTRODUCTION TO QUEUE
 Introduction
o Queues as an abstract data type
o Representation of a Queue as an array
 Types of Queue
o Circular Queue
o Double Ended Queue
o Priority Queue
o Dequeues
 Applications of Queue

Introduction To Queue
Queue is a linear data structure used to represent a linear list. Queue is a linear list of elements in which
deletion of an element can take place only at one end, called as the FRONT and insertion can take place
only at the other end, called the REAR.
The first element in a queue will be the first one to be removed from the list. Therefore, queues are also called
FIFO (First In First Out) lists.
Defination
Queue is a linear data structure which follow First in First out (FIFO) princliple, where elements are added at
REAR end and deleted from FRONT end.
ABSTRACT DATA TYPE .
The definition of an abstract data type in data structure must have following properties
 There should be a particular way in which elements are related to each other.
 A statement of the operations that can be performed on elements of the ADT should be specified.
QUEUE AS AN ABSTRACT DATA TYPE .
A queue of elements of type A is a finite sequence of elements. Thus, a queue, as an ADT, can be defined
with following properties:
 Initialize a queue to be empty.
 Determine if a queue is empty or not.
 Determine if a queue is full or not.
 Insert a new element after the last element in a queue, if it is not full. [Overflow]
 Retrieve the element of FRONT position, from a queue, if it is not empty. [Underflow]
 Delete the FRONT element from the queue, if it is not empty.
Programming Point of view stack as ADT has define as follow.
 Array implementation of QUEUE, which contains integer type of elements
Int QUEUE[10]; // Here QUEUE is an array of Integer type with SIZE 10.
Int FRONT=-1; // FRONT is variable (initially NULL) used to show the position of element to delete.
Int REA R=-1; // REAR is variable (initially NULL) used to show the position of element to insert.
Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 1 of 11
 Int MAX=10; //MAX is a variable shows the maximum size of queue.
Operations…..
void init(); // This procedure initialise the QUEUE to empty state
(FRONT=-1, REAR=-1,MAX=10).
void insert(int item); // This procedure add new element into the QUEUE at REAR position.
void remove( ); // This procedure remove FRONT element from the QUEUE.
int peek( ); // This procedure returns TOP element from the STACK for processing.
int isEmpty(); // This function return 1(TRUE) if QUEUE is empty, otherwise 0.
int isFull(); // This function return 1(TRUE) if QUEUE is full, otherwise 0.
void show(); // This function show elements of QUEUE as they are inserted.

 Stack may formally also define as follow

struct QUEUE
Here struct QUEUE is define with 3 members
{  DATA (Integer Array), FRONT (To show the position of
Int DATA[10]; delete) , REAR (To show the position of insert) and MAX
(Size of Queue).
Int FRONT;  The name of object is queue (small letters)
Int REAR;  We can access members through pointer object through
functions (Call By Referance)
Int MAX;
}queue;
Operations…..
void init(struct QUEUE &pointerQueue);
// This procedure initialise the QUEUE to empty state as follow
void insert(struct QUEUE &pointerQueue ,int item);
// This procedure add new element into the FRONT of the QUEUE.
void remove(struct QUEUE &pointerQueue);
// This procedure remove the TOP element from the STACK.
int isEmpty(struct QUEUE &pointerQueue);
// This function return 1(TRUE) if QUEUE is empty, otherwise 0.
int isFull(struct QUEUE &pointerQueue);
// This function return 1(TRUE) if QUEUE is full, otherwise 0.
void show(struct QUEUE &pointerQueue);
// This function show elements of QUEUE as they are inserted.

PREMITIVE OPERATIONS ON STACK.

 Creation : To Initialise queue as an empty queue.

 Insert : Adds a given element to the REAR end of the queue leaving previous items below.
 Remove : Removes and returns the current node of the queue (of FRONT position).
 Traversing : To Visit each element of the queue.
 Display : To Read each element of the queue and display it.

Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 2 of 11

SOME IMPORTANT POINTS ABOUT QUEUE.
 MAX : Represents the size Of Queue.
 QUEUE : Is the Array to Represent Queue.
 FRONT : A Queue is an ordered collection of item from which the elements deleted at
one end called as FRONT end.
 REAR : A Queue is an ordered collection of item from which the elements inserted at
other end called as REAR end.

Importance of REAR Pointer in QUEUE.

 REAR is a pointer varibale which points to the last element of queue.
 Initially REAR is set to NULL (-1), indicates queue is empty.
 REAR increase by one (moves forward) after every insert operation.
 REAR helps to identify “Queue Overflow” conditions.
 REAR is -1 when queue is empty.
 REAR is set to MAX-1, when queue is full (normal queue).
 When we add first element in queue then FRONT is also set on first position.
 Extra Points about REAR Pointer in Circular QUEUE.
 If REAR is on MAX-1 position and there is a space at first position. In that case REAR is set to 0.
 In case of “Overflow Condition of Circular Queue”, either REAR = MAX-1 or REAR = FRONT-1.
 Circular queue refers to the first element after the last element of an array Queue.

Importance of FRONT Pointer in QUEUE.

 FRONT is a pointer varibale which points to the existing first element of queue.
 Initially FRONT is set to NULL (-1), indicates queue is empty.
 FRONT increase by one (moves forward) after every delete operation.
 FRONT helps to identify “Queue Underflow” conditions.
 FRONT is -1 when queue is empty.
 When we delete last element (only element of queue) then REAR is also set to -1.
 Extra Points about REAR Pointer in Circular QUEUE.
 If FRONT is on MAX-1 position and we delete last element and there is a element at first position. In
that case FRONT is set to 0.

Common points of FRONT and REAR Pointer in QUEUE.

 When FRONT and REAR both are -1, indicates that Queue is Empty.
 When FRONT and REAR are on same position in Queue, then it indicates that Queue has only one
element.
 Both pointers FRONT and REAR moves forward, either we insert or delete the element.

STATES OF THE QUEUE.

 QUEUE OVERFLOW :

Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 3 of 11

 o While inserting a new element in queu, Insert operation is called.
o Overflow is a state when queue has no space for new element and Insert operation is called
then this situation is “Queue is Overflow or Full”.
o When REAR=MAX-1, indicates Overflow (In Normal Queue)
o When (REAR=MAX-1) || (REAR=FRONT-1), indicates Overflow (In Circular Queue)
 QUEUE UNDERFLOW :
o While deleting an existing element from stack pop operation is called.
o Underflow is a state when queue has no elements and Remove operation is called then this
situation is “Queue is Underflow or Empty”.
o When FRONT= -1, indicates Underflow.
 Note that draw the appropriate figure of Overflow and Underflow.

REPRESENTATION OF QUEUE.
1. Queue, being the linear data structure, which follow the First in First out (FIFO) principle.
2. In Queue elements are added at REAR end and deleted from only FRONT end of Queue.
3. A Queue can be implemented by using arrays, structure, pointer and linked lists.
4. Queue can either be a fixed size (Using Array) or it may have a sense of dynamic resizing (Using
Linked List).

REPRESENTED OF A QUEUE AS AN ARRAY….

 Here we are going to implement queue using arrays.
 Some points about implementation of queue using array.
 Array is a data structure that stores a fixed number of elements (size).
 The size of Array should be fixed prior to using it so we declare an array with a maximum size.
 But the size of Queue keeps on changing as the elements are Insert or Remove.

The Following Figure shows the representation of a queue as an array.

Q[0] Q[1] Q[2] Q[3] Q[4] Q[5] Q[6] Q[7] Q[8] Q[9]

10 20 30 40 50 60 70 80 90 100

Front = 0 Rear = 9

INSERTION ALGORITHM FOR QUEUE :

Step 1: [ check for Queue Full / Overflow Condition ]
If ( Rear >= (MAX -1)) then
Print (“Queue Is Full / Overflow Condition” )
Return
Step 2: [Increment Rear end Of Queue ]
Rear = Rear +1
Step 3: [ Insert element at new Rear end of Queue ]

Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 4 of 11

 Queue [Rear] = element
Step 4: [ If it is First Element The Set Front = 0 ]
If ( Front == -1 ) then
Set Front := 0
Step 5: [ Finished ]
Return

DELETION ALGORITHM FOR QUEUE :

Step 1 : [Check for Empty Queue]
If (Front = = -1 ) then
Print (Queue is Empty, Underflow Condition )
Return
Step2: [Assign element from Queue]
Element=Queue [Front]
Step 3 [Increment Front of queue by one]
Front = Front + 1
Step4: [end]
Return

REPRESENTATION OF A QUEUE AS AN LINKED LIST.

 Queue can also be represented using a single linked list.
 The linked list representation of a queue dose not have any restrictions on the number of elements it
can hold.
 Each node of the list contains data and a pointer to the next node.
 The elements in a linked list are allocated dynamically,
 Hence it can grow as an long as there is sufficient memory available for dynamic allocation.
 The structure define to represent the queue is as follow.
struct Node
{
int data;
struct Node *LINK;
}

Disadvantage of Linear Queue.

Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 5 of 11

  On deletion of an element from existing queue, front pointer is shifted to next position. This results into
virtual deletion of an element. By doing so memory space which was occupied by deleted element is
wasted and hence inefficient memory utilization is occur.
Overcome disadvantage of linear queue:
 To overcome disadvantage of linear queue, circular queue is use. In a standard queue data structure
re-buffering problem occurs for each dequeue operation. To solve this problem by joining the front and
rear end of a queue to make the queue as a circular queue Circular queue is a linear data structure. It
follows FIFO principle.
 In circular queue the last node is connected back to the first node to make a circle. Circular linked list
fallow the First In First Out principle elements are added at the rear end and the elements are deleted
at front end of the queue Both the front and the rear pointers points to the beginning of the array. It is
also called as “Ring buffer”. Items can inserted and deleted from a queue in O(1) time.

CIRCULAR QUEUES.
Defination
“A queue, in which the last node is connected back to the first node to form a cycle, is called as circular queue”.
Explanation:
 Circular queue are the queues implemented in circular form rather than in a straight line.
 Circular queues overcome the problem of unutilized space in linear queue implemented as an array.
 The main disadvantage of linear queue using array is that when elements are deleted from the queue,
new elements cannot be added in their place in the queue, i.e. the position cannot be reused.
 After REAR reaches the last position, i.e. MAX-1 in order to reuse the vacant positions, we can bring
rear back to the 0th position, if it is empty, and continue incrementing REAR in same manner as earlier.
Thus rear will have to be incremented circularly.
 Rear can be incremented circularly by the following code.
If ((REAR == MAX-1) and (FRONT! =0)
REAR =0;
Else
Rear= rear +1;
 For deletion, front will also have to be incremented circularly. (In case FRONT != REAR)
If ((FRONT == MAX-1)
FRONT =0;
Else
FRONT= FRONT +1;
 Various methods to check queue is Full or not.
o Use a counter to keep track of the number of elements in the queue. If this counter reaches to
MAX the queue is full.
o If FRONT==0 and REAR=MAX-1 then, we will say that QUEUEis FULL. (Normal Queue)
o If FRONT== REAR+1 then, we will say that QUEUEis FULL. (Circular Queue)
o By checking (REAR+1) % MAX== FRONT.
 Following figure explain circular queue in detail
Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 6 of 11
Representation No 1 …..

Representation No 2 …..

 Fig. No 1: Observe that Empty Queue, and FRONT and REAR both are -1.
 Fig. No 2: Observe queue with 4 elements, where FRONT is set to 0th position and REAR is set to 3rd
position.
 Fig. No. 3: Observe queue is full, because FRONT is 0 and REAR is on last position. If you look in
circular manner REAR is just next to FRONT.
 Now Delete Two Elements and Observe from Fig. No 4. that the value of REAR becomes MAX -1 but
still Queue is Not Full.
 Now Again Delete Three Elements and Observe from Fig. No 5.
 Now Add Two More Elements 1000 & 2000 and Observe Fig. No 6.
 Now Delete All 5 Elements and Observe Fig. No 7 and observe that, Front becomes Rear + 1, so it is
also Empty State for Circular Queue.

 Suppose an array QUEUE of MAX element is used to implement a circular queue.

Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 7 of 11

  If we go on adding elements to the queue we may reach Queue [Max -1] Fig. No. 3. We cannot add
any more element to the circular queue when QUEUE is full.
 If some element in the queue have been deleted then there might be empty slots at the beginning of
the queue Fig. No. 4. In such case these slots would be filled by new element added to the queue
Fig. No 6.
 In short, just because we have reached the end of the array, the queue would not be reported as full.
The queue would be reported full only when all the slots in the array are occupied.

INSERTION ALGORITHM FOR CIRCULAR QUEUE:

Step 1: [check for Queue Full / Overflow Condition]
If ((Rear = = MAX -1 && Front = = 0) || (Rear + 1 = = Front)) then
Print (“Queue Is Full / Overflow Condition”)
Return
Step 2: [Set the Position of Rear]
If (Rear = MAX – 1)
Set Rear: = 0
else
Set Rear: = Rear +1
Step 3: [Insert element at new Rear end of Queue]
Queue [Rear] = element
Step 4: [If it is First Element the Set Front = 0]
If (Front == -1) then
Set Front: = 0
Step 5: [Finished]
Return

DELETION ALGORITHM FOR CIRCULAR QUEUE:

Step 1: [Check for Empty Queue]
If (Front = = -1) then
Print (“Queue is Empty, Underflow Condition”)
Return
Step 2: [Assign element from Queue]
Element=Queue [Front]

Step 3: [Set the Value of Front in Circular Queue]

if (Front == Rear)
Set Front: = -1
Set Rear: = -1;
Else
If (Front = = MAX -1)
Front = 0

Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 8 of 11

 else
Front = Front + 1
[End Of Inner If Structure]
[End Of Outer If Structure]
Step4: [End]
Return

PRIORITY QUEUES.
 A priority queue is a collection of elements.
 A priority queue is a queue in which the intrinsic ordering among the elements decides the result of its
basic operations.
 The ordering among the elements decides the manner in which Add and Delete operations will be
performed.
The priority queue has following properties.
 Each element is assigning a priority number.
 An element of higher priority is processed before any elements of lower priority.
 An elements with the same priority are processed according to the order in which they are added to
the queue.

REPRESENTATION OF PRIORITY QUEUE.

Array Representation
Array element of priority queue has a struct with data, priority and order.
The structure defination is as follow.
struct Pqueue
{
Int data;
Int prioritynumber;
Int order;
}PriQueue[5];

The diagram of priority queue is as follow.

Link Representation
We can represent a priority queue in memory dynamically by means of One Way List:
Each node in the list contain three items of information –
 An information field INFO,
 priority number PRNO
 And the link NEXT.

Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 9 of 11

Node A will precede Node B in the list when A has higher priority than B or when both the Nodes have same
priority but A was added to the list before B. This means that order in one way list correspond to the order of
priority queue.

Types of Priority Queue.

1. Ascending Priority Queue. This is a priority queue in which elelments can be inserted in any order
i.e. arbitarily, but only the smallest element can be removed. This means that the elements having
smallest value int the queue has heighest priority.
2. Descending Priority Queue. This is a priority queue in which elelments can be inserted in any order
i.e. arbitarily, but only the largest element can be removed. This means that the elements having largest
value in the queue has heighest priority.
Advantages of priority queue.
 Preferances to the heigher priority process are added at the beginning.
 Keep the list sorted in increasing order.
 In priority queue we are able to insert items and remove items to any positions based on priority.
Example of priority queue.
 Priority queue can be used in time sharing system: program of high priority are processed first, and
program with same priority from a standard queue.
 Priority queue are used is in operating systems. The operating system has to handle a large number
of jobs. These jobs have to be properly scheduled. The operating system assigns priorities to each type
of job. The jobs are placed in a queue and the job with the highest priority will be executed first.
Double Ended Queue
 A double-ended queue or dequeue is an abstract data structure that implements a queue for which
elements can only be added to or removed from the front (head) or back (tail).
 It is also often called a head-tail linked list.
 Dequeue is a special type of data structure in which insertions and deletions will be done either at the
front end or at the rear end of the queue.
 The operations that can be performed on dequeues are
a. Insert an item from front end
b. Insert an item from rear end
c. Delete an item from front end
d. Delete an item from rear end
e. Display the contents of queue

Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 10 of 11

APPLICATION OF QUEUE’S.
 The common examples for queues can be a queue of people waiting to purchase tickets, where the
first person in the queue is the first one to be served.
Many examples of queues can be noticed within a computer system –
 There may be queues of tasks waiting for the line printer,
 For access to disk storage or even in time sharing system for use of the CPU.
 Within a single program there may be multiple requests to be kept in queue, or one task may create
other tasks which must be executed in turn by keeping them in a queue.
 Round Robin Technique for processor scheduling is implemented using Queue.
 Printer server routines are designed using queues.

Subject: Data Structure (Queue) Print Date:14/Oct/2019 Page 11 of 11