DATA STRUCTURES AND APPLICATIONS (BCS304)
MODULE-II
QUEUES: Queues, Circular Queues, Using Dynamic Arrays, Multiple Stacks and queues.
LINKED LISTS: Singly Linked, Lists and Chains, Representing Chains in C, Linked Stacks and Queues, Polynomials
Text Book: Chapter-3: 3.3, 3.4, 3.7 Chapter-4: 4.1 to 4.4
Queues:
definition
A queue is an ordered collection of homogeneous data elements, in which the first element is inserted from one end called REAR
(also called tail), and the deletion of existing element takes place from the other end called as FRONT (also called head). This makes
queue as FIFO (First in First Out) data structure, which means that element inserted first will also be removed first.
Example
Array Representation
In the following example figure, front = 0 and rear = 5 suppose we want to add another element with value 45, then rear would be
incremented by 1 and the value would be stored at the position pointed by rear.
Queue after insertion of a new element
Here, front = 0 and rear = 6. Every time a new element has to be added, we repeat the same procedure. If we want to delete an element
from the queue, then the value of front will be incremented. Deletions are done from only this end of the queue.
[Link] CSE-DS AMC ENGINEERING COLLEGE Page 1
DATA STRUCTURES AND APPLICATIONS (BCS304)
Queue Abstract Data Type
Queue CreateQ(max-queue-size)::= create
an empty queue whose maximum size is max-queue-size
Boolean IsFullQ(queue, max-queue-size)::=
if (number of elements in queue == max-queue-size)
return TRUE
else return FALSE
Queue AddQ(queue, item)::=
if (IsFullQ(queue))
queue - full
else insert item at rear of queue and return queue
Boolean IsEmptyQ(queue)::=
if {queue == CreateQ(max-queue-size))
return TRUE
else return FALSE
Element DeleteQ(queue)::=
if (IsEmptyQ(queue))
return
else remove and return the item at front of queue.
Queue operation
Insertion
Before inserting an element in a queue, we must check for overflow conditions. An overflow will occur when we try to insert an
element into a queue that is already full. When rear =MAX– 1, where MAX is the size of the queue, we have an overflow condition.
Note that we have written MAX – 1 because the index starts from 0.
1. We first check for the overflow condition.
2. We check if the queue is empty. In case the queue is empty, then both front and rear are set to zero, so that the new
value can be stored at the 0 location. Otherwise, if the queue already has some values, then rear is incremented so
that it points to the next location in the array.
3. The value is stored in the queue at the location pointed by rear.
[Link] CSE-DS AMC ENGINEERING COLLEGE Page 2
DATA STRUCTURES AND APPLICATIONS (BCS304)
Deletion
Before deleting an element from a queue, we must check for underflow conditions. An underflow condition occurs when we try to
delete an element from a queue that is already empty. If front = –1 and rear = –1, it means there is no element in the queue.
Program for Queue implementation using array
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void enQueue(int);
void deQueue();
void display();
int queue[SIZE], front = -1, rear = -1;
void main()
{
int value, choice;
clrscr();
while(1){
printf("\n\n***** MENU *****\n");
printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
enQueue(value);
[Link] CSE-DS AMC ENGINEERING COLLEGE Page 3
DATA STRUCTURES AND APPLICATIONS (BCS304)
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong selection!!! Try again!!!");
}
}
}
void enQueue(int value){
if(rear == SIZE-1)
printf("\nQueue is Full!!! Insertion is not possible!!!");
else{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\nInsertion success!!!");
}
}
void deQueue(){
if(front == rear)
printf("\nQueue is Empty!!! Deletion is not possible!!!");
else{
printf("\nDeleted : %d", queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is Empty!!!");
else{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
[Link] CSE-DS AMC ENGINEERING COLLEGE Page 4
DATA STRUCTURES AND APPLICATIONS (BCS304)
printf("%d\t",queue[i]);
}
}
Circular Queues
Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last
position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.
In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we cannot insert the next element
even if there is a space in front of queue.
Insertion (enqueue):
// Addtion in the Circular Queue
void enqueue (int value)
{
if((front == rear + 1) || (front == 0 && rear == capacity - 1))
printf ("Overflow condition\n");
else
{
if (front == -1)
front = 0;
rear = (rear + 1) % capacity;
queue[rear] = value;
}
}
[Link] CSE-DS AMC ENGINEERING COLLEGE Page 5
DATA STRUCTURES AND APPLICATIONS (BCS304)
Deletion(dequeue):
// Removal from the Circular Queue
int dequeue ()
{
int variable;
if (front == -1)
{
printf ("Underflow condition\n");
return -1;
}
else
{
variable = queue[front];
if (front == rear)
{
front = rear = -1;
}
else
{
front = (front + 1) % capacity;
}
printf ("%d was dequeued from circular queue\n", variable);
return 1;
}
}
Multiple Stacks and queues.
Multi stack
When a stack is created using single array, we cannot able to store large amount of data, thus this problem is rectified using more than
one stack in the same array of sufficient array. This technique is called as Multiple Stack.
Note:
When an array of STACK[n] is used to represent two stacks, say Stack A and Stack B. Then the value of n is such that the combined
size of both the Stack[A] and Stack[B] will never exceed n. Stack[A] will grow from left to right, whereas Stack[B] will grow in
opposite direction i.e.) right to left.
[Link] CSE-DS AMC ENGINEERING COLLEGE Page 6
DATA STRUCTURES AND APPLICATIONS (BCS304)
Multiple Queues
When we implement a queue using an array, the size of the array must be known in advance. If the queue is allocated less space, then
frequent overflow conditions will be encountered. To deal with this problem, the code will have to be modified to reallocate more
space for the array. In case we allocate a large amount of space for the queue, it will result in sheer wastage of the memory. Thus,
there lies a tradeoff between the frequency of overflows and the space allocated. So a better solution to deal with this problem is to
have multiple queues or to have more than one queue in the same array of sufficient size.
In the figure, an array QUEUE[n] is used to represent two queues, QUEUE A and QUEUE B. The value of n is such that
the combined size of both the queues will never exceed n. While operating on these queues, it is important to note one
thing QUEUE A will grow from left to right, whereas QUEUE B will grow from right to left at the same time. Extending
the concept to multiple queues, a queue can also be used to represent n number of queues in the same array That is, if we
have a QUEUE[n], then each QUEUE I will be allocated an equal amount of space bounded by indices b[i] and e[i]. This
is shown in Fig.
[Link] CSE-DS AMC ENGINEERING COLLEGE Page 7