Data Structure (Stack)
Dr. Rajendrani Mukherjee
Abstract Data Type (ADT)
Stack is an abstract data type.
ADT (Abstract Data Type) is a mathematical
model for data types.
An ADT may be defined as - class of objects
whose logical behavior is defined by a set of
values and a set of operations.
Stack History
The idea of Stack was first proposed by
Samelson and Bauer in 1955.
A stack can easily be implemented using an
array or linked list.
Some languages (Python, Ruby etc.) have
available push, pop operations.
Stack
Stack is an ADT . It is a collection of elements
with two main operations –
Push (for adding elements)
Pop (for removing the recently added element)
Stack follows LIFO (Last In First Out).
Stack is a linear data structure.
LIFO
Stack Top
Stack is a linear data structure.
Push and pop occur only at one end of the
Stack. This is referred as top of the stack.
The Pop operation removes an item from the
top of the stack.
Stack Pointer
A stack pointer points to the most recently
accessed location on the stack.
The stack pointer points to the origin of the
stack when the stack has a size of zero.
Stack Overflow and Underflow
When the stack is full, then it is said to be an
Overflow condition.
When the stack is empty, then it is said to be
an Underflow condition.
isFull() − check if stack is full.
isEmpty() − check if stack is empty.
Push Operation
The process of putting a new element into
stack is called Push Operation.
First it is checked whether the stack is full or
not.
If the stack is full then exit.
If the stack is not full, the stack top is
incremented to point to the next empty
space.
The data element gets added to the stack
location where top is pointing.
Pop Operation
First it is checked whether the stack is empty
or not.
If the stack is empty, exit.
If the stack is not empty, then the data
element at which stack top is pointing is
accessed.
The stack top value is decreased by 1.
Push and Pop Operation
Applications of Stack
Expression Parsing ( Infix to Postfix/Prefix
Conversion)
Stack based memory allocation
String Reversal
Tower of Hanoi Algorithm
Expression Parsing
Notations are named as how they use operator
in expression.
Infix Notation
Prefix Notation
Postfix Notation
Infix
Operators are used in-between operands.
a+b
(a + b) ∗ c
(a + b) ∗ (c + d)
Prefix
Operator is prefixed to operands ( operator is written
before operands).
+ab
∗+abc
∗+ab+cd
Postfix
The operator is postfixed to the operands (the
operator is written after the operands).
ab+c∗
ab+cd+∗
