DATA STRUCTURE AND ALGORITHM

Module I

LINEARDATASTRUCTURES- LIST

Introduction, Data structure Types - Data structure operations - Abstract Data Types (ADTs) –
List ADT – array-based implementation – linked list implementation ––singly linked lists-–
applications of lists –Polynomial Manipulation - Stack ADT – Queue ADT - Evaluating
arithmetic expressions.

Data:
Acollectionoffacts,concepts,figures,observations,occurrencesorinstructionsinaFormalizedmanner.

Information:
Themeaning thatiscurrently assignedtodataby meansoftheconventionsappliedto those data
(i.e. processed data)
Record:
Collectionofrelatedfields.

Datatype:

Setofelementsthatsharecommonsetofpropertiesusedtosolveaprogram.

DataStructures:
DataStructureisthewayoforganizing,storing, andretrievingdataandtheirrelationship with each other.
Characteristicsofdatastructures:
1. Itdepictsthelogicalrepresentationofdataincomputermemory.
2. Itrepresentsthelogicalrelationshipbetweenthevariousdataelements.
3. Ithelpsinefficientmanipulationofstoreddataelements.
4. Itallowstheprogramstoprocessthedatainanefficientmanner.

OperationsonDataStructures:
1. Traversal
 DATA STRUCTURE AND ALGORITHM
Module I
2. Search
3. Insertion
4. Deletion

CLASSIFICATIONOFDATASTRUCTURES

DATA STRUCTURES

PRIMARY DATA STRUCTURES SECONDARY DATA STRUCTURES

INT, CHAR ,FLOAT ,

DOUBLE
LINEAR DATA NON LINEAR DATA
STRUCTURES STRUCTURES

LISTS ARRAYS STACKS QUEUES TREES GRAPHS

PrimaryDataStructures /PrimitiveDataStructures:
Primitivedatastructuresincludeallthefundamentaldatastructuresthatcanbedirectlymanipulated by
machine-level instructions. Some of the common primitive data structuresinclude integer, character,
real, Boolean.etc

SecondaryDataStructures/NonPrimitiveDataStructures:
Non primitive data structures,refer to all those data structures that are derivedfrom one or more
primitive data structures. The objective of creating non-primitive data structures is to form sets of
homogeneous or heterogeneous data elements.

LinearDataStructures:
Linear data structures are data structures in which, all the data elements are arranged in linearor
sequential fashion. Examples of data structures include arrays, stacks, queues, linked lists, etc.

NonLinearStructures:
 DATA STRUCTURE AND ALGORITHM
Module I
In non-linear data structures, there is definite order or sequence in which data elements are arranged.
For instance, a non-linear data structures could arrange data elements in a hierarchical fashion.
Examples of non-linear data structures are trees and graphs.

Staticanddynamicdatastructure:

StaticDS:
If a DS is created using static memory allocation,
ie.DS formed when thenumber of data items are known in advance ,it is known as static
data static ds or fixed size ds.

Dynamic DS:
Ifthe DS iscreatedusingdynamicmemory allocation
i.e DS formedwhenthenumberofdata items are not known in advance is known as dynamic ds or
variable size DS.

Applicationofdatastructures:
Datastructuresarewidelyappliedinthefollowingareas:
 Compiler Design
 Operating System
 Statistical Analysis Package
 DBMS
 Numerical Analysis
 Simulation
 Artificial Intelligence
 Graphics

ABSTRACTDATATYPES(ADT):

An abstract Data type (ADT) is defined as a mathematical model with a collection of operations
defined on that model. Set of integers, together with the operations of union, intersection and set
difference form a example of an ADT. An ADTconsists of data together with functions that operate on
that data.

Advantages/BenefitsofADT:
1. Modularity
2. Reuse
3. code is easier to understand
4. Implementation of ADTs can be changed without requiring changes to the program that
uses the ADTs.

THELISTADT:
 DATA STRUCTURE AND ALGORITHM
Module I
Listisanorderedsetofelements.
ThegeneralformofthelistisA1,A2, ……,AN
A1-Firstelementofthe list
AN- Lastelement ofthe list
N–Size of the list
Iftheelementatposition i isAi,thenitssuccessorisAi+1anditspredecessorisAi-1

VariousoperationsperformedonList
1. Insert(X,5)-InserttheelementXaftertheposition5.
2. Delete(X)-TheelementXisdeleted
3. Find(X)-ReturnsthepositionofX.
4. Next(i)-Returnsthepositionofits successorelementi+1.
5. Previous(i)- Returnsthepositionofitspredecessori-1.
6. Printlist-Contents ofthe list is displayed.
7. Makeempty-Makesthelistempty.

ImplementationoflistADT:

1. ArraybasedImplementation

2. LinkedListbasedimplementation

ArrayImplementationoflist:
Array is a collection of specific number of same type ofdata stored in consecutive memory locations.
Arrayis a static data structure i.e., the memoryshould be allocated in advance and the size is fixed. This
will waste the memoryspace when used space is less than the allocated space.

InsertionandDeletionoperationareexpensiveasitrequiresmoredatamovements Find and Print list

operations takes constant time.

Thebasicoperationsperformedonalistofelementsare
a. CreationofList.
b. InsertionofdataintheList
c. DeletionofdatafromtheList
d. Displayall data’sinthe List
e. Searchingforadata in thelist

Declarationof Array:
 DATA STRUCTURE AND ALGORITHM
Module I
#define
maxsize 10
intlist[maxs
ize], n ;

Create Operation:
Create operation is used to create the list with ‘n’ number of elements .If‘n’ exceeds the
array’smaxsize, then elements cannot be inserted into the list. Otherwise the arrayelements are stored
in the consecutive arraylocations (i.e.) list [0], list [1] and so on.

void create()
{
cout<<"\n Enter the number of elements you want to create: ";
cin>>n;
cout<<"\nenter the elements\n";
for(i=0;i<n;i++)
{
cin>>b[i];
}
}

Ifn=6,theoutputof creationisas follows:

list[6]

InsertOperation:
Insert operation is used to insert an element at particular position in the existinglist. Insertingthe
elementinthelastpositionofanarray iseasy.Butinserting the elementataparticularposition in an array is
quite difficult since it involves all the subsequent elementsto be shifted one position to the right.

Routinetoinsertanelementinthearray:
void insert()
{
cout<<"\nenter how many number u want to insert: ";
 DATA STRUCTURE AND ALGORITHM
Module I
cin>>f;
cout<<"\nEnter the elements\n";
for(i=0;i<n;i++)
{
cin>>b[n++];
}
}

Consideranarraywith5elements[maxelements=10]

10 20 30 40 50

If data 15 is to be inserted in the 2nd position then 50 has to bemoved to next index
position, 40 has to bemoved to 50 position, 30 has to bemoved to 40 position and20 has
to bemoved to 30 position.

10 20 30 40 50

10 20 30 40 50

Afterthisfourdatamovement, 15is insertedinthe2ndpositionofthe array.

10 15 20 30 40 50

DeletionOperation:
Deletion is theprocess ofremovingan elementfrom thearrayat anyposition.
Deleting an element from the end is easy. If an element is to be deleted from any particular position,it
requires all subsequent element from that positionis shifted one positiontowardsleft.
 DATA STRUCTURE AND ALGORITHM
Module I

Routinetodeleteanelementinthearray:
void deletion()
{
cout<<"Enter the number u want to delete \n";
cin>>d;
for(i=0;i<n;i++)
{
if(b[i]==d)
{
b[i]=0;
cout<
}
}

Consideranarraywith5elements[maxelements=10]

10 20 30 40 50

If data 20 is to be deleted from the array, then 30 has to be moved to data 20 position,
40 has to be moved to data 30 position and 50 has to be moved to data 40 position.

10 20 30 40 50

Afterthis3datamovement, data 20isdeletedfromthe2ndpositionofthearray.

10 30 40 50

DisplayOperation/Traversingalist
Traversalistheprocessofvisitingtheelements ina array.
Display( ) operation is used to displayall the elements stored in the list. The elements are stored from
the index 0 to n - 1. Using a for loop, the elements in the list are viewed
 DATA STRUCTURE AND ALGORITHM
Module I

Routinetotraverse/displayelementsofthearray:
Voiddisplay()
{
for(i=0;i<n;i++)
{
cout<<"\n"<<b[i];
}

SearchOperation:
Search( ) operation is used to determine whether a particular element is present in the list or not. Input
the search element to be checked in the list.

Routinetosearchanelementinthearray:
void search()
{
cout<<"Enter the number \n";
cin>>e;
for(i=0;i
{
if(b[i]==e)
{
cout<<"Value found the position\n"<
}}

PROGRAM FOR ARRAY IMPLEMENTATION OF LIST

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
void create();
void insert();
void deletion();
void search();
void display();
inta,b[20],n,d,e,f,i;
void main()
{
int c;
clrscr();
cout<<"\n Main Menu";
cout<<"\n 1.Create \n 2.Delete \n 3.Search \n 4.insert \n5.Display \n 6.Exit";
do
{
cout<<"\n enter your choice:";
cin>>c;
switch(c)
{
 DATA STRUCTURE AND ALGORITHM
Module I
case 1: create(); break;
case 2: deletion(); break;
case 3: search(); break;
case 4: insert(); break;
case 5: display(); break;
case 6: exit(0); break;
default:
cout<<"The given number is not between 1-5\n";
}
}
while(c<=6);
getch();
}
void create()
{
cout<<"\n Enter the number of elements you want to create: ";
cin>>n;
cout<<"\nenter the elements\n";
for(i=0;i<n;i++)
{
cin>>b[i];
}
}

void deletion()
{
cout<<"Enter the number u want to delete \n";
cin>>d;
for(i=0;i<n;i++)
{
if(b[i]==d)
{
b[i]=0;
cout<
}
}
}

void search()
{
cout<<"Enter the number \n";
cin>>e;
 DATA STRUCTURE AND ALGORITHM
Module I
for(i=0;i<n;i++)
{
if(b[i]==e)
{
cout<<"Value found the position\n"<
}
}
}

void insert()
{
cout<<"\nenter how many number u want to insert: ";
cin>>f;
cout<<"\nEnter the elements\n";
for(i=0;i<n;i++)
{
cin>>b[n++];
}
}

void display()
{
for(i=0;i<n;i++)
{
cout<<"\n"<<b[i];
}
}

Advantagesofarrayimplementation:
1. Theelementsarefastertoaccessusingrandomaccess
2. Searching an element is easier

Limitationofarrayimplementation
 Anarraystore its nodesin consecutivememorylocations.
 Thenumber of elements in the arrayis fixed and it is not possible to change the number of
elements .
 Insertion and deletion operation inarray are expensive. Since insertion is performed by pushing
the entire array one position down and deletion is performedby shifting theentire array one
position up.

Applicationsofarrays:
Arraysare particularlyused in programs that requirestoringlarge collection of similar type data
elements.

DifferencesbetweenArraybasedandLinkedbasedimplementation
 DATA STRUCTURE AND ALGORITHM
Module I

Array LinkedList
Definition Array is a collection of elements having Linked list is an ordered collection of
same data type with common elements which are connected by
Name links/pointers
Access Elements can be accessed using Sequential access
index/subscript, random access
Memorystructure Elements are stored in contiguous Elements are store data available
memory locations memory space
Insertion&Deletion Insertion and deletion takes more time Insertion and deletion are fast and
in array easy
MemoryAllocation Memory is allocated at compile time Memory is allocated at runtime
i.e static memory allocation i.e dynamic memory allocation
Types 1D,2D,multi-dimensional SLL, DLL, circular linked list
Dependency Each elements is independent Each node is dependent on each
other as address part contains address
of next node in the list

Linkedlistbasedimplementation:

LinkedLists:

A Linked list is an ordered collection of elements. Each element in the list is referred as a node.

Each node contains two fields namely,

Datafield-Thedatafield containstheactualdataoftheelementstobestoredinthelist
Next field- The next field contains the address of the next node in the list

DATA NEXT
ALinkedlistnode
10 40 20 30
Null

AdvantagesofLinkedlist:
1. Insertionanddeletionofelementscanbedoneefficiently
2. Itusesdynamicmemoryallocation
 DATA STRUCTURE AND ALGORITHM
Module I
3. Memoryutilizationisefficientcomparedto arrays
Disadvantagesof Linkedlist:
1. Linkedlistdoesnotsupportrandomaccess
2. Memory is required to store next field
3. Searchingtakestimecomparedtoarrays

Linked List ADT

A linked list is a sequence of data structures, which are connected together via links.
Linked List is a sequence of links which contains items. Each link contains a connection to another
link. Linked list is the second most-used data structure after array.
Following are the important terms to understand the concept of Linked List.
Link −Each link of a linked list can store a data called an element.
Next − Each link of a linked list contains a link to the next link called Next.
LinkedList − A Linked List contains the connection link to the first link called First.

Linked List Representation

Linked list can be visualized as a chain of nodes, where every node points to the next node.

As per the above illustration, following are the important points to be considered.
Linked List contains a link element called first.
Each link carries a data field(s) and a link field called next.
Each link is linked with its next link using its next link.
Last link carries a link as null to mark the end of the list.

Types of Linked List

Following are the various types of linked list.
 DATA STRUCTURE AND ALGORITHM
Module I
Singly Linked List − Item navigation is forward only.
Doubly Linked List − Items can be navigated forward and backward.
Circular Linked List − Last item contains link of the first element as next and the first element
has a link to the last element as previous.

Basic Operations
Following are the basic operations supported by a list.
Insertion − Adds an element at the beginning of the list.
Deletion − Deletes an element at the beginning of the list.
Display − Displays the complete list.
Search − Searches an element using the given key.
Delete − Deletes an element using the given key.

Insertion Operation
Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams
here. First, create a node using the same structure and find the location where it has to be inserted.

Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then
point B.next to C −NewNode.next −>RightNode;
It should look like this −

Now, the next node at the left should point to the new node.
LeftNode.next −>NewNode;
 DATA STRUCTURE AND ALGORITHM
Module I

This will put the new node in the middle of the two. The new list should look like this −

Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it
at the end, the second last node of the list should point to the new node and the new node will point to
NULL.
Deletion Operation
Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate
the target node to be removed, by using searching algorithms.

The left (previous) node of the target node now should point to the next node of the target node −
LeftNode.next −>TargetNode.next;

This will remove the link that was pointing to the target node. Now, using the following code, we will
remove what the target node is pointing at.
TargetNode.next −> NULL;
 DATA STRUCTURE AND ALGORITHM
Module I

We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate
memory and wipe off the target node completely.

Reverse Operation

This operation is a thorough one. We need to make the last node to be pointed by the head node and
reverse the whole linked list.

First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to
its previous node −

We have to make sure that the last node is not the last node. So we'll have some temp node, which
looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their
previous nodes one by one.

Except the node (first node) pointed by the head node, all nodes should point to their predecessor,
making them their new successor. The first node will point to NULL.
 DATA STRUCTURE AND ALGORITHM
Module I

We'll make the head node point to the new first node by using the temp node.

The linked list is now reversed.

Dynamicallocation
The process of allocating memory to the variables during execution of the program or at
run time is known as dynamic memory allocation. C language has four library routines
which allow this function.

Dynamic memory allocation gives best performance in situations in which we do not

know memory requirements in advance. C provides four library routines to automatically
allocate memory at the run time.

Singly Linked List

A singlylinked list is alinked list in which each nodecontains onlyonelink field pointingto the next
node in the list
 DATA STRUCTURE AND ALGORITHM
Module I

SLLwith a Header

Basicoperationsonasingly-linkedlistare:
1. Insert–Insertsanewnodeinthelist.
2. Delete– Deletes anynodefrom the list.
3. Find – Findstheposition(address)ofanynode in the list.
4. FindPrevious-Findstheposition(address)ofthepreviousnodeinthelist.
5. FindNext-Finds theposition(address)ofthenextnodeinthelist.
6. Display-displaythe updateinthelist
7. Search-findwhetheraelementispresentinthelistornot

Program for Singly Linked List in C Programming.

DeclarationofLinkedList
voidinsert(intX,ListL,positionP); void
find(List L,int X);
void delete(int x , List L);
typedefstruct node *position; positionL,p,newnode;
struct node
 DATA STRUCTURE AND ALGORITHM
Module I
{
int data; positionnext;
};

Creationofthelist:
Thisroutinecreatesalistbygettingthenumberof nodesfromtheuser.
Assumen=4forthis example.
void create()
{
inti,n; L=NULL;
newnode=(struct node*)malloc(sizeof(struct node));
printf("\nEnterthenumberofnodestobeinserted\n");
scanf("%d",&n);
printf("\n Enter the data\n");
scanf("%d",&newnode->data);
newnode->next=NULL;
L=newnode;
p=L;
for(i=2;i<=n;i++)
{
newnode=(structnode*)malloc(sizeof(structnode)); scanf("%d",&newnode->data);
newnode->next=NULL;
p->next=newnode;
p=newnode;
}}

RoutinetoDeletetheList
Thisroutinedeletedtheentirelist.
VoidDelete_list(List L)
{
PositionP,temp;
P=L->next;
L->next=NULL;
while(P!=NULL)
{
ctemp=P->next;
free(P); P=temp;
}}
 DATA STRUCTURE AND ALGORITHM
Module I

A program to implement singly linked list is given as follows.

Example :
#include <iostream>
using namespace std;
struct Node
{
int data;
struct Node *next;};
struct Node* head = NULL;
void insert(intnew_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = head;
head = new_node;
}

void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<<ptr->data <<" ";
ptr = ptr->next;
}}
 DATA STRUCTURE AND ALGORITHM
Module I
int main()
{
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The linked list is: ";
display();
return 0;
}
Output
The linked list is: 9 2 7 1 3

In the above program, the structure Node forms the linked list node. It contains the data and a pointer
to the next linked list node. This is given as follows.
struct Node
{
int data;
struct Node *next;
};
The function insert() inserts the data into the beginning of the linked list. It creates a new_node and
inserts the number in the data field of the new_node. Then the new_node points to the head.
Finally the head is the new_node i.e. the linked list starts from there. This is given below.
void insert(intnew_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = head;
head = new_node;}

The function display() displays the whole linked list. First ptr points to head. Then it is continuously
forwarded to the next node until all the data values of the nodes are printed. This is given below.
 DATA STRUCTURE AND ALGORITHM
Module I
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<<ptr->data <<" ";
ptr = ptr->next;
}
}
In the function main(), first various values are inserted into the linked list by calling insert(). Then the
linked list is displayed. This is given below.
int main()
{
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The linked list is: ";
display();
return 0;
}
Advantages of SLL
1. Theelements can beaccessed usingthe nextlink.
2. OccupieslessmemorythanDLLasithasonlyonenextfield.
DisadvantagesofSLL
1. Traversalinthebackwardsisnot possible
2. Lessefficienttoforinsertionanddeletion.

STACK
 DATA STRUCTURE AND ALGORITHM
Module I

 Stack is a Linear Data Structure that follows Last In First Out (LIFO) principle.
 Insertion and deletion can be done at only one end of the stack called TOP of the stack.

Example:-Pile of coins, stack of trays

STACKADT:

TOP pointer

It will always point to the last element inserted in the stack. For empty stack, top will be

pointing to -1. (TOP = -1)

Operations on Stack (Stack ADT)

Two fundamental operations performed on the stack are PUSH and POP.

(a) PUSH:
It is the process of inserting a new element at the Top of the stack.
For every push operation:

1. Check for Full stack(overflow).

2. Increment Top by1.(Top=Top+1)
3. Insert the element X in the Top of the stack.

(b) POP:

It is the process of deleting the Top element of the stack.

For every pop operation:
 DATA STRUCTURE AND ALGORITHM
Module I
1. Check for Empty stack( underflow).
2. Delete(pop)the Top element X from the stack
3. Decrement the Topby1.(Top =Top-1)

Exceptional Conditions of stack

1. Stack Overflow

 An Attempt to insert an element X when the stack is Full, is said to be stack overflow.
 For every Push operation, we need to check this condition.

2. Stack Underflow:

 An Attempt to delete an element when the stack is empty, is said to be stack underflow.
 For every Pop operation, we need to check this condition.

A stack is an Abstract Data Type (ADT), commonly used in most programming languages.
It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates,
etc.

A real-world stack allows operations at one end only. For example, we can place or remove a card or
plate from the top of the stack only. Likewise, Stack ADT allows all data operations at one end only.
At any given time, we can only access the top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element which is
placed (inserted or added) last, is accessed first. In stack terminology, insertion operation is
called PUSH operation and removal operation is called POP operation.
 DATA STRUCTURE AND ALGORITHM
Module I

Stack Representation
The following diagram depicts a stack and its operations −

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either
be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to implement stack
using arrays, which makes it a fixed size stack implementation.

Basic Operations
Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these
basic stuffs, a stack is used for the following two primary operations −
 push() − Pushing (storing) an element on the stack.
 pop() − Removing (accessing) an element from the stack.
When data is PUSHed onto stack.
To use a stack efficiently, we need to check the status of stack as well. For the same
purpose, the following functionality is added to stacks −
 peek() − get the top data element of the stack, without removing it.
 isFull() − check if stack is full.
 isEmpty() − check if stack is empty.

At all times, we maintain a pointer to the last PUSHed data on the stack.
As this pointer always represents the top of the stack, hence named top.
The top pointer provides top value of the stack without actually removing it.
 DATA STRUCTURE AND ALGORITHM
Module I

First we should learn about procedures to support stack functions −

peek()
Algorithm of peek() function −
begin procedure peek
return stack[top]
end procedure

Implementation of peek() function in C programming language −

Example
int peek(){
return stack[top];
}

isfull()
Algorithm of isfull() function −

begin procedure isfull

if top equals to MAXSIZE

returntrue
else
returnfalse
endif

end procedure

Implementation of isfull() function in C programming language −

Example
boolisfull(){
if(top == MAXSIZE)
returntrue;
else
returnfalse;
}
 DATA STRUCTURE AND ALGORITHM
Module I

isempty()
Algorithm of isempty() function −

begin procedure isempty

if top less than 1

returntrue
else
returnfalse
endif

end procedure

Implementation of isempty() function in C programming language is slightly different. We

initialize top at -1, as the index in array starts from 0. So we check if the top is below zero or -1 to
determine if the stack is empty. Here's the code −

Example
boolisempty(){
if(top ==-1)
returntrue;
else
returnfalse;
}

Push Operation
The process of putting a new data element onto stack is known as a Push Operation. Push operation
involves a series of steps −
 Step 1 − Checks if the stack is full.
 Step 2 − If the stack is full, produces an error and exit.
 Step 3 − If the stack is not full, increments top to point next empty space.
 Step 4 − Adds data element to the stack location, where top is pointing.
 Step 5 − Returns success.
 DATA STRUCTURE AND ALGORITHM
Module I

If the linked list is used to implement the stack, then in step 3, we need to allocate space
dynamically.

Algorithm for PUSH Operation

A simple algorithm for Push operation can be derived as follows −

begin procedure push: stack, data

if stack is full
returnnull
endif
top← top +1
stack[top]← data
end procedure
Implementation of this algorithm in C, is very easy. See the following code −
Example
void push(int data){
if(!isFull()){
top= top +1;
stack[top]= data;
}else{
printf("Could not insert data, Stack is full.\n");
}
}

Pop Operation
Accessing the content while removing it from the stack, is known as a Pop Operation. In an
array implementation of pop() operation, the data element is not actually removed,
instead top is decremented to a lower position in the stack to point to the next value. But in
linked-list implementation, pop() actually removes data element and deallocates memory
space.
A Pop operation may involve the following steps −
 Step 1 − Checks if the stack is empty.
 DATA STRUCTURE AND ALGORITHM
Module I
 Step 2 − If the stack is empty, produces an error and exit.
 Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
 Step 4 − Decreases the value of top by 1.
 Step 5 − Returns success.

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

begin procedure pop: stack

if stack is empty
returnnull
endif
data← stack[top]
top← top -1
return data
end procedure

Implementation of this algorithm in C, is as follows −

Example
int pop(int data){

if(!isempty()){
data= stack[top];
top= top -1;
return data;
}else{
printf("Could not retrieve data, Stack is empty.\n");
}}
 DATA STRUCTURE AND ALGORITHM
Module I
Queue
Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both
its ends. One end is always used to insert data (enqueue) and the other is used to remove data
(dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be
accessed first.

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits
first. More real-world examples can be seen as queues at the ticket windows and bus-stops.

Queue Representation
As we now understand that in queue, we access both ends for different reasons. The following diagram
given below tries to explain queue representation as data structure −

As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and Structures. For
the sake of simplicity, we shall implement queues using one-dimensional array.
Basic Operations
Queue operations may involve initializing or defining the queue, utilizing it, and then completely
erasing it from the memory. Here we shall try to understand the basic operations associated with
queues −
enqueue() − add (store) an item to the queue.
dequeue() − remove (access) an item from the queue.
Few more functions are required to make the above-mentioned queue operation efficient.
 DATA STRUCTURE AND ALGORITHM
Module I
These are −
peek() − Gets the element at the front of the queue without removing it.
isfull() − Checks if the queue is full.
isempty() − Checks if the queue is empty.
In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing
(or storing) data in the queue we take help of rear pointer.

Let's first learn about supportive functions of a queue −

peek()
This function helps to see the data at the front of the queue. The algorithm of peek()
function is as follows −

Algorithm
begin procedure peek
return queue[front]
end procedure

Implementation of peek() function in C programming language −

Example
int peek()
{
return queue[front];
}
isfull()
As we are using single dimension array to implement queue, we just check for the rear pointer to reach
at MAXSIZE to determine that the queue is full. In case we maintain the queue in a circular linked-list,
the algorithm will differ. Algorithm of isfull() function −
Algorithm
begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
endif
end procedure
 DATA STRUCTURE AND ALGORITHM
Module I

Implementation of isfull() function in C programming language −

Example
boolisfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}

isempty()
Algorithm of isempty() function −
Algorithm
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
If the value of front is less than MIN or 0, it tells that the queue is not yet initialized, hence
empty.
Here's the C programming code −
Example
boolisempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}

Enqueue Operation
Queues maintain two data pointers, front and rear. Therefore, its operations are
comparatively difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
Step 1 − Check if the queue is full.
Step 2 − If the queue is full, produce overflow error and exit.
Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
Step 4 − Add data element to the queue location, where the rear is pointing.
Step 5 − return success.
 DATA STRUCTURE AND ALGORITHM
Module I

Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen
situations.
Algorithm for enqueue operation
procedureenqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
Implementation of enqueue() in C programming language −
Example
intenqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
end procedure
 DATA STRUCTURE AND ALGORITHM
Module I
Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data where front is pointing and
remove the data after access. The following steps are taken to perform dequeue operation −
Step 1 − Check if the queue is empty.
Step 2 − If the queue is empty, produce underflow error and exit.
Step 3 − If the queue is not empty, access the data where front is pointing.
Step 4 − Increment front pointer to point to the next available data element.
Step 5 − Return success.

Algorithm for dequeue operation

proceduredequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure

Implementation of dequeue() in C programming language −

Example
intdequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
 DATA STRUCTURE AND ALGORITHM
Module I

Evaluating Arithmetic Expressions

The stack organization is very effective in evaluating arithmetic expressions. Expressions are usually
represented in what is known as Infix notation, in which each operator is written between two
operands
(i.e., A + B).
With this notation, we must distinguish between ( A + B )*C and A + ( B * C ) by using either
parentheses or some operator-precedence convention. Thus, the order of operators and operands in an
arithmetic expression does not uniquely determine the order in which the operations are to be
performed.

1. Polish notation (prefix notation) –

It refers to the notation in which the operator is placed before its two operands. Here no
parentheses are required, i.e.,
+AB

2. Reverse Polish notation(postfix notation) –

It refers to the analogous notation in which the operator is placed after its two operands.
Again, no parentheses is required in Reverse Polish notation, i.e.,
AB+
Stack-organized computers are better suited for post-fix notation than the traditional infix
notation. Thus, the infix notation must be converted to the postfix notation. The conversion
from infix notation to postfix notation must take into consideration the operational
hierarchy.
There are 3 levels of precedence for 5 binary operators as given below:

Highest: Exponentiation (^)

Next highest: Multiplication (*) and division (/)
Lowest: Addition (+) and Subtraction (-)

For example –

Infix notation: (A-B)*[C/(D+E)+F]

Post-fix notation: AB- CDE +/F +*
Here, we first perform the arithmetic inside the parentheses (A-B) and (D+E). The division
of C/(D+E) must be done prior to the addition with F.
After that multiply the two terms inside the parentheses and bracket.
 DATA STRUCTURE AND ALGORITHM
Module I

Let’s understand infix, prefix, and postfix expression with a clear example

What is infix expression?

The typical mathematical form of expression that we encounter generally is known as infix notation.
In infix form, an operator is written in between two operands.

Eg: An expression in the form of A + B is in infix form.

 The traditional method of writing mathematical expressions is called infix expressions.

 It is of the form <operand><operator><operand>.
 As the name suggests, here the operator is fixed inside between the operands. e.g. A+B here
the plus operator is placed inside between the two operators, (A*B)/Q.
 Such expressions are easy to understand and evaluate for human beings. However, the
computer finds it difficult to parse – Information is needed about operator precedence and
associativity rules, and brackets that override these rules.
 Hence we have postfix and prefix notations which make the computer take less effort to solve
the problem.

What is postfix expression?

In postfix expression, an operator is written after its operands. This notation is also known
as “Reverse Polish notation”.
Eg: The above expression can be written in the postfix form as A B +

 The postfix expression as the name suggests has the operator placed right after the two
operands.
 It is of the form <operand><operand><operator>
 In the infix expressions, it is difficult to keep track of the operator precedence whereas here the
postfix expression itself determines the precedence of operators (which is done by the
placement of operators)i.e the operator which occurs first operates on the operand.
 E.g. PQ-C/, here – operation is done on P and Q and then / is applied on C and the previous
result.
 A postfix expression is a parenthesis-free expression. For evaluation, we evaluate it from left to
right.
 DATA STRUCTURE AND ALGORITHM
Module I
What is prefix expression?

In prefix expression, The operator is written before the operands.

Eg: The above expression can be written in the postfix form as +A B

 The prefix expression as the name suggests has the operator placed before the operand is
specified.
 It is of the form <operator><operand><operand>.
 It works entirely in the same manner as the postfix expression.
 While evaluating a prefix expression, the operators are applied to the operands immediately on
the right of the operator.
 For evaluation, we evaluate it from left to right. Prefix expressions are also called polish
notation.

Some more examples:-

Infix expression Prefix expression Postfix expression

A+B*C+D ++A*BCD ABC*+D+
(A + B) * (C + D) *+AB+CD AB+CD+*
A*B+C*D +*AB*CD AB*CD*+
A+B+C+D +++ABCD AB+C+D+

We can convert the infix expression to prefix as well as postfix and vice versa.

Now we need to calculate the value of these arithmetic operations by using a stack.
The procedure for getting the result is:

1. Convert the expression in Reverse Polish notation( post-fix notation).

2. Push the operands into the stack in the order they appear.
3. When any operator encounters then pop two topmost operands for executing the
operation.
4. After execution push the result obtained into the stack.
5. After the complete execution of expression, the final result remains on the top of the
stack.

For example –

Infix notation: (2+4) * (4+6)

Post-fix notation: 2 4 + 4 6 + *
Result: 60
 DATA STRUCTURE AND ALGORITHM
Module I
The stack operations for this expression evaluation is shown below:

Polynomial Manipulation
Linked lists can be used to represent polynomials and the different operations that can be
performed on them

Polynomial Representation

Consider a polynomial 6x3+9x2+7x+1.

Every individual terminal polynomial consists of two parts, a coefficient and a power.
Here, 6, 9, 7, and 1 are the coefficients of the terms that have 3, 2, 1, and 0 as their powers
respectively.
Every term of a polynomial can be represented as a node of the linked list

Linked representation of a polynomial

Polynomial manipulations such as addition, subtraction & differentiation etc.. can be

performed using linked list
 DATA STRUCTURE AND ALGORITHM
Module I

Declaration for Linked list implementation of Polynomial ADT

Struct poly
{
int coeff;
int power;
Struct poly* Next;
}*list1,*list2,*list3;

Creation of the Polynomial

Poly create(poly *head, poly *newnode)
{
poly *ptr;
if(head==NULL)
{
head=newnode;
return(head);
}
else
{
ptr=head;
while(ptr-> next!=NULL)
ptr=ptr->next;
ptr->next=newnode;
}
return(head);
}

Addition of Polynomials:
To add two polynomials, we need to scan them once.
If we find terms with the same exponent in the two polynomials,
Then we add the coefficients; otherwise, we copy the term of larger exponent into the sum
and go on. When we reach at the end of one of the polynomial, then remaining part of the
other is copied into the sum.
To add two polynomials, follow the following steps:
 Read two polynomials.
 Add them.

Display the resultant polynomial.

Addition of Polynomials:
Void add()
{
poly *ptr1, *ptr2, *newnode;
ptr1=list1;
ptr2=list2;
while(ptr1!=NULL&&ptr2!=NULL)
{
newnode=malloc(sizeof(struct poly));
if(ptr1->power==ptr2->power)
 DATA STRUCTURE AND ALGORITHM
Module I
{
newnode->coeff = ptr1->coeff + ptr2->coeff;
newnode->power=ptr1->power;
newnode->next=NULL;
list3=create(list3,newnode);
ptr1=ptr->next;
ptr2=ptr2->next;
}
else
{
if(ptr1->power>ptr2->power)
{
newnode->coeff = ptr1->coeff newnode->power=ptr1->power;
newnode->next=NULL;
list3=create(list3,newnode);
ptr1=ptr1->next;
}
else
{
newnode->coeff=ptr2->coeff;
newnode->power=ptr2->power;
newnode->next=NULL;
list3=create(list3,newnode);
ptr2=ptr2->next;
}}}

FOR SUBTRACTION OF POLYNOMIALS,

Add this statement in the above program ,
new node->coeff=ptr1->coeff-ptr2->coeff.

Let's take an example-

If the polynomial is 2x2+3x+4, then it is written in the form of 2x2+3x1+4x0 and represented it using a
linked list. In the diagram, AON means "address of next node".

Linked List Representation

 DATA STRUCTURE AND ALGORITHM
Module I

Addition of polynomials represented as linked lists

Consider the polynomials 12x4+2x2+10 and 9x3+8x2+x.

POLYNOMIAL ADDITION