Chapter 3: Stack
Introduction
Data structure is a specialized format of organizing, storing and accessing
data.
A string is a data structure that contains a sequence of characters, where
each element in the sequence is a single character. In contrast, a list is a
sequence data structure in which each element can be of a different data
type, such as integers, strings, or even other lists. Both strings and lists
support various operations such as reversal, slicing, and counting elements.
Thus, a data structure organizes multiple elements in a way that allows
efficient access, manipulation, and processing of the data it contains.
Stack and Queue are two fundamental data structures commonly used in
programming. While they are not built-in as distinct types in Python.
Understanding stacks and queues is important because they are widely used
in many algorithms and are fundamental to problem-solving in various
programming languages.
Stack
A stack is an ordered collection of elements where the addition of new
elements and the removal of existing elements always take place at the
same end called Top. TOP is the top of the stack. Stack is also called as
LIFO(Last-In First-Out).
[Link] Page 1
Application of Stack
applications of stack in real-life are:
Pile of clothes in an wardrobe.
Multiple chairs in a vertical pile.
Bangles worn on wrist.
Rearranging rail road cars.
Pile of boxes of eatables in pantry or on a kitchen shelf.
application of stack in programming are:
a) To reverse a string.
When we need to reverse a string, the string is traversed from the last
character till the first character. This is done by putting the characters
of a string in a stack.
b) redo/undo mechanism in text/image editor.
We use text/image editor for editing, we have options to redo/undo
the editing. The system uses a stack to keep track of changes made.
c) Backtracking.
While browsing the web, we move from one web page to another by
accessing links between them. in order to go back to the last visited
web page, we may use the back button on the browser. The history of
browsed pages is maintained as stack.
d) To solve Tower of Hanoi.
The Tower of Hanoi is a mathematical puzzle that involves moving a
stack of disks of different sizes from one rod to another, following
specific rules.
e) Expression Evaluation.
[Link] Page 2
While writing any arithmetic expression in a program, we may use
parentheses to order the evaluation of operators. While executing the
program, the compiler checks for matched parentheses. In case of
parentheses are mismatched, the compiler needs to throw an error. To
handle matching of parentheses, stack is used.
Operations on Stack
A stack is a linear data structure that follows the LIFO principle - Last In,
First Out. All insertions and deletions are done from one end only, known as
the TOP of the stack. Two fundamental operations performed on the stack
are PUSH and POP.
PUSH and POP Operations
PUSH adds a new element at the TOP of the stack. It is an insertion
operation. We can add elements to a stack until it is full. A stack is full when
no more elements can be added to it. Trying to add an element to a full
stack results in an exception called ‘overflow’.
POP operation is used to remove the top most element of the stack. It is a
delete operation. We can delete elements from a stack until it is empty.
Trying to delete an element from an empty stack results in an exception
called ‘underflow’.
[Link] Page 3
Implementation of Stack in Python
Stack is a linear and ordered collection of elements. The simple way to
implement a stack in Python is using the data type list. We can fix either of
the sides of the list as TOP to insert/remove elements. It is to be noted that
we are using built-in methods append() and pop() of the list for
implementation of the stack. As these built-in methods insert/delete
elements at the rightmost end of the list, hence explicit declaration of TOP is
not needed.
Let us write a program to create a STACK in which we will:
Insert / Delete elements.
Check if the STACK is empty or not.
Find the number of elements in the STACK.
Read the value of the topmost element in the STACK.
a) To create an empty stack named Stack.
Stack = list()
assigning an empty list to the identifier named Stack.
b) Check whether the stack is empty or not.
[Link] Page 4
c) A function named opPush to insert (PUSH) a new
element in stack. This function has two parameters - the name of the
stack in which the element is to be inserted (Stack) and the element
that needs to be inserted. we will use the built-in method append() of
list to add an element to the stack that always adds at the end of the
list. As there is no limit on the size of list in Python, the implemented
stack will never be full unless there is no more space available in
memory. Hence, we will never face ‘overflow’ (no space for new
element) condition for stack. it is dynamic stack.
d) A function named size to read the number of elements in the Stack.
We will use the len() function of list in Python to find the number of
elements in the Stack(size of Stack).
[Link] Page 5
e) A function named top to read the top most element present in the TOP
of the Stack.
f) A function named opPop to delete the topmost element from the stack.
It takes one parameter - the name of the stack from which element is
to be deleted and returns the value of the deleted element. The
function first checks whether the stack is empty or not. If it is not
empty, it removes the topmost element from it. We shall use the
built-in method pop() of Python list that removes the element from the
end of the list.
[Link] Page 6
g) A function named display to show the contents of the stack.
[Link] Page 7
Python code to implement a stack Operations
[Link] Page 8
Output
***************** Just for Reference to Read Once*****************
The BODMAS rule, BODMAS stands for Brackets, Of (or Orders), Division,
Multiplication, Addition, and Subtraction. By following this rule, you ensure
consistent and accurate calculations.
Here's a breakdown of the BODMAS rule:
Brackets: Calculations within brackets (or parentheses) are always
done first.
Orders (or Of): This includes powers, square roots, and other indices.
Division and Multiplication: These are performed from left to right in
the order they appear.
Addition and Subtraction: These are also performed from left to right
in the order they appear.
Example:
To solve the expression 2 + (3 x 4) - 10 / 2, you would follow these steps
using BODMAS:
Brackets: (3 x 4) = 12
The expression becomes: 2 + 12 - 10 / 2
Division: 10 / 2 = 5
The expression becomes: 2 + 12 - 5
Addition: 2 + 12 = 14
The expression becomes: 14 - 5
Subtraction: 14 - 5 = 9
Therefore, the solution to the expression is 9.
************************************************************
[Link] Page 9
Notations for Arithmetic Expressions
We write arithmetic expressions using operators in between operands, like x
+ y, 2 - 3 * y, etc. and use parentheses () to order the evaluation of
operators in complex expressions. These expressions follow infix
representation and are evaluated using BODMAS rule. Polish mathematician
Jan Lukasiewicz in the 1920's introduced a different way of representing
arithmetic expression, called polish notation.
To summaries, any arithmetic expression can be represented in any of the
three notations, Infix, Prefix and Postfix and are listed in below Table.
[Link] Page 10
How to convert infix expression to post expression
Algorithm
1. Print the operands as they arrive.
2. If stack is empty or contains a left parentheses on top, push the
incoming operator onto the stack.
3. If incoming symbol is '(', push it onto stack.
4. If incoming symbol is ')', pop the stack and print the operators until
the left parentheses is found.
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 lower precedence than the top of the
stack, pop and print the top. Then test the incoming operator against
the new top of the stack.
7. If the incoming operator has equal precedence with the top of the
stack, then pop and print the top of the stack and then push the
incoming operator.
8. At the end of the expression, pop and print all operators of stack.
[Link] Page 11
Conversion of infix expression to postfix expression using a stack.
Problem-1
Convert a given infix expression A+B*C into equivalent postfix expression
using a stack.
The final Postfix expression is ABC*+
Problem-2
Convert a given infix expression A*(B+C-D) into equivalent postfix
expression using a stack.
The final Postfix expression is ABC+D-*
[Link] Page 12
Problem-3
Convert a given infix expression (X + Y) / (Z*8) into equivalent postfix
expression using a stack.
The final Postfix expression is XY+Z8*/
Problem-4
Convert a given infix expression a*(b+c+d) into equivalent postfix
expression using a stack.
[Link] Page 13
[Link] Page 14
Evaluation of Postfix Expression
Stacks can be used to evaluate an expression in postfix notation.
For simplification, we are assuming that operators used in expressions are
binary operators.
Algorithm : Evaluation of postfix expression
Step 1: INPUT postfix expression in a variable, say postExp
Step 2: For each character in postExp, REPEAT Step 3
Step 3: IF character is an operand
THEN PUSH character on the Stack
ELSE POP two elements from the Stack, apply the operator on
the popped elements and PUSH the computed value onto
the Stack
Step 4: IF Stack has a single element
THEN POP the element and OUTPUT as the net result
ELSE OUTPUT “Invaild Postfix expression”
Ex-1
Evaluation of postfix expression 2 3 4 * +
The Final Result = 14
[Link] Page 15
Ex-2
Evaluation of postfix expression 3 4 * 2 5 * +
The Final Result = 22
[Link] Page 16
*****
[Link] Page 17