Unit 2

Stack
◆ Stack is a linear data structure

◆ Follows the LIFO (Last In First Out) principle .

Follows a particular order in which the
operations are performed
◆ Last element inserted into the stack is the
first element to be removed

◆ Behaves like a stack of plates, where the last

plate added is the first one to be removed.

2
3
 Operations of Stack

◆ Push: Adds an element to the top of the stack.

● Pop: Removes the top element from the stack.

● Peek: Returns the top element without removing it.

● IsEmpty: Checks if the stack is empty.

● IsFull: Checks if the stack is full (in case of fixed-size arrays).

4
 Implementation of Stack

◆ Stacks can be implemented using using an array / linked list .

◆ In array-based stack, the elements are stored in a contiguous block of memory
◆ Top element of the stack is the element at the highest index

5
 Working of Stack Data Structure

◆ TOP variable is used to keep track of the top element in the stack.

● Initialy the stack, set TOP = -1 . It means stack is empty

● PUSH Operation : Increase the value of TOP by 1 and place the new element in the
position pointed to by TOP.

● POP Operation :Return the element pointed to by TOP and reduce its value by 1.

● Before pushing, check if the stack is already full

● Before popping, check if the stack is already empty

6
7
 Algorithm of Stack

PUSH Operation
Algorithm push(stack, element)
if top==maxindex
write OverflowError("Stack is full")
else
{
top=top+1
stack[top] = element
}

OVERFLOW CONDITION : Stack Full

8
 Algorithm of Stack

POP Operation
Algorithm pop(stack)
if top==-1
write UnderflowError("Stack is empty")
else
{
element = stack[top]
top= top-1
}
return element

UNDERFLOW CONDITION : Stack Empty

9
 Implementation of Stack

◆ Use of Array and TOP variable

◆ #define MAX 10
struct stack
{
int items[MAX];
int top;
};

typedef struct stack st;

10
 Create Stack

void createemptyStack(st *s)

{
s->top = -1;
}

11
 Full Stack

int isfull(st *s)

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

12
 Empty Stack

int isempty(st *s)

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

13
 PUSH Operation

void push(st *s, int newitem)

{
if (isfull(s))
{
printf("STACK FULL");
}
else
{
s->top++;
s->items[s->top] = newitem;
}
}

14
 POP Operation

void pop(st *s)

{
if (isempty(s))
{
printf("\n STACK EMPTY \n");
}
else
{
printf("Item popped= %d", s->items[s->top]);
s->top--;
}
}

15
 Complexity Analysis

PUSH Operation
◆ PUSH operation adds an element on top of the stack

◆ Top pointer points to the newly pushed element

◆ It takes one parameter and pushes it onto the stack.

◆ Time Complexity: O(1) PUSH Operation takes a single memory allocation operation which is
done in constant time.

◆ Space Complexity : O(1), As no extra space is being used.

16
 Complexity Analysis

POP Operation
◆ POP operation removes the topmost element in the stack and returns an error if the stack is already
empty

◆ Time Complexity: O(1), In array implementation, only an arithmetic operation is performed i.e., the top
pointer is decremented by 1. This is a constant time function.

◆ Space Complexity : O(1), No extra space is utilized for deleting an element from the stack

17
 Applications of STACK

● Reverse a word

● Browser history

● Undo/Redo Operations

● Function Calls

● Recursion

● Expression Evaluation and Parsing

18
 Arithmetic Expression

∙ Stack is very effective in evaluating arithmetic expressions

∙ Expressions are represented in Infix notation

∙ Each operator is written between two operands (i.e., A + B)

∙ ( A + B ) * C and A + ( B * C )

∙ Parentheses or some operator-precedence convention are used to change the order

of operators and operands in an arithmetic expression

19
 Evaluation of Arithmetic Expression

Polish notation (Prefix notation)

● Operator is placed before its two operand
● No parentheses are required
● +AB

Reverse Polish notation( Postfix notation)

● Operator is placed after its two operands
● No parentheses are required
● AB+

20
 Evaluation of Arithmetic Expression

● Stack-organized computers are better suited for post-fix notation than infix notation

● Infix notation must be converted to the postfix notation.

● Conversion from infix notation to postfix notation must take into consideration the operational hierarchy

● Levels of precedence for Binary operators

Highest: Exponentiation (^)

Next highest: Multiplication (*) and division (/)

Lowest: Addition (+) and Subtraction (-)

21
 Examples of Conversion

Example 1 : Convert infix to Post fix

Infix notation: (A-B)*[C/(D+E)+F]
Post-fix notation: AB- CDE +/F +*

Example 2 : Convert Infix to Postfix

Infix notation : A + B * C + D
Postfix Notation : A B C * + D +

Example 3 : Convert Infix to Postfix

Infix notation : A * B + C * D
Postfix Notation : A B * C D * +

Example 4 : Convert Infix to Postfix

Infix : ((A + B) – C * (D / E)) + F
Postfix: AB+CDE/*-F+

22
 Example Conversion

Example 5 : Convert Infix to Prefix

Infix notation : A * B + C * D
Pre-fix Notation : + * A B * C D

Example 6 : Convert Infix to Prefix

Infix notation : A + B * C + D
Pre-fix Notation : + + A * B C D

23
 Evaluate Postfix Expression using STACK

Create a stack to store the operands.

1) Scan the postfix expression from left to right.
2) If the element is an operand, push it onto the stack.
3) If the element is an operator, pop the top two operands from the stack, apply the operator to
them, and push the result back onto the stack.
4) Repeat steps 3 and 4 until the end of the postfix expression is reached.
5) Operand at the top of the stack is the result of the expression.

For example –
Infix notation: (2+4) * (4+6)

Post-fix notation: 2 4 + 4 6 + *

Result: 60
24
25
Evaluate 234*+

26
Evaluate 3 4 * 2 5 * +

27
 Algorithm Evaluation of Postfix Expression

Algorithm postfix_evaluation(postfix_expression)
stack = []

for element in postfix_expression:

if is_operand(element):
push(stack, element)
else:
operand1 = pop(stack)
operand2 = pop(stack)
result = apply_operator(operand1, operand2, element)
push(stack, result)

return pop(stack)

28
 Infix to Postfix Expression

Create an empty stack.

1) Scan the infix expression from left to right.

2) For each element in the infix expression:
● If the element is an operand, append it to the postfix expression.
● If the element is an opening parenthesis, push it onto the stack.
● If the element is a closing parenthesis, pop operands from the stack and append them to the
postfix expression until the opening parenthesis is popped.
● If the element is an operator, pop operands from the stack and append them to the postfix
expression until an operator with higher or equal precedence is encountered at the top of the
stack.
● Then, push the current operator onto the stack.
3) Pop all remaining operands from the stack and append them to the postfix expression.

29
 Convert Infix a+b*c+d to Postfix

Infix Expression Stack Postfix Expression

a+b * c+d empty empty
+b*c+d empty a
b*c+d + a
*c+d + ab
c+d +* ab
+d +* abc
d + abc*+
empty + abc*+d
empty empty abc*+d+

30
 Convert Infix ((A + B) – C * (D / E)) + F to Postfix

Infix Expression Stack Postfix Expression

((A + B) – C * (D / E)) + F Empty empty
(A + B) – C * (D / E)) + F ( empty
A + B) – C * (D / E)) + F (( empty
+ B) – C * (D / E)) + F (( A
B) – C * (D / E)) + F ((+ A
) – C * (D / E)) + F ((+ AB
– C * (D / E)) + F ( AB+
C * (D / E)) + F (- AB+
* (D / E)) + F (- AB+C
(D / E)) + F (-* AB+C

31
D / E)) + F (-*( AB+C
/ E)) + F (-*( AB+CD
E)) + F (-*(/ AB+CD
)) + F (-*(/ AB+CDE
)+F (-* AB+CDE /
+F AB +CDE / * -
F + AB + CDE/ * -
empty + AB + CDE/ * - F
empty empty AB + CDE / * - F +

32
 Examples Infix to Postfix

Example 1 : Infix Expression ((A + B) – C * (D / E)) + F

Convert to Postfix
AB+CDE/*-F+
Example 2 : Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q
Convert to Postfix
KL+MN*-OP^W*U/V/T*+Q+
Example 3 : Infix expression a+b*(c^d-e)^(f+g*h)-i
Convert to Postfix
abcd^e-fgh*+^*+i-

33
 Infix to Prefix Expression

Infix Expression : K + L - M * N + (O^P) * W/U/V * T + Q

Reverse Infix Expression : Q + T * V/U/W * ) P^O(+ N*M - L + K

Apply the algorithm for conversion to Reversed Infix Expression

34
 Algorithm for Infix to Prefix

● First, reverse the infix expression

● Scan the expression from left to right
● Whenever the operands arrive, print them
● If the operator arrives and the stack is found to be empty, then simply push the operator into the stack
● If the incoming operator has higher precedence than the TOP of the stack, push the incoming operator
into the stack.
● If the incoming operator has the same precedence with a TOP of the stack, push the incoming operator
into the stack.
● If the incoming operator has lower precedence than the TOP of the stack, pop, and print the top of the
stack. Test the incoming operator against the top of the stack again and pop the operator from the stack
till it finds the operator of a lower precedence or same precedence.
● If the incoming operator has the same precedence with the top of the stack and the incoming operator
is ^, then pop the top of the stack till the condition is true. If the condition is not true, push the ^ operator.
● When we reach the end of the expression, pop, and print all the operators from the top of the stack.
● If the operator is ')', then push it into the stack.
● If the operator is '(', then pop all the operators from the stack till it finds ) opening bracket in the stack.
● If the top of the stack is ')', push the operator on the stack.
● At the end, reverse the output.

35
36
37