DATA
STRUCTURES
MAHESH GOYANI
MAHATMA GANDHI INSTITUE OF TECHNICAL EDUCATION & RESEARCH CENTER
mgoyani@[Link]
(C) GOYANI MAHESH 1
STACK
(C) GOYANI MAHESH 2
TERMINOLOGY
Stacks in real life: stack of books, stack of plates
Non – Primitive, Linear Data Structure.
Operation can be performed at one end only
Last In Firs Out (LIFO | FILO | FCLS | LCFS)
Most Frequently accessible element is TOP
Insertion -> PUSH : TOP++
Deletion -> POP : TOP--
Stack Full + Push() = Overflow
Stack Empty + Pop() = Underflow
(C) GOYANI MAHESH 3
47 TOP=2
33 TOP=1 33
20 TOP=0 20 20
TOP=-1 Push (20) Push (33) Push (47)
Stack Empty
77 TOP=2
33 TOP=1 33 33 TOP=1
20 20 20 20 TOP=0
Pop () Push (77) Pop () Pop ()
(C) GOYANI MAHESH 4
STACK OPERATION
int pop()
{
return STACK[TOP--]; int IsFull()
} {
return ( TOP == STACK_SIZE-1);
}
void push(int x)
{
STACK[++TOP] = x;
}
int IsEmpty()
{
return ( TOP == -1 );
int top() }
{
return STACK[TOP];
}
(C) GOYANI MAHESH 5
IMPLEMENTATION
STACK implementation can be done in TWO ways;
(I) Static Implementation (Using Array)
(II) Dynamic Implementation (Using Pointers / Linked List)
(C) GOYANI MAHESH 6
Using ARRAY
TOP 1
2 5 7 1
7
5 0 1 2 3 4
2 TOP = 3
(C) GOYANI MAHESH 7
ALGORITHM PUSH (STACK, TOP, DATA)
1. [Check for Stack Overflow]
If TOP == STACK_SIZE - 1, then
(a). “Stack Over Flow”
(b). Return.
2. [Increment TOP]
TOP = TOP + 1
3. [Insert Item On to Stack]
STACK[TOP] = DATA
4. Exit
(C) GOYANI MAHESH 8
ALGORITHM POP(STACK, TOP, DATA)
1. [Check for Stack Underflow]
If TOP < 0, then
(a). “Stack Underflow”
(b). Return.
2. [Read The Top Most Element]
DATA = STACK[TOP]
3. [Decrement TOP]
TOP = TOP - 1
4. Exit
(C) GOYANI MAHESH 9
ALGORITHM PEEP(STACK, TOP, I, DATA)
1. [Check for Stack Underflow]
If TOP - I < 0, then
(a). “Stack Underflow”
(b). Return.
2. [Read Ith Element]
DATA = STACK[I]
3. Exit
(C) GOYANI MAHESH 10
ALGORITHM CHANGE(STACK, TOP, I, DATA)
1. [Check for Stack Underflow]
If TOP - I < 0, then
(a). “Stack Underflow”
(b). Return.
2. [Exchange Ith Element]
STACK[I] = DATA
3. Exit
(C) GOYANI MAHESH 11
Using LINKED LIST
We can avoid the size limitation of a stack implemented with an array
by using a linked list to hold the stack elements
No need for the current pointer, head is enough.
HEAD
TOP 1
1 7 5 2
7
5
2
(C) GOYANI MAHESH 12
OPERATION
head
1 7 5 2
top 7
5
2
pop(1)
head
top 9
7 5 2
7
5
newNode 9
2
push(9)
(C) GOYANI MAHESH 13
ARRAY v/s LINKED LIST
Allocating and deallocating memory for list nodes does take more
time than preallocated array.
List uses only as much memory as required by the nodes; array
requires allocation ahead of time.
List pointers (head, next) require extra memory.
Array has an upper limit, List is limited by dynamic memory
allocation.
(C) GOYANI MAHESH 14
APPLICATION
START
Recursion
Initialization
Infix to Postfix Prologue
Tower of Hanoi
Partial
Decision
Computation
int fact (int no)
Final
{ UPDATE
Computation
int f=1;
if(no==1) Recursive
return no;
Body Call
else
{
f = no * fact (no - 1); Return
}
}
STOP Epilogue
(C) GOYANI MAHESH 15
Recursion Iteration
It is an process of executing a Recursion is a technique to define
statement of set of statements repeatedly, anything in terms of it self.
until some specified condition is met.
Clear cut four steps. Initialization, There must be exclusive if
Condition, Execution & Updating statement for stopping condition
Any recursive problem can be solved Not all problem have recursive
iteratively solution
More efficient in terms of memory Worse option to go for simple
utilization and execution speed problems, or problems not recursive in
nature.
(C) GOYANI MAHESH 16
EXPRESSION
INFIX : Operator appears between two operand : A+B
PREFIX : Operator appears before two operand : +AB
POSTFIX : Operator appears after two operand : AB+
Infix Prefix Postfix
A+B +AB AB+
A+B*C +A*BC ABC*+
A*(B+C) *A+BC ABC+*
A*B/C /*ABC AB*C/
A/B*C */ABC AB/C*
Prefix notation is also known as Polish Notation
Computer understands every thing in terms of POSTFIX (Reverse Polish
Notation) form
In postfix notation, operator appears after operands, so there is no need of
operator precedence rule.
(C) GOYANI MAHESH 17
INFIX TO POSTFIX
1. Push ‘(’ on to TEMP_STACK, and add ‘)’ to the end of P.
2. Scan P from left to right and repeat step 3 to 6 for each element of P until
TEMP_STACK the stack is empty.
3. If an operand is encountered, add it to OP_STACK
4. If left parenthesis encountered than add it to TEMP_STACK.
5. If an operator is encountered, then:
(a). Repeatedly pop from TEMP_STACK and add each operator to
OP_STACK which has same or higher precedence then
(b). Add to TEMP_STACK
6. If right parenthesis encountered, then:
(a). Repeatedly pop from TEMP_STACK and add to OP_STACK until a left
parenthesis encountered.
(b). Remove the left parenthesis (Don’t add it to OP_STACK)
7. Exit.
(C) GOYANI MAHESH 18
Evaluation
P = A +( B / C - ( D * E ^ F ) + G ) * H
Character TEMP_STACK Postfix_STACK
Scanned
A ( A
+ (+ A
( (+( A
B (+( AB
/ (+( / AB
C (+( / ABC
- (+( - ABC/
( (+( - ( ABC/
D (+( - ( ABC/D
(C) GOYANI MAHESH 19
Evaluation
P = A +( B / C - ( D * E ^ F ) + G ) * H
* (+( - (* ABC/D
E (+( - (* ABC/DE
^ (+( - (* ^ ABC/DE
F (+( - (* ^ ABC/DEF
) (+( - ABC/DEF^*
+ (+(+ ABC/DEF^*-
G (+(+ ABC/DEF^*-G
) (+ ABC/DEF^*-G+
* (+ * ABC/DEF^*-G+
H (+* ABC/DEF^*-G+H
) ABC/DEF^*-G+H*+
(C) GOYANI MAHESH 20
Tower of Hanoi
INPUT
X Y Z
D
C
B
A
OUTPUT
Y Z
X
D
C
B
A
(C) GOYANI MAHESH 21
