MODULE-1

DATA
STRUCTURES
MODULE-I:

Introduction to Data Structures, abstract data types, Linear list – singly linked list implementation, insertion,
deletion and searching operations on linear list, Stacks-Operations, array and linked representations of stacks,
stack applications, Queues-operations, array and linked representations.

Introduction:
. Data structure is a collection of organized data in the memory locations .
Data structure can be classified as
. Linear Data structure : one element is connected to another element in linear form .
. In the linear data structure values are arranged in a linear fashion .An array,linked list ,stacks
and queues are Examples of linear data structure.

Types of Data Structures:

There are two types of data structure available for the programming purpose:

o Primitive data structure

o Non-primitive data structure

1
Primitive data structure

Primitive data structure is a data structure that can hold a single value in a specific location whereas
the non-linear data structure can hold multiple values either in a contiguous location or random
locations

The examples of primitive data structure are float, character, integer and pointer. The value to the
primitive data structure is provided by the programmer. The following are the four primitive data
structures:

o Integer: The integer data type contains the numeric values. It contains the whole numbers
that can be either negative or positive. When the range of integer data type is not large
enough then in that case, we can use long.
o Float: The float is a data type that can hold decimal values. When the precision of decimal
value increases then the Double data type is used.
o Boolean: It is a data type that can hold either a True or a False value. It is mainly used for
checking the condition.
o Character: It is a data type that can hold a single character value both uppercase and
lowercase such as 'A' or 'a'.

Non-primitive data structure

The non-primitive data structure is a kind of data structure that can hold multiple values
either in a contiguous or random location. The non-primitive data types are defined by the
programmer. The non-primitive data structure is further classified into two categories, i.e.,
linear and non-linear data structure.

Linear Data Structures:

A data structure is called linear if all of its elements are arranged in the linear order. In
linear data structures, the elements are stored in non-hierarchical way where each element has
the successors and predecessors except the first and last element.

Types of Linear Data Structures are given below:

Arrays: An array is a collection of similar type of data items and each data item is called an
element of the array. The data type of the element may be any valid data type like char, int,
2
float or double.

o The elements of array share the same variable name but each one carries a different index
number known as subscript. The array can be one dimensional, two dimensional or
multidimensional.
o The individual elements of the array age are:
o age[0], age[1], age[2], age[3], age[98], age[99].

Linked List: Linked list is a linear data structure which is used to maintain a list in the
memory. It can be seen as the collection of nodes stored at non-contiguous memory locations.
Each node of the list contains a pointer to its adjacent node.

Stack: Stack is a linear list in which insertion and deletions are allowed only at one end, called
top.

o A stack is an abstract data type (ADT), can be implemented in most of the programming
languages. It is named as stack because it behaves like a real-world stack, for example: -
piles of plates or deck of cards etc.

Queue: Queue is a linear list in which elements can be inserted only at one end
called rear and deleted only at the other end called front.

o It is an abstract data structure, similar to stack. Queue is opened at both end therefore it
3
follows First-In-First-Out (FIFO) methodology for storing the data items.

Non Linear Data Structures: A non-linear data structure is another important type in which
data elements are not arranged sequentially .mainly data elements arranged in random order.
. nonlinear data structures one element is connected multiple elements.

Types of Non Linear Data Structures are given below:

Trees: A tree is a non-linear abstract data type with a hierarchy-based structure. It consists of nodes that are
connected via links. The tree data structure stems from a single node called a root node and has subtrees connected to
the root.

Graphs: A graph is a non-linear kind of data structure made up of nodes or vertices and edges. The
edges connect any two nodes in the graph, and the nodes are also known as vertices.

4
In the above graph,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

. if there is no edge between two nodes the presence value 0

. if there is an edge between two nodes the presence value 1

. Abstract Data Types:

An ADT is a theoretical construct that consist of data as well as the operations to be performed
on data to implementation.
. data
. operations –insertion,deletion and list
. implementation
. Errors
ADT examples are sack,queues and linked list
. Abstract data types can be classified as

1. List ADT: Lists are linear data structures stored in a non-continuous manner the list is made
up of a series of connected nodes that are randomly stored in the memory.
. Here each node consists of two parts the first part is the data and the second part contains the
pointer to the address of the next node.
The List ADT Functions is given below:
• get() – Return an element from the list at any given position.
• insert() – Insert an element at any position of the list.
• remove() – Remove the first occurrence of any element from a non-empty list.
• removeAt() – Remove the element at a specified location from a non-empty list.
• replace() – Replace an element at any position by another element.
• size() – Return the number of elements in the list.

5
• isEmpty() – Return true if the list is empty, otherwise return false.
• isFull() – Return true if the list is full, otherwise return false.

2. Stack ADT: A stack is an ordered list and which elements are inserted and deleted at only one
end called TOP of the stack.
. stack is a LIFO Technique
. The stack ADT operations as follows
• push() – Insert an element at one end of the stack called top.
• pop() – Remove and return the element at the top of the stack, if it is not empty.

• peek() – Return the element at the top of the stack without removing it, if the stack is
notempty.
• size() – Return the number of elements in the stack.
• isEmpty() – Return true if the stack is empty, otherwise return false.
• isFull() – Return true if the stack is full, otherwise return false.

3. Queue ADT: A queue is an ordered list in which insertion is done at one end called REAR and
deletion at another end called FRONT.
. The first inserted element is available first for the operations to be performed and is the first
one to be deleted.
. Hence it is known as first in first out (FIFO)
The queue ADT operations as follows
• enqueue() – Insert an element at the end of the queue.

• dequeue() – Remove and return the first element of the queue, if the queue is not empty.
• peek() – Return the element of the queue without removing it, if the queue is not empty.
• size() – Return the number of elements in the queue.
• isEmpty() – Return true if the queue is empty, otherwise return false.
• isFull() – Return true if the queue is full, otherwise return false.

Linked List: An element in a linked list is a specially termed node . A node consist of two
fields data and link(address).
. A linked list is an ordered collection of finite, homogeneous data elements called nodes .where
the linear order is maintained by means of links or pointers.

6
. single linked list: in a single linked list each node contains only one link which points to the
subsequent node in the list.

. one way chain or singly linked list can be traversed only one direction.

Uses of Linked List

o The list is not required to be contiguously present in the memory.

o list size is limited to the memory size and doesn't need to be declared in advance.
o Empty node can not be present in the linked list.
o We can store values of primitive types or objects in the singly linked list.

Node Creation:

struct node

{
int data;
struct node *next;
};

Advantages :They are dynamic in nature which allocates the memory when required.
. insertion and deletion can be easily implemented.
. stacks and queues can be easily executed .
. it reduces the access time.

Disadvantages : The memory is wasted as pointers required extra memory for storage.
. Each node has to access sequentially.
. Reverse traversing is difficult.
Applications of linked list : Linked list are used to implement stack,queue,graph etc.
7
. linked list let you insert element at the beginning and end of the list.
. in linked list we do not need to know the size in advance .

Singly Linked List operations:

There are various operations which can be performed on singly linked list. A list of all such
operations is given below.

Insertion
.The insertion into a singly linked list can be performed at different positions. Based on
theposition of the new node being inserted, the insertion is categorized into the following
categories

1. insertion at beginning
2.insertion at end of the list
3.insertion after specified node

.
insertion at beginning of the List: To insert a new element at beginning position and ptr node
connected to next node and last node it indicates NULL.

Algorithm:

o Step 1: IF PTR = NULL

WriteOVERFLOW
GotoStep7
[END OF IF]

o Step 2: SET NEW_NODE = PTR

o Step 3: SET PTR = PTR → NEXT
o Step 4: SET NEW_NODE → DATA = VAL
o Step 5: SET NEW_NODE → NEXT = HEAD
o Step 6: SET HEAD = NEW_NODE
o Step 7: EXIT

8
Inserting At End of the List : To insert element in last node of the list the head previous last nodes link field
which was NULL.

Algorithm:
o Step1: IFPTR=NULL

WriteOVERFLO
WGoto Step10

o Step 2: SET NEW_NODE = PTR

o Step 3: SET PTR = PTR - > NEXT
o Step 4: SET NEW_NODE - > DATA = VAL
o Step 5: SET NEW_NODE - > NEXT = NULL
o Step 6: SET PTR = HEAD
o Step 7: Repeat Step 8 while PTR - > NEXT != NULL
o Step8: SETPTR=PTR-
>NEXT[END OF LOOP]
o Step 9: SET PTR - > NEXT = NEW_NODE
o Step 10: EXIT

9
Inserting After specified node : In order to insert an element after the specified number of nodes
in to the linked list we need to skip the desired number of elements in the list to move the pointer
at the position after which the node will be inserted .

Algorithm:
o STEP 1: IF PTR = NULL
WRITEOVERFLO
WGOTOSTEP12
END OF IF

o STEP 2: SET NEW_NODE = PTR

o STEP 3: NEW_NODE → DATA = VAL
o STEP 4: SET TEMP = HEAD
o STEP 5: SET I = 0
o STEP 6: REPEAT STEP 5 AND 6 UNTIL I
o STEP 7: TEMP = TEMP → NEXT
10
o STEP 8: IF TEMP = NULL

WRITE"DESIRED NODE NOT

PRESENT"GOTO STEP 12
END OF IF
END OF
LOOP

o STEP 9: PTR → NEXT = TEMP → NEXT

o STEP 10: TEMP → NEXT = PTR
o STEP 11: SET PTR = NEW_NODE
o STEP 12: EXIT

Deletion : The deletion operation is used to delete a node from the list and it can be performed at
three different locations
. deletion of the first node
. deletion of the last node
. deletion at the specified position

. Deletion of the first node : Deleting a node from the beginning of the list is the simplest operation of
all.since the first node of the list is to be deleted therefore we just need to make the head ,point to the
next of the head. Now free the pointer ptr which was pointing to the head node of the list.

Algorithm:

Step 1: IF HEAD = NULL

WriteUNDERFLOWGotoStep 5
[END OF IF]

Step 2: SET PTR = HEAD

Step 3: SET HEAD = HEAD -> NEXT

Step 4: FREE PTR

Step 5: EXIT

11
2. Deletion of the Last node : There are two scenarios in which a node is deleted from the end of the
linked list
. There is only one node in the list and that needs to be deleted.
. There are more than one node in the list and the last node of the list will be deleted.

Algorithm:
o Step 1: IF HEAD = NULL

WriteUNDERFLOW
GotoStep8
[END OF IF]

o Step 2: SET PTR = HEAD

o Step 3: Repeat Steps 4 and 5 while PTR -> NEXT!= NULL
o Step 4: SET PREPTR = PTR
o Step 5: SET PTR = PTR -> NEXT

[END OF LOOP]

o Step 6: SET PREPTR -> NEXT = NULL

o Step 7: FREE PTR
o Step 8: EXIT

3.Deletion at the specified position :To delete a node from the singly linked list before the
specified position in a singly linked list.

12
Algorithm :

STEP 1: IF HEAD = NULL

WRITEUNDERFLOW
GOTOSTEP10
END OF IF

STEP 2: SET TEMP = HEAD

STEP 3: SET I = 0

STEP 4: REPEAT STEP 5 TO 8 UNTIL I<loc< li=""></loc<>

STEP 5: TEMP1 = TEMP

STEP 6: TEMP = TEMP → NEXT

STEP 7: IF TEMP = NULL

WRITE"DESIREDNODENOTPRESENT"
GOTOSTEP11
END OF IF

STEP 8: I = I+1

END OF LOOP

STEP 9: TEMP1 → NEXT = TEMP → NEXT

STEP 10: FREE TEMP

STEP 11: Exit

Searching in singly linked list : Searching is performed in order to find the location of a particular
element in the list .searching any element in the list needs traversing through the list and make the
comparison of every element of the list with the specified element.

13
. if the element is matched with any of the list element then the location of the element is returned from
the function.

Algorithm:

o Step 1: SET PTR = HEAD

o Step 2: Set I = 0
o STEP 3: IF PTR = NULL

WRITE"EMPTYLIST"
GOTOSTEP8
END OF IF

o STEP 4: REPEAT STEP 5 TO 7 UNTIL PTR != NULL

o STEP 5: if ptr → data = item

Writei+1
End of IF

o STEP 6: I = I + 1
o STEP 7: PTR = PTR → NEXT

[END OF LOOP]

o STEP 8: EXIT

Traversing in singly linked list : Traversing is the most common operation that is performed in almost
every scenario of singly linked list .Traversing means visiting each node of the list once in order to
perform some operation on that .

Algorithm:

STEP 1: SET PTR = HEAD

STEP 2: IF PTR = NULL

WRITE"EMPTYLIST"
GOTOSTEP6
STEP 3: REPEAT STEP 5 AND 6 UNTIL PTR != NULL

STEP 4: PRINT PTR→ DATA

STEP 5: PTR = PTR → NEXT

STEP 6: EXIT

Write a c program to singly linked list implementation and operations

14
a)creation b)insertion c)deletion d)Traversal

#include<stdio.h>

#include<stdlib.h>

structnode{
int data;
structnode*next;
}*head=NULL;

intcount()
{
structnode*temp;
int i=1;
temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
i++;
}
return(i);
}

structnode*create(int value)
{
structnode*temp;
temp=(structnode*)malloc(sizeof(structnode));
temp->data=value;
temp->next=NULL;
return temp;
}
voidinsert_begin(int value)
{
structnode*newnode;
newnode=create(value);
if(head==NULL)
{
head=newnode;
}
else
{
newnode->next=head;
head=newnode;
}
}

voidinsert_end(int value)
{
structnode*newnode,*temp;
newnode=create(value);
if(head==NULL)
{

15
head=newnode;
}
else
{
temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newnode;
}
}

voidinsert_pos(int value,int pos)

{
structnode*newnode,*temp1,*temp2;
int i,c=1;
newnode=create(value);
i=count();
if(pos==1)
insert_begin(value);
elseif(pos>i+1)
{
printf("insertion is not posible");
return;
}
else
{
temp1=head;
while(c<=pos-1&& temp1!=NULL)
{
temp2=temp1;
temp1=temp1->next;
c++;
}
newnode->next=temp2->next;
temp2->next=newnode;
}
}

voiddelete_begin()
{
structnode*temp;
if(head==NULL)
{
printf("deletion is not possible");
}
else
{
temp=head;
head=head->next;
free(temp);
}
}
voiddelete_end()
{
structnode*temp1,*temp2;

16
if(head==NULL)
{
printf("deletion is not possible");
}
else
{
temp1=head;
while(temp1->next!=NULL)
{
temp2=temp1;
temp1=temp1->next;
}
temp2->next=NULL;
free(temp1);
}
}
voiddelete_pos(int pos)
{
structnode*temp1,*temp2;
int i,c=1;
i=count();
if(pos==1)
delete_begin();
elseif(pos>i)
{
printf("Deletion is not posible");
return;
}
else
{
temp1=head;
while(c<=pos && temp1->next!=NULL)
{
temp2=temp1;
temp1=temp1->next;
c++;
}
temp2->next=temp1->next;
free(temp1);
}
}
voiddisplay()
{
structnode*temp;
if(head==NULL)
{
printf("list is empty");
}
else
{
temp=head;
while(temp->next!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
}
printf("%d",temp->data);

17
}
}

voidmain()
{
int ch,pos,value;
do
{
printf("\n1.Insert Begin\n2.Insert End\n3.Insert Position\n4.Delete Begin\n5.Delete End\n6
.Delete Position\n7.Display\n8.Exit\n");
printf("enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case1:printf("enter the value:");
scanf("%d",&value);
insert_begin(value);
break;
case2:printf("enter value:");
scanf("%d",&value);
insert_end(value);
break;
case3:printf("enter value:");
scanf("%d",&value);
printf("enter position you want to insert: ");
scanf("%d",&pos);
insert_pos(value,pos);
break;
case4:delete_begin();
break;
case5:delete_end();
break;
case6:printf("enter position you want to delete: ");
scanf("%d",&pos);
delete_pos(pos);
break;
case7:display();
break;
case8:break;
default:printf("\nyour choice is wrong!.. ");
}
}while(ch!=8);
}

Difference between Array and Linked List

18
S.No. ARRAY LINKED LIST

A linked list is a group of

entities called a node. The
An array is a grouping of node includes two
data elements of equivalent segments: data and
1. data type. address.

It stores elements
It stores the data elements randomly, or we can say
in a contiguous memory anywhere in the memory
2. zone. zone.

In the case of an array, In the linked list, the

memory size is fixed, and placement of elements is
it is not possible to change allocated during the run
3. it during the run time. time.

The elements are not The data elements are

4. dependent on each other. dependent on each other.

The memory is assigned at The memory is assigned at

5. compile time. run time.

It is easier and faster to In a linked list, the process

access the element in an of accessing elements
6. array. takes more time.

In the case of an array, In the case of the linked

memory utilization is list, memory utilization is
7. ineffective. effective.

When it comes to When it comes to

executing any operation executing any operation
like insertion, deletion, like insertion, deletion, the
8 array takes more time. linked list takes less time.

DOUBLY LINKED LIST: A doubly linked list is a more complex data structure than a singly
linked list the main advantage of a doubly linked list is that it allows for efficient traversal of the
list in both directions. This is because each node in the list contains a pointer to the previous node
and a pointer to the next node.
.This allows for quick and easy insertion and deletion of nodes from the list as well as
efficient traversal of the list in both directions,

19
. A doubly linked list is a data structure that consists of a set of nodes each of which contains a
value and two pointers .one pointing to the previous node in the list and one pointing to the next
node in the list.
Representation of doubly linked list in data structure : In a data structure a doubly linked list is
represented using nodes that have three fields
1.Data
2.A pointer to the next node (next)
3.A pointer to the previous node(prev)

In C, the structure of a doubly linked list can be given as,

struct node
{
struct node
*prev;int data;
struct node *next;
};

Doubly linked list operations :

1.insertion
2.deletion
3.searching
4.Traversing

Example :

20
Insertion : To insert a new element in the list this operation can be performed in three ways

1.insertion at beginning of the list

2.insertion at end of the list
3.insertion after specified node

1.insertion at beginning of the list : The elements is inserted at beginning the new node
connected to next node. In doubly linked list first node and last node it indicates NULL
value.

Algorithm:
Step 1: IF ptr = NULL

WriteOVERFLOW
GotoStep9
[END OF IF]

Step 2: SET NEW_NODE = ptr

Step 3: SET ptr = ptr -> NEXT

21
Step 4: SET NEW_NODE -> DATA = VAL

Step 5: SET NEW_NODE -> PREV = NULL

Step 6: SET NEW_NODE -> NEXT = START

Step 7: SET head -> PREV = NEW_NODE

Step 8: SET head = NEW_NODE

Step 9: EXIT

2.insertion at end of the List :The element is inserted at end the new node inserted
into the list.

.Allocate the memory for the new node make the pointer ptr point to the newnode
being inserted .

Algorithm :
Step 1: IF PTR = NULL

WriteOVERFLOW
GotoStep11
[END OF IF]

Step 2: SET NEW_NODE = PTR

22
Step 3: SET PTR = PTR -> NEXT

Step 4: SET NEW_NODE -> DATA = VAL

Step 5: SET NEW_NODE -> NEXT = NULL

Step 6: SET TEMP = START

Step 7: Repeat Step 8 while TEMP -> NEXT != NULL

Step 8: SET TEMP = TEMP -> NEXT

[END OF LOOP]

Step 9: SET TEMP -> NEXT = NEW_NODE

Step 10C: SET NEW_NODE -> PREV = TEMP

Step 11: EXIT

3.insertion after specified node : To insert a node after the specified position in the list.

23
Algorithm :

Step 1: IF PTR = NULL

WriteOVERFLOW
GotoStep15
[END OF IF]

Step 2: SET NEW_NODE = PTR

Step 3: SET PTR = PTR -> NEXT

Step 4: SET NEW_NODE -> DATA = VAL

Step 5: SET TEMP = START

Step 6: SET I = 0

Step 7: REPEAT 8 to 10 until I

Step 8: SET TEMP = TEMP -> NEXT

STEP 9: IF TEMP = NULL

STEP 10: WRITE "LESS THAN DESIRED NO. OF ELEMENTS"

GOTOSTEP15
[ENDOFIF]
[END OF LOOP]

Step 11: SET NEW_NODE -> NEXT = TEMP -> NEXT

Step 12: SET NEW_NODE -> PREV = TEMP

Step 13 : SET TEMP -> NEXT = NEW_NODE

24
Step 14: SET TEMP -> NEXT -> PREV = NEW_NODE

Step 15: EXIT

2.Deletion : Delete a node from the list the deletion of a node in a doubly linked list can be divide in to
three categories

1. Deletion at beginning of the list

2.Deletion at end of the list

3.deletion at a specified node

1.Deletion at beginning of the list : Deletion in doubly linked list at the beginning is the simplest
operation to delete a node at first node and head pointing to next node of the list now free the pointer
ptr by using free function.

Algorithm :

STEP 1: IF HEAD = NULL

WRITEUNDERFLOW
GOTO STEP 6

STEP 2: SET PTR = HEAD

STEP 3: SET HEAD = HEAD → NEXT

STEP 4: SET HEAD → PREV = NULL

STEP 5: FREE PTR

STEP 6: EXIT

25
2.deletion at end of the list : Deletion of the last node in a doubly linked list needs traversing the list in
order to reach the last node of the list and then make pointer.

1.if the list is already empty then the condition head==NULL will become true and there fore the
operation cannot be carried on.

2.if there is only one node in the list then the condition head->next==NULL become true.

3.other wise just traverse the list to reach the last of the list.

Algorithm :

Step 1: IF HEAD = NULL

26
WriteUNDERFLOW
GotoStep7 7
[END OF IF]

Step 2: SET TEMP = HEAD

Step 3: REPEAT STEP 4 WHILE TEMP->NEXT != NULL

Step 4: SET TEMP = TEMP->NEXT

[END OF LOOP]

Step 5: SET TEMP ->PREV-> NEXT = NULL

Step 6: FREE TEMP

Step 7: EXIT

Deleting the Last Node from a Doubly Linked List:

3. Deletion at a specified node : in order to delete the node after the specified data we
need to perform the following steps
. copy the head pointer into a temporary pointer temp.
. Traverse the list until we find the desired data value.
. check if this is the last node of the list.
. check if the node which is to be deleted is the last node of the list if it so then we
have to make the next pointer of this node point to NULL so that it can be the new
last node of the list.

27
Algorithm:

Step 1: IF HEAD = NULL

WriteDERFLOW
GotoStep9
[END OF IF]

Step 2: SET TEMP = HEAD

3: Repeat Step 4 while TEMP -> DATA != ITEM

Step 4: SET TEMP = TEMP -> NEXT

[END OF LOOP]

Step 5: SET PTR = TEMP -> NEXT

Step 6: SET TEMP -> NEXT = PTR -> NEXT

Step 7: SET PTR -> NEXT -> PREV = TEMP

Step 8: FREE PTR

Step 9: EXIT

28
3.searching : we just need traverse the list in order to search for a specific element in the list
perform following operations in order to search a specific operation
1.copy head pointer into temporary pointer variable ptr.
2.declare a local variable I and assign it to 0.
3.Traverse the list until the pointer ptr becomes NULL keep shifting pointer to its next and
increasing i by plus one.
4.compare each element of the list with the item which is to be searched.
5.if the item matched with any node value then the location of that value I will be returned
from the function else NULL is returned.
Algorithm :

Step 1: IF HEAD == NULL

WRITE"UNDERFLOW"
GOTOSTEP8
[END OF IF]

Step 2: Set PTR = HEAD

Step 3: Set i = 0

Step 4: Repeat step 5 to 7 while PTR != NULL

Step 5: IF PTR → data = item

return i
[END OF IF]

Step 6: i = i + 1

Step 7: PTR = PTR → next

Step 8: Exit

4.Traversing :Although traversing means visiting each node of the list once to perform some specific
operation .Here we are printing the data associated with each node of the list.

29
Algorithm :

Step 1: IF HEAD == NULL

WRITE"UNDERFLOW"
GOTOSTEP6
[END OF IF]

Step 2: Set PTR = HEAD

Step 3: Repeat step 4 and 5 while PTR != NULL

Step 4: Write PTR → data

Step 5: PTR = PTR → next

Step 6: Exit

. Circular linkedlist : in a circular singly linked list the last node of the list contains a pointer to the
first node of the list. we can have circular singly linked list as well as circular doubly linked list.

. we traverse a circular singly linked list until we reach the same node where we started .The
circular singly linked list has no beginning and no ending there is no null value present in the next
part of any of the nodes.

. circular linked list are mostly used in task maintenance in operating system.

Operations : circular linked list operations are

1.insertition

30
2.deletion
3.Traversing
4.Searching
1.insertion : To insert a newnode in the list .insertion can be classified as
.insertion at beginning : There are two scenario in which a node can be inserted in circular
singly linked list at beginning .
.Either the node will be inserted in an empty list or the node is to be inserted in an already
filled list.
. The condition head==NULL will be true since the list in which we are inserting the node is
a circular singly linked list there fore the only node of the list.
. The condition head==NULL will become false which means that the list contains at least
one node.

Algorithm :
Step 1: IF PTR = NULL
WriteOVERFLOW
GotoStep11
[END OF IF]

Step 2: SET NEW_NODE = PTR

Step 3: SET PTR = PTR -> NEXT

Step 4: SET NEW_NODE -> DATA = VAL

Step 5: SET TEMP = HEAD

Step 6: Repeat Step 8 while TEMP -> NEXT != HEAD

Step 7: SET TEMP = TEMP -> NEXT

[END OF LOOP]

31
Step 8: SET NEW_NODE -> NEXT = HEAD

Step 9: SET TEMP → NEXT = NEW_NODE

Step 10: SET HEAD = NEW_NODE

Step 11: EXIT

2.inserting node at end of the list :To insert a new node in end of the list

Algorithm :

Step 1: IF PTR = NULL

WriteOVERFLOW
GotoStep1

[END OF IF]

Step 2: SET NEW_NODE = PTR

Step 3: SET PTR = PTR -> NEXT

Step 4: SET NEW_NODE -> DATA = VAL

Step 5: SET NEW_NODE -> NEXT = HEAD

Step 6: SET TEMP = HEAD

Step 7: Repeat Step 8 while TEMP -> NEXT != HEAD

Step 8: SET TEMP = TEMP -> NEXT

[END OF LOOP]

Step 9: SET TEMP -> NEXT = NEW_NODE

Step 10: EXIT

32
2. Deletion:To delete the element into the list it can be classified as

. Deletion at beginning : Remove the node from circular singly linked list at the beginning of the node
in the list .

. There are three scenarios of deleting a node from circular singly linked list at beginning

1.The list is empty

2.The list contains single node .

3.The list contains more than one node .

Algorithm:

Step 1: IF HEAD = NULL

WriteUNDERFLOW
GotoStep8
[END OF IF]

Step 2: SET PTR = HEAD

Step 3: Repeat Step 4 while PTR → NEXT != HEAD

Step 4: SET PTR = PTR → next

[END OF LOOP]

Step 5: SET PTR → NEXT = HEAD → NEXT

Step 6: FREE HEAD

Step 7: SET HEAD = PTR → NEXT

33
Step 8: EXIT

.Deletion at end of the List :There are three scenarios of deleting a node in circular singly
linked list at the end
. The list is empty
. The list contains single element.
. The list contains more than one element.

Algorithm :

Step 1: IF HEAD = NULL

WriteUNDERFLOW
GotoStep8
[END OF IF]

Step 2: SET PTR = HEAD

Step 3: Repeat Steps 4 and 5 while PTR -> NEXT != HEAD

Step 4: SET PREPTR = PTR

Step 5: SET PTR = PTR -> NEXT

[END OF LOOP]

Step 6: SET PREPTR -> NEXT = HEAD

Step 7: FREE PTR

Step 8: EXIT

34
3.Traversing : Although traversing means visiting each node of the list once to perform some
specific operation Here we are printing the data associated with each node of the list.

Algorithm:

1. Set ptr=Head

2. If ptr=NULL write empty list goto step7

3. Repeat step 4 and 5 until Ptr->next!=head

4. print ptr->data=value

5.ptr=ptr->next

6.print ptr->data

7.Exit

4.Searching : searching in circular singly linked list needs traversing across the list the item which
is to be searched in the list is matched with each node data of the list once and if the match found
then the location of that item is returned other wise -1 returned.

Algorithm :

1.set Ptr=head

2.set I=0

3.if ptr=NULL write “empty list” goto step8

4.if head->data=item

Write i+1

5.Repeat step 5 to 7 until ptr->next !=head

6.if ptr->data=item

7. i=i+1

8.ptr=ptr->next

9.Exit

STACKS:
35
Stack is a linear data structure in which the insertion and deletion operations are performed at
only one end. In a stack adding and removing of elements are performed at single position which is known
as "top". That means, new element is added at top of the stack and an element is removed from the top of
the stack only. In stack, the insertion and deletion operations are performed based on LIFO (Last In First
Out) principle. The first element which is inserted intostack is deleted last the last element which is
inserted into stack is deleted first.

In a stack, the insertion operation is performed using a function called "push" and deletion
operation is performed using a function called "pop". In the figure, PUSH and POP operations are
performed at top position in the stack. That means, both the insertion and deletion operations are
performed at one end i.e., at Top.

Example: If we want to create a stack by inserting 10,45,12,16,35 and 50. Then 10 becomes
the bottom most element and 50 is the top most element. Top is at 50 as shown in the image below.

OPERATIONS ON A STACK :
The following are some common operations implemented on the stack
. push(): when we insert an element in a stack then the operation is known as a push . if the stack is
full then the overflow condition occurs.
. pop(): when we delete an element from the stack the operation is known as a pop. If the stack is
empty means that no element exists in the stack this state is known as an underflow state.
. isEmpty(): it determines whether the stack is empty or not.
.isfull():it determines whether the stack is full or not.
.peek(): it returns the element at the given position.
36
.count(): it returns the total number of elements available in a stack.
. display():it prints all the elements available in the stack.

. Push operation : Before inserting an element in a stack we check whether the stack is full.if we
try to insert the element in a stack and the stack is full then the overflow condition occurs.
. when we initialize a stack we set the value of top as -1 to check that the stack is empty. when
the new element is pushed in a stack first the value of the top gets incremented i.e top=top+1
And the element will be placed at the new position of the top.
. The elements will be inserted until we reach the maxsize of the stack.

.POP operation : Before deleting the element from the stack, we check whether the stack is
empty.

. If we try to delete the element from the empty stack, then the underflow condition occurs.

. If the stack is not empty, we first access the element which is pointed by the top

. Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

37
Stack data structure can be implement in two ways.
They are as follows. 1. Stack Using Arrays

2. stack Using Linked List

When stack is implemented using array, that stack can organize only limited number of
elements.
When stack is implemented using linked list, that stack can organize unlimited number of
elements.
ARRAY REPRESENTATION OF STACKS:
In the computer’s memory, stacks can be represented as a linear array. Every stack has a
variable called TOP associated with it, which is used to store the address of the topmost element
of the stack. It is this position where the element will be added to or deleted from. There is another
variable called MAX, which is used to store the maximum number of elements that the stack can
hold. If TOP = NULL, then it indicates that the stack is empty and if TOP = MAX–1, then the stack
is full. (You must be wondering why we have written MAX–1. It is because array indices start from
0.).

38
The above stack shows that TOP = 4, so insertions and deletions will be done at this
position. In the above stack, five more elements can still be stored.

Stack implementation using array:

Before implementing actual operations, first follow the below steps to create an empty
stack.
Step 1: Declare all the functions used in stack (push,pop,display) implementation.
Step 2: Create a one dimensional array with fixed size .
Step 3: Define a integer variable 'top' and initialize with '-1'. (int top = -1).
Step 4: In main method display a menu with list of operations and make suitable function calls to
perform operation selected by the user on the stack.
Push Operation:
The push operation is used to insert an element into the stack. The new element is added
at the topmost position of the stack. However, before inserting the value, we must first check if
TOP=MAX–1, because if that is the case, then the stack is full and no more insertions can be
done. If an attempt is made to insert a value in a stack that is already full, an OVERFLOW message is printed.

To insert an element with value 6, we first check if TOP=MAX–1. If the condition is false,
then we increment the value of TOP and store the new element at the position given by stack[TOP].
Thus, the updated stack becomes as shown

Algoritm to Insert an Element in a Stack:

39
The algorithm to insert an element in a stack. In Step 1, we first check for the OVERFLOW
condition. In Step 2, TOP is incremented so that it points to the next location in the array. In Step
3, the value is stored in the stack at the location pointed by TOP.
Pop Operation:
The pop operation is used to delete the topmost element from the stack. However, before
deleting the value, we must first check if TOP=NULL because if that is the case, then it means the
stack is empty and no more deletions can be done. If an attempt is made to delete a value from a
stack that is already empty, an UNDERFLOW message is printed.

To delete the topmost element, we first check if TOP=NULL. If the condition is false, then
we decrement the value pointed by TOP. Thus, the updated stack becomes as

Algoritm to Delete an Element from Stack:

The algorithm to delete an element from a stack. In Step 1, we first check for the
UNDERFLOW condition. In Step 2, the value of the location in the stack pointed by TOP is stored
in VAL. In Step 3, TOP is decremented.

Peek Operation:
40
Peek is an operation that returns the value of the topmost element of the stack without
deleting it from the stack.However, the Peek operation first checks if the stack is empty, i.e., if TOP
= NULL, then an appropriate message is printed, else the value is returned.
Here, the Peek operation will return 5, as it is the value of the topmost element of the stack.

Algorithm for Peek operation:

Display operation :

Displays the elements of a Stack. We can use the following steps to display the elements
of a stack.
Step 1: Check whether stack is EMPTY. (top == -1)
Step 2: If it is EMPTY, then display "Stack is EMPTY!!!" and terminate the function.
Step3: If it is NOT EMPTY, then define a variable 'i' and initialize with top. Display stack[i]
value and decrement i value by one (i--).
Step 4: Repeat above step until i value becomes '0'.

Stack using Linked List:

The major problem with the stack implemented using array is, it works only for fixed
number of data values. That means the amount of data must be specified at the beginning of the
implementation itself( size of the stack). Stack implemented using array is not suitable, when we
don't know the size of data which we are going to use. A stack data structure can be implemented
by using linked list data structure. The stack implemented using linked list can work for unlimited
number of values. That means, stack implemented using linked list works for variable size of data.
So, there is no need to fix the size at the beginning of the implementation. The Stack implemented
using linked list can organize as many data values as we want.

In a linked stack, every node has two parts—one that stores data and another that stores the
address of the next node. The START pointer of the linked list is used as TOP. All insertions and
deletions are done at the node pointed by TOP. If TOP = NULL, then it indicates that the stack is
41
empty.

Example:

In above example, the last inserted node is 9 and the first inserted node is 5. The order of elements
inserted is 5,6,2,4,3,7,1 and 9.
Stack implementation using Linkedlist:
To implement stack using linked list, we need to set the following things before
implementing actual operations.
Step 1 : Declare all the functions used in stack(push,pop,disply) implementation
Step 2: Define a 'Node' structure with two fields data and link.
Step 3: Define a Node pointer 'top' and set it to NULL.
Step 4: Implement the main method by displaying Menu with list of operations and make suitable
function calls in the main method.
OPERATIONS ON A LINKED STACK:
A linked stack supports all the three stack operations, that is, push, pop, and peek.
Push Operation:
The push operation is used to insert an element into the stack. The new element is added at the
topmost position of the stack.

To insert an element with value 9, we first check if TOP=NULL. If this is the case, then
we allocate memory for a new node, store the value in its DATA part and NULL in its NEXT part.
The new node will then be called TOP. However, if TOP!=NULL, then we insert the new node at
the beginning of the linked stack and name this new node as TOP.
Thus, the updated stack becomes as shown as below:

Algorithm to push an element into a linked stack:

42
In Step 1, memory is allocated for the new node. In Step 2, the DATA part of the new node
is initialized with the value to be stored in the node. In Step 3, we check if the new node is the first
node of the linked list. This is done by checking if TOP = NULL. In case the IF statement evaluates
to true, then NULL is stored in the NEXT part of the node and the new node is called TOP.
However, if the new node is not the first node in the list, then it is added before the first node of
the list (that is, the TOP node) and termed as TOP.
Pop Operation:
The pop operation is used to delete the topmost element from a stack. However, before
deleting the value, we must first check if TOP=NULL, because if this is the case, then it means that
the stack is empty and no more deletions can be done. If an attempt is made to delete a value from
a stack that is already empty, an UNDERFLOW message is printed.

In case TOP!=NULL, then we will delete the node pointed by TOP, and make TOP point
to the second element of the linked stack. Thus, the updated stack becomes as shown below

Algorithm to delete an element from a stack:

43
In Step 1, we first check for the UNDERFLOW condition. In Step 2, we use a pointer PTR
that points to TOP. In Step 3, TOP is made to point to the next node in sequence. In Step 4, the
memory occupied by PTR is given back to the free pool.
Display operation:
Displaying stack of elements We can use the following steps to display the elements (nodes)
of a stack.
Step 1: Check whether stack is Empty (top == NULL).
Step 2: If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
Step 3: If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
Step 4: Display 'temp->data-> and move it to the next node. Repeat the same until temp reaches to
the first node in the stack (temp-> link != NULL).
Step 5: Finally! Display 'temp->data->NULL’.

APPLICATIONS OF STACKS:
Stacks can be easily applied for a simple and efficient solution. Different Application of
Stacks:

• Reversing a list

• Arithmetic Expression

a)infix notation

b)prefix notation

c)postfix notation

d)Evaluation postfix expression

• Conversion of an infix expression into a postfix expression
• Conversion of an infix expression into a prefix expression
• Evaluation of a prefix expression
• Recursion
Tower of Hanoi
. Balancing symbols

1.Reversing a List : To reverse a string or elements in reverse order.

.It is a efficient

44
. write a program to implement stack operations using a reversing a list of elements .
#include<stdio.h>
#include<conio.h>
#define maxsize 10
‘ int stack[size],top=-1;
Void push(int);
int pop();
int isempty();
void main()
{
int a[size],i;
clrscr();
printf(“enter array elements \n”);
for(i=0;i<size;i++)
scanf(“%d”,&a[i]);
for(i=0;i<size;i++)
push(a[i]);
printf(“List is reverse order \n”);
for(i=0;!isempty();i++)
{
int ele;
ele=pop();
printf(“%d”,ele);
}
getch();
}
Void push(int ele)
{
if(top==size-1)
{
Printf(“stack is overflow “);
else

45
top=top+1;
stack[top]=ele;
}
}
int pop()
{
int ele;
if(top==-1)
printf(“stack is under flow “);
else
{
ele=stack[top];
top=top-1;
}
return ele;
}
int isempty()
{
if(top==-1)
return 1;
else
return 0;
}
2.Expressions : it is a set of operands in between the operator is called as expression
Example : A+B
a) Infix : when the operator is written in between the operands then it is known as infix
notation.
Example : a+b, a/b,a*b
b) Prefix: The operator comes first followed by the operands .
Example : ++a,+ab,--ab
c)Postfix: The operands comes first followed by the operator .
Example : ab+,ab*,ab/
d. Evaluation of postfix Expression : it is a operand stack
46
. only one stack is used .
. if the character is an operand then push into stack.
. if the character is an operator then pop top,two operands from the stack and push the result
back into stack.
.After reading all the characters from the postfix expression stack will be having only the
which is result.
Example: 562*+

character stack
5 5
5 5 6
2 562
* Pop 2 ,pop 6
6*2=12
5 12
+ Pop 12,pop5
5+12=17
562*+=17
3.Conversion of infix to postfix expression :
1) If the character is left parenthesis push to the stack.
2) If the character is operand ,add to the postfix expression
3) If the character is operator ,check whether stack is empty
1)If the stack is empty ,push operator into stack
2)If the stack is not empty ,check the priority of the operator
i)if the priority operator > operator present at top of stack then push operator into
stack.
ii) if the priority of the operator is <= operator present at top of the stack ,then pop
the operator from stack and ADD to postfix expression and goto step(i).
4)if the character is right parenthesis then pop all the operations from the stack until it matches
left parenthesis and ADD to postfix expression.
5)After reading all the characters ,if stack is not empty then pop and ADD to postfix expression.
Example : Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

47
Input Expression Stack Postfix Expression

K K

+ +

L + KL

- - K L+

M - K L+ M

* -* K L+ M

N -* KL+MN

K L + M N*
+ +
K L + M N* -

( +( K L + M N *-

O +( KL+MN*-O

^ +(^ K L + M N* - O

P +(^ K L + M N* - O P

) + K L + M N* - O P ^

* +* K L + M N* - O P ^

W +* K L + M N* - O P ^ W

/ +/ K L + M N* - O P ^ W *

U +/ K L + M N* - O P ^W*U

48
/ +/ K L + M N* - O P ^W*U/

V +/ KL + MN*-OP^W*U/V

* +* KL+MN*-OP^W*U/V/

T +* KL+MN*-OP^W*U/V/T

KL+MN*-OP^W*U/V/T*
+ +
KL+MN*-OP^W*U/V/T*+

Q + KL+MN*-OP^W*U/V/T*Q

KL+MN*-
OP^W*U/V/T*+Q+

The final postfix expression of infix expression(K + L - M*N + (O^P) * W/U/V * T + Q) is KL+MN*-OP^W*U/V/T*+Q+.

4.Conversion of infix to prefix expression :

. reverse the expression

. Apply the postfix notation
. left parenthesis ( to )
.right parenthesis ) to (

. reverse the postfix expression

Example : (A+B)*C-D+F
Reverse the expression F+D-C*(B+A)

character stack postfix

F F
+ + F
D + FD
49
- + -(POP +) FD+
C - FD+
* - * FD+C
( FD+C
- *(
B FD+CB
- *(
+ FD+CB
- *(+
FD+CB*
POP(*)
A -(+ FD+CB*A
) -(+) FD+CB*A+-
POP(+)
POP(-)

ReversetheExpression=-+A*BC+FD

5.Evaluation of a Prefix Expression :start right to left

-+3*45/16^23=21

symbol stack

3 3

2 3 2

^ 8

16 8 16

/ 2

5 2 5

4 2 5 4

* 2 20

3 2 20 3

+ 2 23

- 21

6.Recursion : Recursion is a function the function call itself is called as recursion

Recursion example Towers of Hanoi problem

.Towers of Hanoi problem : It is a puzzle game

. Here Three pegs or disks the data is moved to one disk to another disk

Disks are A,B,C DISK=3 N=3

1.Tower(N-1,Begin,End,Aux)

2.Tower(1,Begin,Aux,End)

3.Tower(N-1,Aux,Begin,End)

S.NO disk

50
1 A->C

2 A->B

3 C->B

4 A->C

5 B->A

6 B->C

7 A->C

Algorithm for Tower of Hanoi:

Step 1: Start

Step 2: Let the three towers be the source, dest, aux. Step

3: Read the number of disks, n from the user. Step 4:

Move n-1 disks from source to aux.

Step 5: Move nth disk from source to dest.Step

6: Move n-1 disks from aux to dest.

Step 7: Repeat Steps 3 to 5, by decrementing n by 1.

Step 8: Stop

51
7.Balancing Symbols : symbol stack is used

( Expressions
[ Expressions
{ } Block of statements
( ) Balanced symbols
[ ] Balanced symbols
. counting open symbols and counting closed symbols .

Algorithm : read character from Expression

. if character is open symbol ‘(‘,’[‘,’{‘ push symbol into the stack.

. if character is closed symbol ‘)’ ,’]’ ,’}’

a)check if stack is empty if thus expression is unbalanced.

b)if the stack is not empty then pop the symbol from the stack and compare with the
symbol which is read ,if doesn’t matches expression is unbalanced.else repeat the process.

. After Reading all character of expression still stack is not empty that implies unbalanced
expression.

Ex: [(a+b)(a-b)] it is a balanced expression .

[(a+b)(a-b] it is a unbalanced expression

QUEUES: Queue is a linear data structure which elements are inserted at one end called rear and
which elements are deleted other end called front .front is front side and rear is backside.Queue
is a FIFO Technique which element is inserted first that element is deleted first.

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()".

.Queue uses two pointers front and rear

The front pointer accesses the data from the front end.while the rear pointer accesses data
from the rear end.

Example: Queue after inserting 25, 30, 51, 60 and 85.

52
Operations on a Queue:
The following operations are performed on a queue data structure.
a. enQueue(value) -(To insert an element into the queue)
b. deQueue() - (To delete an element from the queue)
c. display() - (To display the elements of the queue)

1.Enqueue(): Enqueue is a function used to insert a new

element into the queue.in a queue the new element is
always inserted at rear position .The Enqueue() function
takes one integer value as parameter and inserts that value
into the queue.

Ex: consider the list of elements 12,9,7,18,14,36,45

Initially front=0n and rear=-1 then rear=rear+1=-1+1=0

Front=0 and rear=0 12 is inserted o th position

Front=0 and rear=1 9 is inserted 1 st position

Front=0 rear=2 7 is inserted 2 nd position

Front=0 rear=3 18 is inserted 3rd position

Front=0 rear=4 14 is inserted 4 th position

Front=0 rear=5 36 is inserted 5 th position

Front=0 rear=6 45 is inserted 6 th position

The elements are 12 9 7 18 14 36 45

53
Algorithm :

Step 1:if Rear=Max-1 write overflow goto step4

Step2: if front=-1 and rear=-1

Set front=rear=0

Else

Set Rear=Rear+1

Step 3:Set Queue[Rear]=num

Step 4:Exit

2.Dequeue operation :Deleting a value from the queue .in

a queue data structure dequeue() is a function used to
delete an element from the queue.in a queue the element
is always deleted from front position .The dequeue()
function doesnot take any values as parameter.

Initially front=-1 and rear=6 then front=front+1 and

front=0

Front=0 and rear=6 12 is deleted

Front=1 and rear=6 9 is deleted from the queue.

Front=2 rear=6 7 is deleted from the queue

Front=3 rear=6 18 is deleted from the queue

Front=4 rear=6 14 is deleted from the queue

Front=5 rear=6 36 is deleted from the queue

Front=6 rear=6 45 is deleted from the queue then queue is

empty .

Algorithm:

Step 1: if front=-1 or front >Rear

Write under flow

54
Else

Set val=queue[front]

Set front=front+1

Step 2:Exit

Display():

Displays the elements of a Queue: We can use the following steps to display the elements of a
queue.

Step 1: Check whether queue is EMPTY. (front == rear)

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+1'.

Step 4: Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i'value
is equal to rear (i <= rear)

Queue data structure can be implemented in two ways.

They are as follows...

1. Using Array
2. Using Linked List
When a queue is implemented using array, that queue can organize only limited number of elements.
When a queue is implemented using linked list, that queue can organize unlimited number of elements.

Queue implementation by Using Array:

A queue data structure can be implemented using one dimensional array. But, queue
implemented using array can store only fixed number of data values. The implementation of queue data
structure using array is very simple, just define a one dimensional array of specific size and insert or
delete the values into that array by using FIFO (First In First Out) principle with the help of variables
'front' and 'rear'. Initially both 'front' and 'rear' are set to -1. Whenever, we want to insert a new value

55
into the queue, increment 'rear' value by one and then insert at that position.
. Two conditions
Overflow –insertion into queue which is full
Underflow –deletion from empty queue
.Two Ends
Front – it’s point to starting element
Rear – it’s point to last element .

Step 1: Declare all the user defined functions which are used in queue implementation.

Step 2: Create a one dimensional array with above defined SIZE (int queue[SIZE])

Step 3: Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -1,rear =
-1)

Step 4: Then implement main method by displaying menu of operations list and make suitable
function calls to perform operation selected by the user on queue.

EnQueue Operation :

Inserting value into the queue:

In a queue data structure, enQueue() is a function used to insert a new element into the queue. Ina
queue, the new element is always inserted at rear position. The enQueue() function takes one integer
value as parameter and inserts that value into the queue. We can use the following stepsto insert an
element into the queue.

New element =45

56
DeQueue Opeartion:

Deleting a value from the Queue In a queue data structure, deQueue() is a function usedto
delete an element from the queue. In a queue, the element is always deleted from front position. The
deQueue() function does not take any value as parameter. We can use the following steps to delete an
element from the queue.

Deleted element=12
Queue

LINKED REPRESENTATION OF QUEUES:

The major problem with the queue implemented using array is, It will work for only fixed
number of data. That means, the amount of data must be specified in the beginningitself. Queue using
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 linked list data structure. The queue which is implemented using
linked list can work for unlimited number of values. That means, queue using linked list can work for
variable size of data (No need to fix the size at beginning of the implementation). The Queue
implemented using linked list can organize as many data values as we want.

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.
To implement queue using linked list, we need to set the following things beforeimplementing
57
actual operations.
Step 1: Include all the header files which are used in the program. And declare all the userdefined
functions.
Step 2: Define a 'Node' structure with two members data and next.
Step 3: Define two Node pointers 'front' and 'rear' and set both to NULL.
Step 4: Implement the main method by displaying Menu of list of operations and make suitable
function calls in the main method to perform user selected operation.
EnQueue(value):
Inserting an element into the Queue We can use the following steps to insert a new nodeinto
the queue.

Algorithm to Insert an Element into Queue using Linked List:

DeQueue():
Deleting an Element from Queue We can use the following steps to delete a node from the
queue.

58
Algorithm to Delete an Element from Queue using Linked List:

Display():
Displaying the elements of Queue We can use the following steps to display the elements (nodes)of a
queue...
Step 1: Check whether queue is Empty (front == NULL).
Step 2: If it is Empty then, display 'Queue is Empty!!!' and terminate the function.
Step 3: If it is Not Empty then, define a Node pointer 'temp' and initialize with front.
Step 4: Display 'temp data -> and move it to the next node. Repeat the same until 'temp' reaches to
'rear' (temp -> next != NULL).
Step 5: Finally Display 'temp-> data -> NULL'.

TYPES OF QUEUES:
A queue data structure can be classified into the following types:
1. Circular Queue
2. Deque
3. Priority Queue

Applications of Queues:
. Printing job management
. client server model
. CPU scheduling - in which process is executed first

59
. Batch processing – manage incoming jobs and process them in order .
. Resource Allocation
. Simulation - line of customers waiting for bank
. In process communication – process and multithread system

60