PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.

E - CSE
UNIT I - LINEAR DATA STRUCTURES – LIST, STACK AND QUEUE

List ADT– Singly Linked Lists – Doubly Linked Lists-Circular Linked List– Applications of Lists : l
Manipulation on Polynomia –Stack ADT –Implementation of Stack – Applications of Stack – Balancing
Symbols - Conversion of Infix to postfix expression – Expression Evaluation - Queue ADT - Circular
Queue – Double Ended Queue – Applications of queues.

Data:
A collection of facts, concepts, figures, observations, occurrences or instructions in a
formalized manner.
Information:
The meaning that is currently assigned to data by means of the conventions applied to
those data(i.e. processed data)
Record:
Collection of related fields.
Data type:
Set of elements that share common set of properties used to solve a program.
Data Structures:
Data Structure is the way of organizing, storing, and retrieving data and their relationship
with each other.
Characteristics of data structures:
1. It depicts the logical representation of data in computer memory.

2. It represents the logical relationship between the various data elements.

3. It helps in efficient manipulation of stored data elements.

4. It allows the programs to process the data in an efficient manner.

Operations on Data Structures:

1.Traversal

2.Search

3.Insertion

4.Deletion

23CS1302 1 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
CLASSIFICATION OF DATA STRUCTURES

DATA STRUCTURES

PRIMARY DATA STRUCTURES SECONDARY DATA STRUCTURES

INT, CHAR, FLOAT DOUBLE LINEAR DATA NON LINEAR

STRUCTURES DATA
STRUCTURES

TREES GRAPHS
LISTS ARRAYS STACKS QUEUE

Primary Data Strucutres/Primitive Data Structures:

Primitive data structures include all the fundamental data structures that can be directly manipulated by
machine-level instructions. Some of the common primitive data structures include integer, character, real,
boolean etc

Secondary Data Structures/Non-Primitive Data Structures:

Non-primitive data structures refer to all those data structures that are derived from one or more primitive
data structures. The objective of creating non-primitive data structures is to form sets of homogeneous or
heterogeneous data elements.

Linear Data Structures:

Linear data structures are data strucutres in which, all the data elements are arranged in i, linear or
sequential fashion. Examples of data structures include arrays, stacks, queues, linked lists, etc.

Non-Linear Structures:
In non-linear data strucutres, 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.

23CS1302 2 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
Static and dynamic data structure:

Static Ds:
If a ds is created using static memory allocation, ie. ds formed when the number of data items are known
in advance ,it is known as static data static ds or fixed size ds

Dynamic Ds:
If the ds is created using dynamic memory allocation i.e ds formed when the number of data items are not
known in advance is known as dynamic ds or variable size ds.

Application of data structures:

Data structures are widely applied in the following areas:

 Compiler design
 Operating system
 Statistical analysis package
 DBMS
 Numerical analysis
 Simulation
 Artificial intelligence
 Graphics

ABSTRACT DATA TYPES (ADTS):

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 ADT consists of data together with functions that operate on that data.
Advantages/Benefits of ADT:
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.

THE LIST AI)T:

List is an ordered set of elements.

The general form of the list is A1 ,A2 , ……,AN

A1 - First element of the list

A2- 1st element of the list
N –Size of the list

If the element at position i is Ai, then its successor is Ai+1 and its predecessor is Ai-1

23CS1302 3 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
Various operations performed on List

1. Insert (X, 5)- Insert the element X after the position 5.

2. Delete (X) - The element X is deleted

3. Find (X) - Returns the position of X.

4. Next (i) - Returns the position of its successor element i+1.

5. Previous (i) Returns the position of its predecessor i-1.

6. Print list - Contents of the list is displayed.

7. Makeempty- Makes the list empty.

Implementation of list ADT:

1. Array based Implementation

2. Linked List based implementation

Differences between Array based and Linked based implementation

Array Linked List

Definition Array is a collection of elements Linked list is an ordered collection
having same data type with common of elements which are connected by
name links/pointers
Access Elements can be accessed using Sequential access
index/subscript, random access
Memory structure Elements are stored in contiguous Elements are stored at available
memory locations memory space
Insertion & Deletion Insertion and deletion takes more time Insertion and deletion are fast and
in array easy
Memory Allocation Memory is allocated at compile time Memory is allocated at run time i.e
i.e static memory allocation 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

23CS1302 4 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE

Linked list based implementation:

Linked Lists:

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,
Data field-The data field contains the actual data of the elements to be stored in the list Next field- The
next field contains the address of the next node in the list

DATA NEXT

A Linked list node

Advantages of Linked list:

1.Insertion and deletion of elements can be done efficiently
2.It uses dynamic memory allocation
3.Memory utilization is efficient compared to arrays
Disadvantages of linked list:
1.Linked list does not support random access
2.Memory is required to store next field
3.Searching takes time compared to arrays
Types of Linked List
1. Singly Linked List or One Way List
2. Doubly Linked List or Two-Way Linked List
3. Circular Linked List
Dynamic allocation
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

23CS1302 5 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE

To use dynamic memory allocation functions, you must include the header file stdlib.h.
malloc()
The malloc function reserves a block of memory of specified size and returns a pointer of type void. This
means that we can assign it to any type of pointer.
The general syntax of malloc() is ptr =(cast-type*)malloc(byte-size);
where ptr is a pointer of type cast-type. malloc() returns a pointer (of cast type) to an area of memory
with size byte-size.
calloc():
calloc() function is another function that reserves memory at the run time. It is normally used to request
multiple blocks of storage each of the same size and then sets all bytes to zero. calloc() stands for
contiguous memory allocation and is primarily used to allocate memory for arrays. The syntax of calloc()
can be given as:
ptr=(cast-type*) calloc(n,elem-size);
The above statement allocates contiguous space for n blocks each of size elem-size bytes. The only
difference between malloc() and calloc() is that when we use calloc(), all bytes are initialized to zero.
calloc() returns a pointer to the first byte of the allocated region.

free():
The free() is used to release the block of memory.
Syntax:
The general syntax of the free()function is, free(ptr);
where ptr is a pointer that has been created by using malloc() or calloc(). When memory is deallocated
using free(), it is returned back to the free list within the heap.

realloc():
At times the memory allocated by using calloc() or malloc() might be insufficient or in excess. In both
the situations we can always use realloc() to change the memory size already allocated by calloc() and
malloc(). This process is called reallocation of memory. The general syntax for realloc() can be given as,
ptr = realloc(ptr,newsize);

The function realloc() allocates new memory space of size specified by newsize to the pointer variable
ptr. It returns a pointer to the first byte of the memory block. The allocated new block may be or may not

23CS1302 6 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
be at the same region. Thus, we see that realloc() takes two arguments. The first is the pointer referencing
the memory and the second is the total number of bytes you want to reallocate.

Singly Linked List

A singly linked list is a linked list in which each node contains only one link field pointing to the next
node in the list

SLL

SLL with a Header

Basic operations on a singly-linked list are:
1. Insert – Inserts a new node in the list.
2. Delete – Deletes any node from the list.
3. Find – Finds the position( address ) of any node in the list.
4. FindPrevious - Finds the position( address ) of the previous node in the list.
5. FindNext- Finds the position( address ) of the next node in the list.
6. Display-display the date in the list
7. Search-find whether a element is present in the list or not

Declaration of Linked List

void insert(int X,List L,position P);
void find(List L,int X);
void delete(int x , List L);
typedef struct node *position;
position L,p,newnode;
struct node

23CS1302 7 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
{
int data; position next;
};
Creation of the list:
This routine creates a list by getting the number of nodes from the user. Assume n=4 for this example.
void create()
{
int i,n; L=NULL;
newnode=(struct node*)malloc(sizeof(struct node));
printf("\n Enter the number of nodes to be inserted\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=(struct node *)malloc(sizeof(struct node));
scanf("%d",&newnode->data);
newnode->next=NULL;
p->next=newnode;
p=newnode;
}
}

Initially the list is empty

List L
Null

L
Insert(10,List L)- A new node with data 10 is inserted and the next field is updated to NULL. The next
field of previous node is updated to store the address of new node.

Insert(20,L) - A new node with data 20 is inserted and the next field is updated to NULL. The next field
of previous node is updated to store the address of new node.

10 20 Null

23CS1302 8 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE

L P

Insert(30,L) - A new node with data 30 is inserted and the next field is updated to NULL. The next field
of previous node is updated to store the address of new node.

10 20 30 Null

L P

Case 1:Routine to insert an element in list at the beginning

void insert(int X, List L, position p)
{
p=L;
newnode=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data to be inserted\n");
scanf("%d",&newnode->data); newnode->next=L; L=newnode;

Case 2:Routine to insert an element in list at Position

This routine inserts an element X after the position P.
Void Insert(int X, List L, position p)
{
position newnode;
newnode =(struct node*) malloc( sizeof( struct node ));
if( newnode = = NULL )
Fatal error( “ Out of Space ” );
else
{
Newnode -> data = x ;
Newnode -> next = p ->next ;
P -> next = newnode ;
}
}

23CS1302 9 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
Insert(25,L, P) - A new node with data 25 is inserted after the position P and the next field is updated to
NULL. The next field of previous node is updated to store the address of new node.

Case 3:Routine to insert an element in list at the end of the list

void insert(int X, List L, position p)

{
p=L;
newnode=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data to be inserted\n");
scanf("%d",&newnode->data);
while(p->next!=NULL)
p=p->next;
newnode->next=NULL;
p->next=newnode;
p=newnode;
}

Routine to check whether a list is Empty

This routine checks whether the list is empty .If the lis t is empty it returns 1

int IsEmpty( List L )

{
Null
if ( L -> next = = NULL )
return(1); L
}

Routine to check whether the current position is last in the List

23CS1302 10 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
This routine checks whether the current position p is the last position in the list. It returns 1 if position p
is the last position
int IsLast(List L , position p)
{
if( p -> next= =NULL) return(1);
}

NULL

L P
Routine to Find the Element in the List:
This routine returns the position of X in the list L

position find(List L, int X)

{
position p;
p=L->next;
while(p!=NULL && p->data!=X)
p=p->next;
return(p);
}

Find(List L, 20) - To find an element X traverse from the first node of the list and move to the next with
the help of the address stored in the next field until data is equal to X or till the end of the list

Find Previous
It returns the position of its predecessor.

position FindPrevious (int X, List L)

{
position p; p = L;
while( p -> next ! = NULL && p -> next -> data! = X )
p = p -> next;
return P;
}

23CS1302 11 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE

Routine to find next Element in the List

It returns the position of successor.

void FindNext(int X, List L)

{
position P; P=L->next;
while(P!=NULL && P->data!=X)
P = P->next;
return P->next;
}

Routine to Count the Element in the List:

This routine counts the number of elements in the list void count(List L)
{
P = L -> next; while( p != NULL )
{
count++;
p = p -> next;
}
print count;
}

Routine to Delete an Element in the List:

It delete the first occurrence of element X from the list L void Delete( int x , List L){
position p, Temp;
p = FindPrevious( X, L);
if( ! IsLast (p, L))
{
temp = p -> next;
P -> next = temp -> next;

23CS1302 12 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
free ( temp );
}}

Routine to Delete the List

This routine deleted the entire list.

void Delete_list(List L)
{
position P,temp;
P=L->next;
L->next=NULL;
while(P!=NULL)
{
temp=P->next;
free(P);
P=temp;
}
}

Advantages of SLL
1.The elements can be accessed using the next link

23CS1302 13 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
2.Occupies less memory than DLL as it has only one next field.

Disadvantages of SLL
1.Traversal in the backwards is not possible 2.Less efficient to for insertion and deletion.

Doubly-Linked List
A doubly linked list is a linked list in which each node has three fields namely Data, Next, Prev.

Data-This field stores the value of the element

Next-This field points to the successor node in the list

Prev-This field points to the predecessor node in the list

PREV DATA NEXT

DLL NODE

DOUBLY LINKED LIST

Basic operations of a doubly -linked list are:
1. Insert – Inserts a new element at the end of the list.
2. Delete – Deletes any node from the list.
3. Find – Finds any node in the list.

4. Print – Prints the list

Declaration of DLL Node

typedef struct node *position ;
struct node
{

23CS1302 14 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
int data;
position prev;
position next;
};

Creation of list in DLL

Initially the list is empty. Then assign the first node as head. newnode->data=X;

newnode->next=NULL; newnode->prev=NULL; L=newnode;

If we add one more node in the list,then create a newnode and attach that node to the end of the list.

L->next=newnode; newnode->prev=L;

Routine to insert an element in a DLL at the beginning

void Insert (int x, list L, position P)

{
struct node *Newnode;
if(pos==1)
P=L;
Newnode = (struc node*)malloc (sizeof(struct node));
if (Newnode! = NULL)
Newnode->data= X;
Newnode ->next= L ->next;
L->next ->prev=Newnode
L->next = Newnode;
Newnode ->prev = L;
}

Routine to insert an element in a DLL any position:

void Insert (int x, list L, position P)

{
struct node *Newnode;
Newnode = (struc node*)malloc (sizeof(struct node));
if (Newnode! = NULL)
Newnode->data= X;
Newnode ->next= P ->next;
P->next ->prev=Newnode
P ->next = Newnode;
Newnode ->prev = P:
}

23CS1302 15 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE

Routine to insert an element in a DLL at the end:

void insert(int X, List L, position p)

{
p=L;
newnode=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data to be inserted\n");
scanf("%d",&newnode->data);
while(p->next!=NULL)
p=p->next;
newnode->next=NULL;
p->next=newnode;
newnode->prev=p;
}

Routine for deleting an element:

void Delete (int x ,List L)

Position p , temp;
P = Find( x, L );
if(P==L->next)
temp=L;
L->next=temp->next;
temp->next->prev=L;
free(temp);

elseif( IsLast( p, L ) )

{
temp = p;
p -> prev -> next = NULL;
free(temp);
}
else
{

23CS1302 16 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
temp = p;
p -> prev -> next = p -> next;
p -> next -> prev = p -> prev;
free(temp);
}

Routine to display the elements in the list:

void Display( List L )
{
P = L -> next ;
while ( p != NULL)
{
printf(“%d”, p -> data ;
p = p -> next ;
}
printf(“ NULL”);
}
Routine to search whether an element is present in the list

void find()
{
int a,flag=0,count=0; if(L==NULL)
printf(“\nThe list is empty”);
else
{
printf(“\nEnter the elements to be searched”);
scanf(“%d”,&a);
for(P=L;P!=NULL;P=P->next)
{
count++;
if(P->data==a)
{
flag=1;
printf(“\nThe element is found”);
printf(“\nThe position is %d”,count);
break;
}
}

Advantages of DLL:

The DLL has two pointer fields. One field is prev link field and another is next link field. Because of
these two pointer fields we can access any node efficiently whereas in SLL only one link field is there
which stores next node which makes accessing of any node difficult.

Disadvantages of DLL:

23CS1302 17 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE

The DLL has two pointer fields. One field is prev link field and another is next link field. Because of
these two pointer fields, more memory space is used by DLL compared to SLL

Applications of List:
1.Polynomial ADT

2.Radix sort

3.Multilist

Polynomial Manipulation
Polynomial manipulations such as addition, subtraction & differentiation etc.. can be
performed using linked list.

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*head1,poly*newnode1)
{
poly *ptr; if(head1==NULL)
{
head1=newnode1; return (head1);
}
else
{
ptr=head1;
while(ptr->next!=NULL)
ptr=ptr->next;
ptr->next=newnode1;
}
return(head1);
}
Addition of two polynomials
void add()
{
poly *ptr1, *ptr2, *newnode ;

23CS1302 18 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
ptr1= list1;
ptr2 = list2;
while( ptr1 != NULL && ptr2 != NULL )
{
newnode = (struct poly*)malloc( sizeof ( struct poly ));
if( ptr1 -> power = = ptr2 -> power )

{
newnode -> coeff = ptr1 -> coeff + ptr2 -> coeff;
newnode -> power = ptr1 -> power ;
newnode -> next = NULL;
list3 = create( list3, newnode );
ptr1 = ptr1 -> 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;
}}}

Subtraction of two polynomial

void sub()
{
poly *ptr1, *ptr2, *newnode; ptr1 = list1;
ptr2 = list2;
while( ptr1 != NULL && ptr2 != NULL )
{
newnode = (struct poly*)malloc( sizeof (struct poly)) ;
if(ptr1->power==ptr2->power)
{
newnode->coeff=(ptr1-coeff)-(ptr2->coeff);
newnode->power=ptr1->power;
newnode->next=NULL;

23CS1302 19 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
list3=create(list3,newnode);
ptr1=ptr1->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;
}
}
}

Polynomial Differentiation:

void diff()

{
poly *ptr1, *newnode; ptr1 = list1;
while( ptr1 != NULL)
{
newnode = (struct poly*)malloc( sizeof (struct poly));
newnode->coeff=(ptr1-coeff)*(ptr1->power);
newnode->power=ptr1->power-1;
newnode->next=NULL;
list3=create(list3,newnode);
ptr1=ptr1->next;
}
}

Polynomial Multiplication
void mul()

{
poly *ptr1, *ptr2, *newnode ; ptr1= list1;
ptr2 = list2;

23CS1302 20 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
while( ptr1 != NULL && ptr2 != NULL )
{
newnode = (struct poly*)malloc( sizeof ( struct poly ));
if( ptr1 -> power = = ptr2 -> power )

{
newnode -> coeff = ptr1 -> coeff * ptr2 -> coeff;
newnode -> power = ptr1 -> power+ptr2->power;
newnode -> next = NULL;
list3 = create( list3, newnode );
ptr1 = ptr1 -> next;
ptr2 = ptr2 -> next;

}
}
}

STACK

 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

STACK ADT

STACK MODEL

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.

23CS1302 21 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
(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 by 1. (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:

1. Check for Empty stack ( underflow ).

2. Delete (pop) the Top element X from the stack
3. Decrement the Top by 1. (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.

Implementation of Stack

Stack can be implemented in 2 ways.

1. Static Implementation (Array implementation of Stack)

2. Dynamic Implementation (Linked List Implementation of Stack)

Linked list implementation of Stack

 Stack elements are implemented using SLL (Singly Linked List) concept.
 Dynamically, memory is allocated to each element of the stack as a node.
Type Declarations for Stack using SLL
struct node;
typedef struct node *stack;
typedef struct node *position; stack S;

23CS1302 22 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
struct node{ int data; position next;};
int IsEmpty(Stack S);

void Push(int x, Stack S);

void pop(Stack S);

int TopElement(Stack S);
(i) Stack Empty Operation:
 Initially Stack is Empty.
 With Linked List implementation, Empty stack is represented as S -> next = NULL.
 It is necessary to check for Empty Stack before deleting ( pop) an element from the stack.
Routine to check whether the stack is empty S

int IsEmpty( Stack S)

HEADER NULL
{

if ( S -> next = = NULL)

EMPTY STACK
return ( 1 );
}

(ii) Push Operation

 It is the process of inserting a new element at the Top of the stack.
 With Linked List implementation, a new element is always inserted at the Front of the List.(i.e.)
S -> next.
 It takes two parameters. Push(X, S) the element X to be inserted at the Top of the StackS.
 Allocate the memory for the newnode to be inserted.
 Insert the element in the data field of the newnode.
 Update the next field of the newnode with the address of the next node which is stored in the
S -> next.
S

Header

30 20 10 NULL

40

newnode
Before Insertion

23CS1302 23 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE

Push routine /*Inserts element at front of the list

void push(int X, Stack S)

{

Position newnode, Top;

newnode = malloc (sizeof( struct node ) );
newnode -> data = X;
newnode -> next = S -> next;
S -> next = newnode;
Top = newnode;
}

Header

40 30 20 10 NULL

After Insertion

TOP
(i) Pop Operation
 It is the process of deleting the Top element of the stack.
 With Linked List implementations, the element at the Front of the List (i.e.)
S -> next is always deleted.
 It takes only one parameter. Pop(X).The element X to be deleted from the Front of the List.
 Before deleting the front element in the list, check for Empty Stack.
 If the Stack is Empty, deletion is not possible.
 Otherwise, make the front element in the list as “temp”.
 Update the next field of header.

23CS1302 24 DATA STRUCTURES

PANIMALAR ENGINEERING COLLEGE II YEAR / III SEM B.E - CSE
 Using free ( ) function, Deallocate the memory allocated for temp node.

Header

40 30 20 10 NULL

TOP
Before Deletion

Pop routine /*Deletes the element at front of list

void Pop( Stack S )

{

Position temp, Top;

Top = S -> next;
if( S -> next = = NULL)
Error(“empty stack! Pop not possible”);
else
{

Temp = S -> next;

S -> next = temp -> next;
free(temp);
Top = S -> next;
}}

23CS1302 25 DATA STRUCTURES

R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Header

40 30 20 10 NULL

HEADER

30 20 10 NULL

TOP
After Deletion

(i) Return Top Element

 Pop routine deletes the Front element in the List.
 If the user needs to know the last element inserted into the stack, then the user can return the Top
element of the stack.
 To do this, first check for Empty Stack.
 If the stack is empty, then there is no element in the stack.
 Otherwise, return the element present in the S -> next -> data in the List.

Routine to Return Top Element

int TopElement(Stack S)

if(S->next==NULL)

error(“Stack is empty”);
return 0;
else
return S->next->data;
}
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE
S

Header

40 30 20 10 NULL

Applications of Stack

The following are some of the applications of stack:

1. Evaluating the arithmetic expressions

o Conversion of Infix to Postfix Expression
o Evaluating the Postfix Expression
2. Balancing the Symbols
3. Function Call
4. Tower of Hanoi
5. 8 Queen Problem

Evaluating the Arithmetic Expression

There are 3 types of Expressions
 Infix Expression
 Postfix Expression
 Prefix Expression

INFIX:

The arithmetic operator appears between the two operands to which it is being applied.

TOP
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE
POSTFIX:

The arithmetic operator appears directly after the two operands to which it applies. Also called reverse
polish notation.

PREFIX:
The arithmetic operator is placed before the two operands to which it applies. Also called polish notation.

Evaluating Arithmetic Expressions

1. Convert the given infix expression to Postfix expression

2. Evaluate the postfix expression using stack.

Algorithm to convert Infix Expression to Postfix Expression:

Read the infix expression one character at a time until it encounters the delimiter “#” Step 1: If the

character is an operand, place it on the output.

Step 2: If the character is an operator, push it onto the stack. If the stack operator has a higher or equal
priority than input operator then pop that operator from the stack and place it onto the output.

Step 3:If the character is left parenthesis, push it onto the stack

Step 4:If the character is a right parenthesis, pop all the operators from the stack till it encounters left
parenthesis, discard both the parenthesis in the output.

Infix: A+B*C/(E-F)#

Input String Output Stack Operator Stack

A+B*C/(E-F) A

A+B*C/(E-F) A +
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE
Input String Output Stack Operator Stack

A+B*C/(E-F) AB +

A+B*C/(E-F) AB +*

A+B*C/(E-F) ABC +*

A+B*C/(E-F) ABC* +/

A+B*C/(E-F) ABC* +/(

A+B*C/(E-F) ABC*E +/(

A+B*C/(E-F) ABC*E +/(-

A+B*C/(E-F) ABC*EF +/(-

A+B*C/(E-F) ABC*EF- +/

A+B*C/(E-F) ABC*EF-/+

Towers of Hanoi

Towers of Hanoi can be easily implemented using recursion. Objective of the problem is moving
a collection of N disks of decreasing size from one pillar to another pillar. The movement of the disk is
restricted by the following rules.

Rule 1 : Only one disk could be moved at a time.

Rule 2 : No larger disk could ever reside on a pillar on top of a smaller disk.

Rule 3 : A 3rd pillar could be used as an intermediate to store one or more disks, while they were being

moved from source to destination.

Tower 1 Tower 2 Tower 3

A B C
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Initial Setup of Tower of HanoiRecursive Solution

N - represents the number of disks.

Step 1. If N = 1, move the disk from A to C.

Step 2. If N = 2, move the 1st disk from A to B. Then move the 2nd disk from A to C, The move the 1st
disk from B to C.

Step 3. If N = 3, Repeat the step (2) to more the first 2 disks from A to B using C as intermediate. Then
the 3rd disk is moved from A to C. Then repeat the step (2) to move 2 disks from B to C using A as
intermediate.

In general, to move N disks. Apply the recursive technique to move N - 1 disks from A to B using C as
an intermediate. Then move the Nth disk from A to C. Then again apply the recursive technique to move
N - 1 disks from B to C using A as an intermediate.

Recursive Routine for Towers of Hanoi

void hanoi (int n, char s, char d, char i)
{
/* n no. of disks, s source, d destination i intermediate */ if (n = = 1)
{
print (s, d); return;
}
else
{
hanoi (n - 1, s, i, d);
print (s, d)
hanoi (n-1, i, d, s);
return;
}
}
Source Pillar Intermediate Pillar Destination Pillar

Tower 1 Tower 2 Tower 3

1. Move Tower1 to Tower3

R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE
Tower 1 Tower 2 Tower 3

2. Move Tower1 to Tower2

Tower 1 Tower 2 Tower 3

3. Move Tower 3 to Tower 2

Tower 1 Tower 2 Tower 3

4. Move Tower 1 to Tower 3

Tower 1 Tower 2 Tower 3

5. Move Tower 2 to Tower 1

Tower 1 Tower 2 Tower 3

6. Move Tower 2 to Tower 3

Tower 1 Tower 2 Tower 3

7. Move Tower 1 to Tower 3

Tower 1
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Since disks are moved from each tower in a LIFO manner, each tower may be considered as a
Stack. Least Number of moves required solving the problem according to our algorithm is given by,

O(N)=O(N-1)+1+O(N-1) =2N-1

Function Calls

When a call is made to a new function all the variables local to the calling routine need to be
saved, otherwise the new function will overwrite the calling routine variables. Similarly the current
location address in the routine must be saved so that the new function knows where to go after it is
completed.

Main() Balance() Push()

Call
balance()

Recursive Function to Find Factorial

int fact(int n)
{

int S;
if(n==1)
return(1);
else
S = n * fact( n – 1 );
return(S)
}

Balancing the Symbols

 Compilers check the programs for errors, a lack of one symbol will cause an error.
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE
 A Program that checks whether everything is balanced.
 Every right parenthesis should have its left parenthesis.
 Check for balancing the parenthesis brackets braces and ignore any other character.

Algorithm for balancing the symbols

Read one character at a time until it encounters the delimiter `#'.
Step 1 : - If the character is an opening symbol, push it onto the stack.
Step 2 : - If the character is a closing symbol, and if the stack is empty report an error as missing opening
symbol.
Step 3 : - If it is a closing symbol and if it has corresponding opening symbol in the stack, POP it from
the stack. Otherwise, report an error as mismatched symbols.
Step 4 : - At the end of file, if the stack is not empty, report an error as Missing closing symbol.
Otherwise, report as balanced symbols.

Example for Balanced symbols:

E.g. Let us consider the expression ((B*B)-{4*A*C}/[2*A]) #

((B*B)-{4*A*C}/[2*A]) #

Read Character Stack

( (
(
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

)
(

{
(
{

[ (

]
(

Empty stack, hence the symbols the balanced in the given expression.
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE
Example for unbalanced symbols:

QUEUES:
 Queue is a Linear Data Structure that follows First in First out (FIFO) principle.
 Insertion of element is done at one end of the Queue called “Rear “end of the Queue.
 Deletion of element is done at other end of the Queue called “Front “end of the Queue.
 Example: - Waiting line in the ticket counter.

Front End
RearEnd

QUEUE Q
Deletion Insertion
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE
Queue Model

Front Pointer:-

It always points to the first element inserted in the Queue.

Rear Pointer:-
It always points to the last element inserted in the Queue.

For Empty Queue:-

Front (F) = - 1

Rear (R) = - 1

Operations on Queue

Fundamental operations performed on the queue are

1. EnQueue
2. DeQueue

(i) EnQueue operation:-

 It is the process of inserting a new element at the rear end of the Queue.
 For every EnQueue operation
o Check for Full Queue
o If the Queue is full, Insertion is not possible.
o Otherwise, increment the rear end by 1 and then insert the element in the rear end
of the Queue.

(ii) DeQueue Operation:-

 It is the process of deleting the element from the front end of the queue.
 For every DeQueue operation
o Check for Empty queue
o If the Queue is Empty, Deletion is not possible.
o Otherwise, delete the first element inserted into the queue and then increment the
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE
front by 1.
Exceptional Conditions of Queue

 Queue Overflow
 Queue Underflow

(i) Queue Overflow:

 An Attempt to insert an element X at the Rear end of the Queue when the Queue is full is said to
be Queue overflow.
 For every Enqueue operation, we need to check this condition.

(ii) Queue Underflow:

 An Attempt to delete an element from the Front end of the Queue when the Queue is empty is said
to be Queue underflow.
 For every DeQueue operation, we need to check this condition.

Implementation of Queue
Queue can be implemented in two ways.

Implementation using Array (Static Queue)

Implementation using Linked List (Dynamic Queue)

Linked List Implementation of Queue


 Queue is implemented using SLL (Singly Linked List ) node.
 Enqueue operation is performed at the end of the Linked list and DeQueue operation is performed
at the front of the Linked list.
 With Linked List implementation, for Empty queue

Front = NULL & Rear = NULL

Linked List representation of Queue with 4 elements

R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE
Q

Header

10 20 30 40 NULL

Front Rear

Declaration for Linked List Implementation of Queue ADT

struct node;
typedef struct node * Queue;
typedef struct node * position;
int IsEmpty (Queue Q);
Queue CreateQueue (void);
void MakeEmpty (Queue Q);
void Enqueue (int X, Queue Q);
void Dequeue (Queue Q);
struct node
{

int data ;
position next;
}* Front = NULL, *Rear = NULL;

(i) Queue Empty Operation:

 Initially Queue is Empty.
 With Linked List implementation, Empty Queue is represented as S -> next = NULL.
 It is necessary to check for Empty Queue before deleting the front element in the Queue.

ROUTINE TO CHECK WHETHER THE QUEUE IS EMPTY

Empty Queue
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

int IsEmpty (Queue Q

{ Q

Header NULL
if ( Q Next = = NULL)

return (1);

(ii) EnQueue Operation

 It is the process of inserting a new element at the Rear end of the Queue.
 It takes two parameters, EnQueue ( int X , Queue Q ). The elements X to be inserted into the
Queue Q.
 Using malloc ( ) function allocate memory for the newnode to be inserted into the Queue.
 If the Queue is Empty, the newnode to be inserted will become first and last node in the list.
Hence Front and Rear points to the newnode.
 Otherwise insert the newnode in the Rear -> next and update the Rear pointer.
R INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Routine to EnQueue an Element in Queue

void EnQueue ( int X, Queue Q )

{
Q
struct node *newnode;
newnode = malloc (sizeof (struct node)); Header NULL
if (Rear = = NULL)
{
Empty Queue
newnode data = X;
newnode next = NULL; Before Insertion
Q -> next = newnode;
Front = newnode;
Rear = newnode;
} Header
Q
else
{ 10 NULL

newnode data = X;
newnode next = NULL;
Rear next = newnode;
Rear = newnode;
}

(iii) DeQueue Operation

 It is the process of deleting the front element fro m the Queue.

 It takes one parameter, Dequeue ( Queue Q ). Always element in the front (i.e) element pointed by
Q -> next is deleted always.
 Element to be deleted is made “temp”.
 If the Queue is Empty, then deletion is not possible.
 If the Queue has only one element, then the element is deleted and Front and Rear pointer is made
NULL to represent Empty Queue.
 Otherwise, Front element is deleted and the Front pointer is made to point to next node in the list.
 The free ( ) function informs the compiler that the address that temp is pointing to, is unchanged but
the data present in that address is now undefined.
PANIMALAR ENGINEERING COLLEGE II YEAR/III SEM B.E-CSE

Header

20 30 40 NULL

Front Rear

Routine to DeQueue an Element from the Queue

void DeQueue ( Queue Q )

{

struct node *temp;

if ( Front = = NULL )
Error (“Empty Queue!!! Deletion not possible.” );
else if (Front = = Rear)
{
temp = Front;
Q -> next = NULL;
Front = NULL;
Rear = NULL;
free ( temp );
}
else
{
temp = Front;
Q -> next = temp -> next; Front = Front Next; free (temp);
}
}

23CS1302 41 DATA STRUCTURE

PANIMALAR ENGINEERING COLLEGE II YEAR/III SEM B.E-CSE

Applications of Queue

1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life, Call Center phone systems will use Queues, to hold people calling them in an order,
until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they
arrive, First come first served.
4. Batch processing in operating system.
5. Job scheduling Algorithms like Round Robin Algorithm uses Queue.

Drawbacks of Queue (Linear Queue)

 With the array implementation of Queue, the element can be deleted logically only by moving
Front = Front + 1.
 Here the Queue space is not utilized fully.

To overcome the drawback of this linear Queue, we use Circular Queue.

CIRCULAR QUEUE

enqueue(data)
 Create a struct node type node.
 Insert the given data in the new node data section and NULL in address section.
 If Queue is empty then initialize front and rear from new node.
 Queue is not empty then initialize rear next and rear from new node.
 New node next initialize from front
dequeue()
 Check if queue is empty or not.
 If queue is empty then dequeue is not possible.
 Else Initialize temp from front.
 If front is equal to the rear then initialize front and rear from null.
 Print data of temp and free temp memory.

23CS1302 42 DATA STRUCTURE

PANIMALAR ENGINEERING COLLEGE II YEAR/III SEM B.E-CSE

 If there is more than one node in Queue then make front next to front then initialize rear next
from front.

 Print temp and free temp.

print()
 Check if there is some data in the queue or not.
 If the queue is empty print “No data in the queue.”
 Else define a node pointer and initialize it with front.
 Print data of node pointer until the next of node pointer becomes NULL.

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

struct node *front = NULL;

struct node *rear = NULL;

23CS1302 43 DATA STRUCTURE

PANIMALAR ENGINEERING COLLEGE II YEAR/III SEM B.E-CSE

//Insert elements in Queue

void enqueue (int d)

{
struct node *newnode;
newnode = (struct node *) malloc (sizeof (struct node));
newnode ->data = d;
newnode ->next = NULL;
if ((rear == NULL) && (front == NULL))
{
front = rear = newnode;
rear->next = front;
}
else
{
rear->next = newnode;
rear = newnode;
newnode ->next = front;
}
}

// Delete an element from Queue

void dequeue ()
{
struct node *temp;
temp = front;
if ((front == NULL) && (rear == NULL))
printf ("\nQueue is Empty");
else if (front == rear)
{
front = rear = NULL;
free (temp);
}
else
{
front = front->next;
rear->next = front;
free (temp);
}

// Print the elements of Queue

23CS1302 44 DATA STRUCTURE

PANIMALAR ENGINEERING COLLEGE II YEAR/III SEM B.E-CSE

void display ()
{
struct node *temp;
temp = front;
if ((front == NULL) && (rear == NULL))
printf ("\nQueue is Empty");
else
{
do
{
printf (" %d", temp->data);
temp = temp->next;
}
while (temp != front);
}
}

DOUBLE-ENDED QUEUE (DEQUE)

Dequeue is also called as double ended queue and it allows user to perform insertion and deletion from
the front and rear position. And it can be easily implemented using doubly linked list. On creating
dequeue, we need to add two special nodes at the ends of the doubly linked list (head and tail). And these
two nodes needs to be linked between each other (initially).

In DEQUE, insertion and deletion operations are performed at both ends of the Queue.

23CS1302 45 DATA STRUCTURE

PANIMALAR ENGINEERING COLLEGE II YEAR/III SEM B.E-CSE

Operations on Deque :

Mainly the following four basic operations are performed on queue :

insertFront() : Adds an item at the front of Deque.

insertRear() : Adds an item at the rear of Deque.
deleteFront() : Deletes an item from front of Deque.
deleteRear() : Deletes an item from rear of Deque.

struct node

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

struct node *head = NULL, *tail = NULL;

struct node * createNode(int data)

{
struct node *newnode = (struct node *)malloc(sizeof (struct node));
newnode->data = data;
newnode->next = newnode->prev = NULL;
return (newnode);
}

void createSentinels()

{
head = createNode(0);
tail = createNode(0);
head->next = tail;
tail->prev = head;
}

/* insertion at the front of the queue */

void enqueueAtFront(int data)

{
struct node *newnode, *temp;
newnode = createNode(data);
23CS1302 46 DATA STRUCTURE
PANIMALAR ENGINEERING COLLEGE II YEAR/III SEM B.E-CSE

temp = head->next;
head->next = newnode;
newnode->prev = head;
newnode->next = temp;
temp->prev = newnode;
}

/*insertion at the rear of the queue */

void enqueueAtRear(int data)

{
struct node *newnode, *temp;
newnode = createNode(data);
temp = tail->prev;
tail->prev = newnode;
newnode->next = tail;
newnode->prev = temp;
temp->next = newnode;
}

/* deletion at the front of the queue */

void dequeueAtFront()
{
struct node *temp;
if (head->next == tail) {
printf("Queue is empty\n");
} else {
temp = head->next;
head->next = temp->next;
temp->next->prev = head;
free(temp);
}
return;
}

/* deletion at the rear of the queue */

void dequeueAtRear()
{
struct node *temp;
if (tail->prev == head) {
printf("Queue is empty\n");
} else {
temp = tail->prev;
tail->prev = temp->prev;
23CS1302 47 DATA STRUCTURE
PANIMALAR ENGINEERING COLLEGE II YEAR/III SEM B.E-CSE

temp->prev->next = tail;
free(temp);
}
return;
}

/* display elements present in the queue */

void display() {
struct node *temp;

if (head->next == tail)
{
printf("Queue is empty\n");
return;
}

temp = head->next;
while (temp != tail) {
printf("%-d", temp->data);
temp = temp->next;
}
printf("\n");
}

23CS1302 48 DATA STRUCTURE