Queues ADT
Queues ADT
Queues ADT
Jayapriya K N
AP/CSE
Queue
What isADT
a Queue?
Queue is a linear data structure in which the insertion and
deletion operations are performed at two different ends.
In a queue data structure, adding and removing elements
are performed at two different positions.
The insertion is performed at one end and deletion is
performed at another end.
In a queue data structure, the insertion operation is
performed at a position which is known as 'rear' and the
deletion operation is performed at a position which is
known as 'front'.
In queue data structure, the insertion and deletion
operations are performed based on FIFO (First In First
Out) principle.
Definition
In a queue data structure, the insertion operation is
performed using a function called "enQueue()" and
deletion operation is performed using a function
called "deQueue()".
Before we implement actual operations, first follow the below steps to create
an empty queue.
Step 1 - Include all the header files which are used in the program and
define a constant 'SIZE' with specific value.
Step 2 - Declare all the user defined functions which are used in queue
implementation.
Step 3 - Create a one dimensional array with above defined SIZE (int
queue[SIZE])
Step 4 - Define two integer variables 'front' and 'rear' and initialize both
with '-1'. (int front = -1, rear = -1)
Step 5 - Then implement main method by displaying menu of operations list
and make suitable function calls to perform operation selected by the user on
queue.
deQueue() - Deleting a value from the Queue
The major problem with the queue implemented using an array is, It
will work for an only fixed number of data values. That means, the
amount of data must be specified at the beginning itself.
Queue using an array is not suitable when we don't know the size of
data which we are going to use.
A queue data structure can be implemented using a linked list data
structure.
The queue which is implemented using a linked list can work for an
unlimited number of values.
That means, queue using linked list can work for the variable size of
data (No need to fix the size at the beginning of the
implementation). The Queue implemented using linked list can
organize as many data values as we want.
example
In linked list implementation of a queue, the last
inserted node is always pointed by 'rear' and the first
node is always pointed by 'front'.
Example
In above example, the last inserted node is 50 and it is
pointed by 'rear' and the first inserted node is 10 and it
is pointed by 'front'. The order of elements inserted is
10, 15, 22 and 50.
example
Operations
We can use the following steps to delete a node from the
queue...
Step 1 - Check whether queue is Empty (front ==
NULL).
Step 2 - If it is Empty, then display "Queue is Empty!!!
Deletion is not possible!!!" and terminate from the
function
Step 3 - If it is Not Empty then, define a Node pointer
'temp' and set it to 'front'.
Step 4 - Then set 'front = front → next' and delete
'temp' (free(temp)).
display() - Displaying the elements of Queue
We can use the following steps to display the elements of a circular queue...
Step 1 - Check whether queue is EMPTY. (front == -1)
Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the
function.
Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set
'i = front'.
Step 4 - Check whether 'front <= rear', if it is TRUE, then display 'queue[i]'
value and increment 'i' value by one (i++). Repeat the same until 'i <= rear'
becomes FALSE.
Step 5 - If 'front <= rear' is FALSE, then display 'queue[i]' value and
increment 'i' value by one (i++). Repeat the same until'i <= SIZE - 1'
becomes FALSE.
Step 6 - Set i to 0.
Step 7 - Again display 'cQueue[i]' value and increment i value by one (i++).
Repeat the same until 'i <= rear' becomes FALSE.
Double Ended Queue Datastructure