[Link].

in
Stack
By:Prof Priyanka Jangde
Basic Idea
A stack is an Abstract Data Type (ADT), commonly used in most
programming languages. It is named stack as it behaves like a real-
world stack, for example – a deck of cards or a pile of plates, etc.

8 October 2020 priyankajangde@[Link] 3

Basic Idea

CARGO

Goods in a cargo

out
in

Trains in a Railyard Plates on a tray

8 October 2020 priyankajangde@[Link] 4
Stacks: Definition
A stack is an ordered collection of homogeneous data element where the
insertion and deletion operations take place at one end only

LIFO (Last In First Out)

PUSH
POP

ITEM 1 TOP
ITEM 2
ITEM 3
ITEM 4

.
.
.
.
Bottom

8 October 2020 priyankajangde@[Link] 5

Stack Representation

•Can be implemented by means of Array, Structure, Pointers and Linked List.

•Stack can either be a fixed size or dynamic.

8 October 2020 priyankajangde@[Link] 6

Stacks: Memory Representations
Array representation
Linked list representation
Index 1D Array
STACK_HEAD
l Bottom
ITEM1

l+1 ITEM2
ITEMi .. . ... ....
l+2 .
. .
. . TOP

l+i-1 ITEMi TOP ITEM2

. .
. .
. .

u ITEM1
SIZE = u+l-1

8 October 2020 priyankajangde@[Link] 7

Stacks: Operations
push

pop

create
STACK
isempty

isfull

8 October 2020 priyankajangde@[Link] 8

Stacks: Operations
PUSH To insert an item into the stack

POP To remove an item from a stack

STATUS To know the present state of a stack

TOP To read the top element

8 October 2020 priyankajangde@[Link] 9

STACK: Last-In-First-Out (LIFO)
• void push (stack *s, int element);
/* Insert an element in the stack */
• int pop (stack *s);
/* Remove and return the top element */
• void create (stack *s);
/* Create a new stack */
• int isempty (stack *s);
/* Check if stack is empty */
• int isfull (stack *s);
/* Check if stack is full */
8 October 2020 priyankajangde@[Link] 10
Stacks: Applications
Stack is extensively used in system programming

Arithmetic expression evaluation

Code Generation

Implementation of recursion

Activation record management

8 October 2020 priyankajangde@[Link] 11

8 October 2020 priyankajangde@[Link] 12
Stack using Array
Push using Stack
PUSH

top

top

8 October 2020 priyankajangde@[Link] 14

Algorithm Push_Array
Input: The new item ITEM to be pushed onto it
Output: A stack with a newly pushed ITEM at the TOP position.
Data Structure : An Array A with TOP as the pointer.

Steps:
1. If TOP≥ SIZE then
2. Print “Stack is full”
3. Else
4. TOP = TOP+1
5. A[TOP]= ITEM
6. EndIf
7. Stop
8 October 2020 priyankajangde@[Link] 15
Pop using Stack
POP

top

top

8 October 2020 priyankajangde@[Link] 16

Algorithm Pop_Array
Input: A stack with elements.
Output: Removes an ITEM from the top of the stack if it is not empty.
Data Structure : An Array A with TOP as the pointer.

Steps:
1. If TOP< 1 then
2. Print “Stack is empty”
3. Else
4. ITEM= A[TOP]
5. TOP = TOP-1
6. EndIf
7. Stop
8 October 2020 priyankajangde@[Link] 17
Algorithm Status_Array
 Input: A stack with elements.
 Output: States whether it is empty or full , available free space and item at TOP.
 Data Structure : An Array A with TOP as the pointer.

 Steps:
1. If TOP< 1 then
2. Print “Stack is empty”
3. Else
4. If (TOP ≥ SIZE) then
5. Print “ Stack is full”
6. Else
7. Print “ The element at TOP is” A[TOP]
8. Free = (SIZE- TOP)/ SIZE * 100
9. Print “percentage of free stack is” free
10. Endif
11. EndIf
12. Stop

8 October 2020 priyankajangde@[Link] 18

Stack using Linked List
Push using Linked List
PUSH OPERATION

top

8 October 2020 priyankajangde@[Link] 20

Algorithm Push_LL
Input: ITEM is the item to be inserted.
Output: A single linked list with a newly inserted node with data content ITEM.
Data Structure : A single linked list structure whose pointer to the header is
known from STACK_HEAD and TOP is the pointer to the first node.

Steps:
1. /* Insert at front*/
2. New DATA = ITEM
3. New LINK= TOP
4. TOP= new
5. STACK_HEADLINK=TOP
6. Stop
8 October 2020 priyankajangde@[Link] 21
Pop using Linked List
POP OPERATION

top

8 October 2020 priyankajangde@[Link] 22

Algorithm Pop_LL
InputA stack with elements.
Output: The removed item is stored in ITEM
Data Structure : A single linked list structure whose pointer to the header is known from STACK_HEAD and TOP
is the pointer to the first node.

Steps:
1. If Top = NULL
2. Print “ Stack is empty”
3. Exit
4. Else
5. Ptr = TOP LINK
6. ITEM = TOP DATA
7. STACK_HEAD = ptr
8. TOP = ptr
9. Endif
10. Stop

8 October 2020 priyankajangde@[Link] 23

Algorithm Status_LL()
 Input: A stack with elements.
 Output: Status information such as its state (empty or full), number of items, item at the TOP.
 Data Structure : A single linked list structure whose pointer to the header is known from STACK_HEAD and TOP is the
pointer to the first node.

 Steps:
1. Ptr = STACK_HEAD LINK
2. If (ptr = NULL) then
3. Print “ stack is empty”
4. Else
5. nodeCount = 0
6. While (ptr ≠ NULL)do
7. nodeCount = nodeCount +1
8. Ptr = ptr LINK
9. EndWhile
10. Print “ the item at the front is” , TOP  DATA, “ Stack contains”, nodeCount, “ Number of items”
11. Endif
12. Stop

8 October 2020 priyankajangde@[Link] 24

Basic Idea
• In the array implementation, we would:
• Declare an array of fixed size (which determines the maximum size of the stack).

• Keep a variable which always points to the “top” of the stack.

• Contains the array index of the “top” element.

• In the linked list implementation, we would:

• Maintain the stack as a linked list.
• A pointer variable top points to the start of the list.
• The first element of the linked list is considered as the stack top.

8 October 2020 priyankajangde@[Link] 25

Declaration
#define MAXSIZE 100
struct lifo
{
struct lifo
int value;
{ structlifo *next;
int st[MAXSIZE]; };
int top; typedef struct lifo stack;
};
typedef struct lifo stack; stack *top;
stack s;

ARRAY LINKED LIST

8 October 2020 priyankajangde@[Link] 26

Stack Creation

void create (stack *s)

{ void create (stack **top)
s->top = -1; {
*top = NULL;
/* s->top points to
last element /* top points to NULL,
pushed in; indicating empty
initially -1 */ stack */
} }

ARRAY LINKED LIST

8 October 2020 priyankajangde@[Link] 27
Pushing an element into stack
void push (stack *s, int element) void push (stack **top, int element)
{ {
if (s->top == (MAXSIZE-1)) stack *new;
{ new = (stack *)malloc (sizeof(stack));
printf (“\n Stack overflow”); if (new == NULL)
exit(-1); {
} printf (“\n Stack is full”);
else exit(-1);
{ }
s->top++; new->value = element;
s->st[s->top] = element; new->next = *top;
} *top = new;
} }

ARRAY LINKED LIST

8 October 2020 priyankajangde@[Link] 28

Popping an element from stack
int pop (stack **top)
{
int pop (stack *s) int t;
{ stack *p;
if (s->top == -1) if (*top == NULL)
{ {
printf (“\n Stack underflow”); printf (“\n Stack is empty”);
exit(-1);
exit(-1); }
} else
else {
{ t = (*top)->value;
p = *top;
return (s->st[s->top--]); *top = (*top)->next;
} free (p);
} return t;
}
}

ARRAY LINKED LIST

8 October 2020 priyankajangde@[Link] 29

Checking for stack empty

int isempty (stack *s) int isempty (stack *top)

{ {
if (s->top == -1) if (top == NULL)
return 1; return (1);
else else
return (0); return (0);
} }

ARRAY LINKED LIST

8 October 2020 priyankajangde@[Link] 30

Checking for Stack Full

int isempty (stack *s) int isempty (stack *top)

{ {
if (s->top == -1) if (top == NULL)
return 1; return (1);
else else
return (0); return (0);
} }

ARRAY LINKED LIST

8 October 2020 priyankajangde@[Link] 31

Example: A Stack using an Array
#include <stdio.h>
#define MAXSIZE 100
struct lifo
{
int st[MAXSIZE];
int top;
};
typedef struct lifo stack;
main() {
stack A, B;
create(&A);
create(&B);
push(&A,10);
push(&A,20);
push(&A,30);
push(&B,100);
push(&B,5);
printf (“%d %d”, pop(&A), pop(&B));
push (&A, pop(&B));
if (isempty(&B))
printf (“\n B is empty”);
return;
}

8 October 2020 priyankajangde@[Link] 32

Example: A Stack using Linked List
 #include <stdio.h>
 struct lifo
 {
 int value;
 struct lifo *next;
 };
 typedef struct lifo stack;

 main() {
 stack *A, *B;
 create(&A);
 create(&B);
 push(&A,10);
 push(&A,20);
 push(&A,30);
 push(&B,100);
 push(&B,5);

 printf (“%d %d”, pop(&A), pop(&B));

 push (&A, pop(&B));

 if (isempty(B))
 printf (“\n B is empty”);
 return;
 }

8 October 2020 priyankajangde@[Link] 33

Applications of Stacks
• Direct applications:
• Page-visited history in a Web browser
• Undo sequence in a text editor
• Chain of method calls in the Java Virtual Machine
• Validate XML

• Indirect applications:
• Auxiliary data structure for algorithms
• Component of other data structures

8 October 2020 priyankajangde@[Link] 34

Important Features
The three important features of postfix expression are:
1. The operands maintain the same order as in the equivalent infix
expression.
2. The parentheses are not needed to designate the expression
unambiguously.
3. While evaluating the postfix expression the priority of the operators
is no longer relevant
We consider five binary operations: +, -, *, / and $ or ↑
(exponentiation). For these binary operations, the following in the
order of precedence (highest to lowest):
8 October 2020 priyankajangde@[Link] 35
Operator Precedence

8 October 2020 priyankajangde@[Link] 36

Infix and Postfix Notations
• Infix: operators placed between operands:
A+B*C
• Postfix: operands appear before their operators:-
ABC*+
• There are no precedence rules to learn in postfix notation, and
parentheses are never needed

8 October 2020 priyankajangde@[Link] 37

Infix to Postfix
Infix Postfix
A+B AB+
A+B*C ABC*+
(A + B) * C AB+C*
A+B*C+D ABC*+D+
(A + B) * (C + D) AB+CD+*
A*B+C*D AB*CD*+

8 October 2020 priyankajangde@[Link] 38

Infix to Postfix
A+B * C
(A + (B * C))
(A + (B C *) )
A B C * +

A + B * C + D
((A + (B * C)) + D )
((A + (B C*) )+ D)
((A B C *+) + D)
AB C * + D +
8 October 2020 priyankajangde@[Link] 39
Infix to postfix conversion
• Use a stack for processing operators (push and pop operations).
• Scan the sequence of operators and operands from left to right and
perform one of the following:
• output the operand,
• push an operator of higher precedence,
• pop an operator and output, till the stack top contains operator of a lower
precedence and push the present operator.

8 October 2020 priyankajangde@[Link] 40

The algorithm steps
1. Print operands as they arrive.
2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the
stack.
3. If the incoming symbol is a left parenthesis, push it on the stack.
4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a
left parenthesis. Discard the pair of parentheses.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
6. If the incoming symbol has equal precedence with the top of the stack, use association. If the
association is left to right, pop and print the top of the stack and then push the incoming operator. If
the association is right to left, push the incoming operator.
7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack
and print the top operator. Then test the incoming operator against the new top of stack.
8. At the end of the expression, pop and print all operators on the stack. (No parentheses should
remain.)
8 October 2020 priyankajangde@[Link] 41
Infix to Postfix Conversion
Requires operator precedence information

Operands:
Add to postfix expression.

Close parenthesis:
pop stack symbols until an open parenthesis appears.

Operators:
Pop all stack symbols until a symbol of lower precedence appears. Then push the
operator.

End of input:
Pop all remaining stack symbols and add to the expression.
8 October 2020 priyankajangde@[Link] 42
Infix to Postfix Rules
Current Operator Postfix string
Expression: symbol Stack
1 A A
A * (B + C * D) + E
2 * * A
3 ( *( A
becomes
4 B *( AB
AB C D * + * E + 5 + *(+ AB
6 C *(+ ABC
7 * *(+* ABC
8 D *(+* ABCD
Postfix notation
is also called as 9 ) * ABCD*+
Reverse Polish 10 + + ABCD*+*
Notation (RPN) 11 E + ABCD*+*E
12 ABCD*+*E+

8 October 2020 priyankajangde@[Link] 43

8 October 2020 priyankajangde@[Link] 44
8 October 2020 priyankajangde@[Link] 45
8 October 2020 priyankajangde@[Link] 46
8 October 2020 priyankajangde@[Link] 47
8 October 2020 priyankajangde@[Link] 48
8 October 2020 priyankajangde@[Link] 49
8 October 2020 priyankajangde@[Link] 50
Infix to Postfix
Example 1: Convert ((A – (B + C)) * D) ↑ (E + F) infix expression to
postfix form

8 October 2020 priyankajangde@[Link] 51

Solution of Example 1

8 October 2020 priyankajangde@[Link] 52

Infix to Postfix
Example: Convert infix expression (A+B)*(C-D)/(E+F) to postfix.

8 October 2020 priyankajangde@[Link] 53

Solution

8 October 2020 priyankajangde@[Link] 54

Conversion from infix to prefix:
The precedence rules for converting an expression from infix to
prefix are identical.
The only change from postfix conversion is that traverse the
expression from right to left and the operator is placed before the
operands rather than after them.
The prefix form of a complex expression is not the mirror image of
the postfix form.

8 October 2020 priyankajangde@[Link] 55

Infix to Prefix
Example 1: Convert the infix expression A + B – C into prefix
expression

8 October 2020 priyankajangde@[Link] 56

Solution

8 October 2020 priyankajangde@[Link] 57

8 October 2020 priyankajangde@[Link] 58
8 October 2020 priyankajangde@[Link] 59
8 October 2020 priyankajangde@[Link] 60
8 October 2020 priyankajangde@[Link] 61
8 October 2020 priyankajangde@[Link] 62
8 October 2020 priyankajangde@[Link] 63
8 October 2020 priyankajangde@[Link] 64
8 October 2020 priyankajangde@[Link] 65
8 October 2020 priyankajangde@[Link] 66
8 October 2020 priyankajangde@[Link] 67
8 October 2020 priyankajangde@[Link] 68
8 October 2020 priyankajangde@[Link] 69
Infix to Prefix
Example; (A-(B/C))*((D*E)-F)

8 October 2020 priyankajangde@[Link] 70

Solution

8 October 2020 priyankajangde@[Link] 71

Advantage

8 October 2020 priyankajangde@[Link] 72

Evaluation of postfix expression:
The postfix expression is evaluated easily by the use of a stack.
When a number is seen, it is pushed onto the stack; when an
operator is seen, the operator is applied to the two numbers that are
popped from the stack and the result is pushed onto the stack.
 When an expression is given in postfix notation, there is no need to
know any precedence rules.

8 October 2020 priyankajangde@[Link] 73

Evaluation of postfix expression:
Algorithm for evaluating postfix expression: Let P is an expression written in
postfix notation.
1) STACK=empty stack.
 2) Scan P from left to right and repeat step 3 and 4 for each symbol in P until end
of expression.
3) If an operand is encountered, push it on STACK.
 4) If an operator x encountered then;
a) Operand 2= pop (STACK).
b) Operand 1= pop (STACK).
c) Value= operand1 x operand 2.
d) Push value on STACK.
5) Return the value at top of the STACK.
6) Exit
8 October 2020 priyankajangde@[Link] 74
Example
Example 1: Evaluate the following postfix expression: 6 2 3 + – 3 8 2
/+*2↑3+

8 October 2020 priyankajangde@[Link] 75

Solution

8 October 2020 priyankajangde@[Link] 76

8 October 2020 priyankajangde@[Link] 77
Evaluation of postfix expression:
Example: Let us now consider an example. Suppose that we are
asked to evaluate the following postfix expression 6 2 + 5 9 * +

8 October 2020 priyankajangde@[Link] 78

Solution

8 October 2020 priyankajangde@[Link] 79

Evaluation of Prefix Expression:
Algorithm
1) Read prefix string from right to left until there is a data.
2) Repeat;
If char is operand add to prestack
If char is operator
–operand 1= pop prestack.
-operand 2= pop prestack.
-result= value after applying operator between operand 1 and
operand
-push the result into prestack.
3) pop prestack get required value.
8 October 2020 priyankajangde@[Link] 80
Example
Convert infix to prefix ((A-B)+C*(D+E))-(F+G)

8 October 2020 priyankajangde@[Link] 81

Solution

Out put_stack = GF+ED+C*BA-+-

Reversing the output_stack we get prefix expression: -+-AB*C+DE+FG

8 October 2020 priyankajangde@[Link] 82

Evaluation of prefix expression:

8 October 2020 priyankajangde@[Link] 83

Evaluation of prefix expression
Example: +-*+12/421$42

8 October 2020 priyankajangde@[Link] 84

Solution

8 October 2020 priyankajangde@[Link] 85

Example

8 October 2020 priyankajangde@[Link] 86

Solution

8 October 2020 priyankajangde@[Link] 87

Example

8 October 2020 priyankajangde@[Link] 88

Solution

8 October 2020 priyankajangde@[Link] 89

Animation of Tower of Hanoi
8 October 2020 priyankajangde@[Link] 91
8 October 2020 priyankajangde@[Link] 92
References / Study Material
Books for C Programming:
The C Programming Language, Brian W. Kernighan and Dennis M. Ritchie,
Prentice Hall of India.
Schaum’s Outline of Programming with C, Byron Gottfried, Tata McGraw-
Hill
Books on Data Structures:
Data Structures, Schaum’s Outline Series, Seymour Lipschutz, Tata McGraw-
Hill
Fundamentals of Data Strcutures in C , Ellis Horowitz, Satraj Sahni and
Susan Anderson-Freed, W. H. Freemn and Company
Classic Data Structures, D. Samanta, Prentice Hall of India.

8 October 2020 priyankajangde@[Link] 93

References / Study Material
Web references:
[Link]
Some useful software:
[Link]
Notes:
[Link]
Course related information and announcements:
[Link]
[Link]
8 October 2020 priyankajangde@[Link] 94
8 October 2020 priyankajangde@[Link] 95
 If you try to solve problems
yourself, you will learn
many things automatically.

8 October 2020 priyankajangde@[Link] 96