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).
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.
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’
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.
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).
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.
g) A function named display to show the contents of the stack.
Python code to implement a stack Operations
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.
***********************************************************
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.
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.
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-*
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.
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
Ex-2
Evaluation of postfix expression 3 4 *25 Final
*****