COURSE OUTCOME

CO1: Apply the concepts of data structure, data type and array data
structure and analyze the algorithms and determine their time complexity.
CO2: Apply various data structure such as stacks, Linked List, queues, trees
and graphs to solve various computing problems using C-programming
language.
CO3: Implement standard algorithms for searching & sorting and identify
when to choose which technique.
CO4: Apply the data structure that efficiently models the information in a
problem.

1
1
CONTENTS (TO BE COVERED)
❑ Introduction of Data Structures and Algorithms

❑ Stack

❑ Basic Operations (PUSH, POP)

❑ Array Representation of Stack (Static & Dynamic)

❑ Applications of Stack

❑ Tower of Hanoi

❑ Multiple Stack representation using Single Array

1
LECTURE CONTENTS WITH A BLEND OF NPTEL
CONTENTS
❑ Introduction of Data Structures and Algorithms

❑ Stack

❑ Array Representation of Stack (Static & Dynamic)

❑ Applications of Stack

❑ Tower of Hanoi

❑ Multiple Stack representation using Single Array

1
What is Data Structure?
• A data structure is a way of organizing data in a
computer so that it can be used data effectively.
• For example, we can store a list of items having the
same data-type using the array data structure.
Types of Data Structures
Based on the organizing method of data structure, data structures are divided into two
types.
• Linear Data Structures
• Non - Linear Data Structures
Linear Data Structures Non-Linear Data Structures

• if a data structure organizes the data in • If a data structure organizes the data in
sequential order, then that data structure is random order then that data structure is
called a linear data structure
called as Non-linear data structure.
• Example
Arrays
• Example
List (Linked List) Tree
Stack Graph
Queue Dictionaries
Heaps
Tries, Etc.,
DATA
STRUCTURE

LINEAR DATA NON LINEAR DATA

STRUCTURE
STRUCTURE

ARRAY QUEUE STACK

6
Stack (Last in First Out)
• A stack is called a last-in-first-out (LIFO) collection. This means that
the last thing we added (pushed) is the first thing that gets pulled
(popped) off.

• A stack is a sequence of items that are accessible at only one end of

the sequence
EXAMPLES OF STACK:

8
Basic Operations

⮚ PUSH(Insertion)

⮚ POP (Deletion)
Example
Example of Stack
PUSH Operation

• In a stack, push() is a function used to insert an element into the stack. In a stack,
the new element is always inserted at top position. Push function takes one
integer value as parameter and inserts that value into the stack. We can use the
following steps to push an element on to the stack...

✔ Step 1 - Check whether stack is FULL. (top == SIZE-1)

✔ Step 2 - If it is FULL, then display "Stack is FULL!!! Insertion is not
possible!!!" and terminate the function.
✔ Step 3 - If it is NOT FULL, then increment top value by one (top++) and set
stack[top] to value (stack[top] = value).
POP Operation
• In a stack, pop() is a function used to delete an element from the stack. In a stack,
the element is always deleted from top position. Pop function does not take any
value as parameter. We can use the following steps to pop an element from the
stack...
✔ Step 1 - Check whether stack is EMPTY. (top == -1)
✔ Step 2 - If it is EMPTY, then display "Stack is EMPTY!!! Deletion is not
possible!!!" and terminate the function.
✔ Step 3 - If it is NOT EMPTY, then delete stack[top] and decrement top value
by one (top--).
Display Stack items:
• The 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.
✔ Step 3 - 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 3 - Repeat above step until i value becomes '0'.
Applications

1. Reversing Strings:
• A simple application of stack is reversing strings.
• To reverse a string , the characters of string are pushed
onto the stack one by one as the string is read from left
to right.
• Once all the characters of string are pushed onto stack,
they are popped one by one. Since the character last
pushed in comes out first, subsequent pop operation
results in the reversal of the string.
Example
•To reverse the string ‘REVERSE’ the string is read from left to right and
its characters are pushed .
LIKE: onto a stack.
Applications
2. Checking the validity of an expression containing nested
parenthesis:
• Stacks are also used to check whether a given arithmetic
expressions containing nested parenthesis is properly
parenthesized.
• The program for checking the validity of an expression
verifies that for each left parenthesis braces or
bracket ,there is a corresponding closing symbol and
symbols are appropriately nested.
For example:
VALID INPUTS INVALID INPUTS
{} {(}
({[]}) ([(()])
{[]()} {}[])
[{({}[]({ [{)}(]}]
})}]
Applications
3. Evaluating arithmetic expressions
–INFIX notation:
–The general way of writing arithmetic expressions is known as infix
notation. e.g, (a+b)

•PREFIX notation: e.g, +AB

•POSTFIX notation: e.g: AB+

Conversion of Infix to Postfix
1. Scan the Infix expression from left to right for
tokens (Operators, Operands & Parentheses) and perform the steps 2 to 5 for
each token in the Expression.
2. If token is operand, Append it in postfix expression
3. If token is a left parentheses “(“, push it in stack
4. If token is an operator,
– Pop all the operators which are of higher or equal precedence then the
incoming token and append them (in the same order) to the output
Expression.
– After popping out all such operators, push the new token on stack.
Conversion of Infix to Postfix
5. If “)” right parentheses is found,
• Pop all the operators from the Stack and append them to Output String,
till you encounter the Opening Parenthesis “(“.
• Pop the left parenthesis but don’t append it to the output string (Postfix
notation does not have brackets).

6. When all tokens of Infix expression have been scanned. Pop all the
elements from the stack and append them to the Output String.
The Output string is the Corresponding Postfix Notation.
Example: 2+(4-1)*3 step1
2+41-*3 step2
2+41-3* step3
241-3*+ step4
CONVERSION OF INFIX INTO POSTFIX
{2+(4-1)*3 into 241-3*+}
CURRENT ACTION STACK STATUS POSTFIX
SYMBOL PERFORMED EXPRESSION

( PUSH C C 2
2 2
+ PUSH + (+ 2
( PUSH ( (+( 24
4 24
- PUSH - (+(- 241
1 POP 241-
) (+ 241-
* PUSH * (+* 241-
3 241-3
POP * 241-3*
POP + 241-3*+
)
Tower of Hanoi
• The Tower of Hanoi puzzle was invented by the French mathematician Edouard
Lucas in 1883.
• Tower Of Hanoi is a Puzzle involving the usage of Stacks.
• Shifting of discs from source tower to target tower.
• Rules for solving puzzle:
1. One disc can be shifted at once.
2. Only top disc can be shifted.
3. Large disc cannot be placed on smaller disc.
4. Only 3 stacks can be used for solving the puzzle.

•Source Tower having N discs can be solved using (2^N)-1 moves.

Usage of Stacks in Tower of Hanoi

Steps:
1. Move 1 from A to C
2. Move 2 from A to B
3. Move 1 from C to B
4. Move 3 from A to C
5. Move 1 from B to A
6. Move 2 from B to C
7. Move 1 from A to C

Real life analogy of Stack is Access single disc, Single Access location.
Use of Recursion for
: algorithm
Explanation
• The recursion used before
"movedisk" is to move all but the
bottom disk on the initial tower to
an intermediate pole.
• The next line simply moves the
bottom disk to its final resting
place.
• Then on line we move the tower
from the intermediate pole to the
top of the largest disk.
• The base case is detected when
the tower height is 0 and the base
of the tower is moved Use of recursion is again use of stack
Application
▪ Used as Backup rotation Scheme (Backups of Computers
having multiple tapes/media)
✔A backup rotation scheme is a system for managing your
backup storage media (tapes/DVDs/HDDs).
▪ Used by neuropsychologists trying to evaluate frontal lobe
deficits.
▪ Used to Solve mathematical problems related to Hamilton
Cycle.
Representation of Stack
• Stack can be represented in two ways
1. Using array
2. Using linked lists
Both the representations are having their own
advantages and disadvantages. So to select the
representation of stack is application dependent.
Stack representation using static array
• Stack data structure can be implemented using a one-
dimensional array.
• Size of array is fixed.
• Basic steps to create an empty stack.
1. Include all the header files which are used in the
program and define a constant 'SIZE' with specific
value.
2. Declare all the functions used in stack implementation.
3. Create a one dimensional array with fixed size.
4. Define a integer variable 'top' and initialize with '-1'.
(int top = -1)
5. In main method, display menu with list of operations
and make suitable function calls to perform operation
selected by the user on the stack.
• #include<stdio.h>
• #include<conio.h>
• #define SIZE 10
• int stack[SIZE], top=-1;
push(value) - Inserting value into the
stack
• Step 1 - Check whether stack is FULL. (top == SIZE-1)
• Step 2 - If it is FULL, then display "Stack is FULL!!!
Insertion is not possible!!!" and terminate the function.
• Step 3 - If it is NOT FULL, then increment top value by
one (top++) and set stack[top] to value (stack[top] =
value).
void push(int value)
{
If(top==SIZE-1)
printf(“stack is full!!! Insertion is not possible”);
else
{
top++;
stack[top]=value;
printf(“successfully inserted”);
}
}
pop() - Delete a value from the Stack

• Step 1 - Check whether stack is EMPTY. (top == -1)

• Step 2 - If it is EMPTY, then display "Stack is EMPTY!!!
Deletion is not possible!!!" and terminate the function.
• Step 3 - If it is NOT EMPTY, then delete stack[top] and
decrement top value by one (top--).
void pop()
{
if(top==-1)
printf(“stack is empty!! Deletion not
possible”);
else{
printf(“deleted: %d”,stack[top]);
top--;
}
}
display() - Displays 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.
• Step 3 - 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 3 - Repeat above step until i value becomes '0'.
void display()
{
if(top == -1)
printf("\nStack is Empty!!!");
else{
int i;
printf("\nStack elements are:\n");
for(i=top; i>=0; i--)
printf("%d\n",stack[i]);
}
}
void main() switch(choice){
{ case 1: printf("Enter the value to be
int value, choice; insert: ");
clrscr(); scanf("%d",&value);
while(1){ push(value);
printf("\n\n***** MENU break;
*****\n"); case 2: pop();
printf("1. Push\n2. Pop\n3. break;
Display\n4. Exit"); case 3: display();
printf("\nEnter your choice: "); break;
scanf("%d",&choice); case 4: exit(0);
default: printf("\nWrong selection!!!
Try again!!!");
}}} 39
• In the implementation of stack using static array, size is
always predefined or fixed.
• Once stack is created its size cannot be changed hence
a condition called “stack full”
arises.
• To overcome this problem we will use dynamic array/
growable stack.
• So a dynamic array can change its capacity.
• Growable stack is the concept of allocating more memory
such that stack full condition does not arises easily.
• A growable array base stack can be implemented by
allocating new memory larger than previous stack
memory and copying elements from old stack to new
stack.
• And then at last the name of the new stack as the name
given to the previous stack.
Strategy for growable stack
• There are two strategies:
1. Tight Strategy : Add a constant amount to the old
stack (N+c)
2. Growth Strategy : Double the size of old stack (2N)
• Following steps should be done
1. Allocate new space
2. Copy data to new space
3. Free old space
Implement Stack Operations using Dynamic
Memory Allocation
Problem Solution
1. Use malloc function to allocate memory.
2. Define separate functions for the operations like push,
pop and display.
3. Use switch statement to access these functions.
#include<stdio.h> Program
#include<stdlib.h>
struct stack
{
int * a;
int top;
int maxSize;
};
void initstack(struct stack * p, int maxSize);
void push(struct stack * p, int item);
void display(struct stack p);
int pop(struct stack * p);
intvoid printMenu();
main()
{
struct stack p;
int data,ch, data1, m;
scanf("%d",&m);
initstack(&p,m);
do
{
printMenu();
printf("Enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Enter the element to be pushed\n");
scanf("%d",&data);
push(&p,
case 2: data);
data1 = pop(&p);
break;
if(data1 != -1000)
printf("The popped element is %d\n",data1);
break;
case 3: printf("The contents of the stack are"); void push(struct stack * p, int item)
display(p); {
printf("\n"); if (p->top == p->maxSize-1)
break; {
default: printf("Stack is full\n");
return 0; return;
} }
} p->a = (int *)malloc(sizeof(int));
while(1); p->top++;
return 0; p->a[p->top] =item;
} p->maxSize--;
void printMenu() }
{ void display(struct stack p)
printf("Choice 1 : Push\n"); {
printf("Choice 2 : Pop\n"); struct stack *p1;
printf("Choice 3 : Display\n"); p1=&p;
printf("Any other choice : Exit\n"); int a[30],n=0,i;
} for (i = p1->top ; i >= 0; i--)
void initstack(struct stack * p, int maxSize) {
{ printf("\n%d", p1->a[i]);
p->top=-1; }
p->maxSize=maxSize; }
}
int pop(struct stack * p)
{
int num;
if(p->top == -1)
{
printf("Stack is empty\n");
return -1000;
}
num = p->a[p->top];
p->top--;
return num;
}
Stack Using Linked List

50
Linked List in Data Structure
• A linked list is a linear data structure, in which the elements are
not stored at contiguous memory locations. The elements in a
linked list are linked using pointers as shown in the below
image:

A linked list is represented by a pointer to the first node of the linked list. The first node
is called the head. If the linked list is empty, then the value of the head is NULL.
Each node in a list consists of at least two parts:
1) data
2) Pointer (Or Reference) to the next node
Why Linked List?
• Arrays can be used to store linear data of similar types, but arrays
have the following limitations.

1) The size of the arrays is fixed: So we must know the upper limit on
the number of elements in advance. Also, generally, the allocated
memory is equal to the upper limit irrespective of the usage.

2) Inserting a new element in an array of elements is expensive

because the room has to be created for the new elements and to
create room existing elements have to be shifted.
For example, in a system, if we maintain a sorted list of IDs in
an array id[].
• id[] = [1000, 1010, 1050, 2000, 2040].
• And if we want to insert a new ID 1005, then to maintain the
sorted order, we have to move all the elements after 1000
(excluding 1000).
Deletion is also expensive with arrays until unless some
special techniques are used. For example, to delete 1010 in
id[], everything after 1010 has to be moved.
Advantages over arrays
• They are a dynamic in nature which allocates the
memory when required.
• Insertion and deletion operations can be easily
implemented.
• Stacks and queues can be easily executed.
• Linked List reduces the access time.

Disadvantages of Linked Lists

• The memory is wasted as pointers require extra memory
for storage.
• No element can be accessed randomly; it has to access
each node sequentially.
• Reverse Traversing is difficult in linked list.
Applications of Linked Lists
• Linked lists are used to implement stacks, queues,
graphs, etc.
• Linked lists let you insert elements at the beginning and
end of the list.
• In Linked Lists we don't need to know the size in advance.
Types of Linked Lists:
There are 3 different implementations of Linked List
available, they are:
• Singly Linked List
• Doubly Linked List
• Circular Linked List
Singly Linked List

Singly linked lists contain nodes which have a data part as well as
an address part i.e. next, which points to the next node in the
sequence of nodes.
The operations we can perform on singly linked lists
are insertion, deletion and traversal.
Doubly Linked List

In a doubly linked list, each node contains a data part and two
addresses, one for the previous node and one for the next node.
Circular Linked List
In circular linked list the last node of the list holds the address of
the first node hence forming a circular chain.
ARRAY LINKED LIST
Array is a collection of elements of similar data type. Linked List is an ordered collection of elements of same type, which
are connected to each other using pointers.
Array supports Random Access, which means elements can be Linked List supports Sequential Access, which means to access any
accessed directly using their index, like arr[0] for 1st element/node in a linked list, we have to sequentially traverse the
element, arr[6] for 7th element etc. complete linked list, upto that element.
Hence, accessing elements in an array is fast with a constant time To access nth element of a linked list, time complexity is O(n).
complexity of O(1).
In an array, elements are stored in contiguous memory location or In a linked list, new elements can be stored anywhere in the memory.
consecutive manner in the memory. Address of the memory location allocated to the new element is
stored in the previous node of linked list, hence formaing a link
between the two nodes/elements.

In array, Insertion and Deletion operation takes more time, as the In case of linked list, a new element is stored at the first free and
memory locations are consecutive and fixed. available memory location, with only a single overhead step of storing
the address of memory location in the previous node of linked list.
Insertion and Deletion operations are fast in linked list.

Memory is allocated as soon as the array is declared, at compile Memory is allocated at runtime, as and when a new node is added.
time. It's also known as Static Memory Allocation. It's also known as Dynamic Memory Allocation.

In array, each element is independent and can be accessed using it's In case of a linked list, each node/element points to the next, previous,
index value. or maybe both nodes.
Array can single dimensional, two Linked list can be Linear(Singly), Doubly or Circular linked list.
dimensional or multidimensional
Size of the array must be specified at time of array decalaration. Size of a Linked list is variable. It grows at runtime, as more nodes
are added to it.
Array gets memory allocated in the Stack section. Whereas, linked list gets memory allocated in Heap section.