Class notes BCA 402

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