VISVESVARAYA TECHNOLOGICAL UNIVERSITY
“Jnana Sangama”, Belagavi– 590018
DSA Seminar on
STACKS AND STACKS USING DYNAMIC
ARRAYS
PRESENTED BY UNDER THE GUIDANCE OF
Asmita T (1AT23IS026) Dr. K S Ananda Kumar
Femilin Yahini W (1AT23IS049) Associate Professor
D Vidyashri (1AT23IS040) Dept. of ISE, Atria IT
ATRIA INSTITUTE OF TECHNOLOGY
BANGALORE-54, Karnataka
DEPARTMENT OF INFORMATION SCIENCE AND
ENGINEERING
Stacks
Stack using dynamic
arrays
Table of
Contents
01 Introduction to
Stacks
02 Types of Stacks
03 Stack Applications
04 Dynamic stacks
05 Conclusion
01
Introduction to Stacks
Definition and Purpose
What is a Stack?
01 A stack is a linear data structure that follows the Last In First Out (LIFO)
principle, where the last element added is the first to be removed.
It's used in various applications like function calls and expression
evaluation.
Key Characteristics
Stacks are characterized by their operations: push (add) and pop (remove).
02 They also have a fixed size, which can lead to overflow in some
implementations.
Practical Uses
Commonly used in programming languages for managing function calls.
03 Utilized in undo mechanisms in software applications.
Stack Operations
Push Operation IsFull Operation
Push is the operation to add an item This operation checks if the stack has any
to the top of the stack. elements.(or full)
This operation increases the stack's It’s useful to prevent overflow errors when
size by one. attempting to push from an full stack.
Pop Operation IsEmpty Operation
Pop is the operation that removes the This operation checks if the stack has
item from the top of the stack. any elements.
This operation decreases the stack's It’s useful to prevent underflow errors
size by one and returns the removed when attempting to pop from an
item. empty stack.
02
Types of Stacks
Simple Stack
Definition
A simple stack is a straightforward implementation using arrays or
linked lists.
It provides basic stack functionalities.
Advantages
Easy to implement and understand.
Good performance for basic operations.
Disadvantages
Fixed size if an array is used, leading to overflow.
Requires additional memory for linked list implementations.
Dynamic Stack
Definition
A dynamic stack adjusts its size as needed.
Typically implemented using linked lists.
Advantages
No fixed size, thus preventing overflow issues.
Efficient memory usage as it grows and shrinks dynamically.
Disadvantages
Slightly more complex to implement.
Additional memory overhead due to pointers in linked lists.
03
Stack Applications
SPARSE MATRIX
Stack Frames
A sparse matrix is a matrix in which most of the elements
are zero. Stacks can be used to store and manipulate
sparse matrices efficiently, especially for operations like
traversal or non-zero element handling.
Expression Evaluation
Prefix and Postfix
Notation
Parsing
Stacks facilitate evaluating expressions written in prefix or postfix notation.
They help in correctly ordering operations according to precedence.
Converting Infix to Prefix using Stacks
Infix notation is the conventional notation used in arithmetic expressions, where
operators are placed between operands.
Example: A + B * C
Prefix notation, also known as Polish notation, places operators before their
operands.
Example: + A * B C
04
Creating a Stack
using Dynamic array
Implementation OF Stacks
Using Dynamic Arrays
We can allocate or create a stack dynamically
during run time. When we are not sure about
the size of the stack,
Using malloc(),calloc(),realloc(),free()
Code illustration
Int stacksize = 1;
int *s;
Int top=-1;
S=(int *)malloc(stacksize * sizeof(int));
Void push()
{
If(top==stacksize-1)
{
Printf(“stack full:Increase by 1\n”);
Stacksize ++;
S=(int*)relloc(s,stacksize * sizeof(int));
}
S[++top]=item;
}
Void pop()
{
If(top==-1)
{
Printf(“Stack underflow”);
Return;
}
Printf(“Item deleted=%d\n”,s[top--]);
Stacksize--;
S=(int *)relloc(s,stacksize *sizeof(int));
}
05
Conclusion
KEY FEATURES
Dynamic arrays offer features like automatic
resizing,
❖ Which allows them to accommodate more
elements than their initial capacity.
❖ They also provide random access to elements,
making them efficient for many operations,
including insertion and deletion.
REAL-WORLD EXAMPLES
REAL-WORLD EXAMPLES Stacks and
dynamic arrays are used in various real-
world applications, from web browsers (for
backtracking) to game development (for
managing game states). Their versatility
makes them indispensable tools in a
developer's toolkit.
Summary of Stacks
Key Takeaways
Stacks are fundamental data structures with various
applications in computer science.
Understanding stacks aids in grasping more complex
data structures and algorithms.
Future Learning
Explore more advanced data structures that build upon
stacks.
Consider learning about queues and their differences
from stacks.
Thank you!
