Introduction

What is a Stack?
A stack is a linear data structure that follows the Last-In-First-Out (LIFO)
principle. Think of it like a stack of plates: you can only add or remove plates from the
top.

Key Operations in stacks:

 Push: Add an element to the top of the stack.
 Pop: Remove the top element from the stack.
 Peek: View the top element without removing it.
 isEmpty: Check if the stack is empty.

Stacks in python are a dynamic data structure as they can grow (with increase in
number of elements) or shrink (with decrease in number of elements). A static data
structure, on the other hand, is the one that has fixed size.

A stack is a linear structures implemented in LIFO (Last In First Out) manner where
insertions and deletions are restricted to occur only at one end – stack’ s top. LIFO
means element last inserted would be the first one to be deleted. Thus, we can say that
a stack is a list of data that follows these rules:
1. Data can only be removed from the top (pop), i.e., the element at the top of the
stack. The removal of element from a stack is technically called POP operation.
2. A new data element can only be added to the top of the stack (push). The
insertion of element in a stack is technically called PUSH operation
Consider figure below that illustrates the operations (push and pop) on a stack.
Some Other Stack Terms in python
There are some other terms related to stacks, such as peek, overflow and Underflow.

Peek:
Refers to inspecting the value at the stack’s top without removing it; it is also
sometimes referred as inspection.

Overflow:
Refers to situation (ERROR) when one tries to push an item in stack that is full. This
situation occurs when the size of the stack is fixed and cannot grow further or there is
no memory left to accommodate new item.

Underflow:
Refers to situation (ERROR) when one tries to pop/ delete an item from an empty stack.
That is, stack is currently having no item and still one tries to pop an item. Consider
some examples illustrating stack-functioning in limited- size stack. (Please note, we have
bound fixed the capacity of the stack for understanding purposes.)

Implementing stacks in python

In python, you can use lists to implement stacks. Python offers us a convenient set of
methods to operate lists as stacks.
For various stack operations, we can use a list say stack and use python code as
described below:
Peek we can use: <stack> [top]
where < stack> is a list; top is an integer having value equal to len
(<stack>) -1.

Push we can use: <stack>. append (<item>)

when <item> is the item being pushed in the stack.
Pop we can use: <stack>. Pop ( )
it removes the last value from the stack and returns it.
Let us now implement a stack of through a program.

def push (stk, item):

Program Code:

Python program to implement stack operations.

STACK IMPLEMENTATION
“““
Stack: implemented as a list
top: integer having position o topmost element in stack
““ “
def is Empty (stk):
if stk == [ ]
return True
else:
returns False
def push (stk, item) :
stk. append (item)
top = len (stk) -1
def pop (stk):
if is Empty (stk) :
return “underflow”
else:
item = stk. Pop ( )
if len (stk) == 0:
top = None
else:
top = len (stk) -1
return item
def peek (stk) :
if is Empty (stk) :
return “underflow”
else:
top = len (stk) -1
return stk [top]
def Display (stk) :
if is Empty (stk) :
print (:stack empty”)
else:
top = len (stk) -1
print (stk[top], “<- top” )
for a in range (top- 1, -1, -1 ) :
print (stk [a])

#_main_
stack = [ ] # initially stack is empty
top = None
While True:
print (“STACK OPERATIONS”)
print (“1. Push”)
print (“2. Pop”)
print (“3. Peek”)
print (“4. Display stack”)
print ( “5. Exit”)
ch = int (input (“Enter your choice (1-5) :” ) )
if ch == 1 :
item = int (input (“Enter item:” ) )
push (stack, item)
 elif ch == 2 :
item = pop (stack)
if item ==”underflow”
print (“underflow” : stack is empty !” )
else:
print (“popped item is”, item)
elif ch == 3:
item = peek (stack)
if item ==”underflow”
print (“underflow! Stack is empty!”)
else:
print (“Topmost item is”, item)
elif ch == 4:
Display (stack)
elif ch == 5:
break
else:
print (“Invalid choice!” )
Sample run of the above program is as shown below:
Applications of Stacks in python

There are several applications and uses of stacks. The stacks are basically applied where
LIFO (Last in First Out) scheme is required

Reversing a line using stacks in python

A simple example of stack application is reversal of a given line. We can accomplish this
task by pushing each character on to a stack as it is read. When the line is finished,
characters are then popped off the stack, and they will come off in the reverse order as
shown in Figure below. The given line is: Stack.

Polish Strings using stacks in python

Another application of stacks is in the conversion of arithmetic expressions in high-level

programming language into machine readable form. As our computer system can only
understand and work on a binary language, it assumes that an arithmetic operation can
take place in two operands only e.g., A+ b, c D, D/A etc. But in our usual from an
arithmetic expression may consist of more than one operator and two operands
For example:
(A + B) C (D/(J + D)).

These complex arithmetic operations can be converted into polish string using stacks
which then can be executed in two operands and a operator form.
Polish string, named after a polish mathematician, Jan Lukasiewicz, refers to the
notation in which the operator symbol is placed either before its operands (prefix
notation) or after its operands (postfix notation) in contrast to usual form where
operator is placed in between the operands (infix notation).
Following table shows the three types of notations:

Conversion of infix Expression to Postfix

(Suffix) Expression

While evaluating an infix expression, there is an evaluation order according to which

I Brackets or Parenthesis,
II Exponentiation,
III Multiplication or Division,
IV Addition or Subtraction

Take place in the above specified order. The operators with the same priority (e.g.,
and/) are evaluated from left to right.

To convert an infix expression into a postfix expression, this evaluation order is taken
into consideration.

An infix expression may be converted into postfix from either manually or using a stack.
The manual conversion requires two passes: one for inserting braces and another for
conversion. However, the convert an infix expression into a postfix expression manually
are given below:

 Determine the actual evaluation order by inserting branches.

 Convert the expression in the innermost branches into postfix notation by putting
the operator after the operands.
 Repeat step (ii) until entire expression is converted into postfix notation.
Example: Convert (A+B) × C /D into postfix notation.
Solution:

Step 1: Determine the actual evaluation order by putting braces

=((A+B)×C)/D

Step 2: Converting expressions into innermost braces

=((AB+)×C)/D=(AB+C×) / D = AB +C × D /

Example: Convert((A+B)*C / D + E^F)) / G into postfix will be

=((((AB+B) *C) / D) +(E^F))/G

Converting expressions in the braces, we get

=((((AB+) *C)/D) + (EF^))/G

=(((AB+C*)/D) + EF^)/G
=((AB+C*D/) +EF^)/G= (AB + C * D/EF ^ +)/G
=AB + C * D/EF ^ +G/

Example: Give postfix from of the following expression

A* (B+(C+D) * (E+F)/*H

Solution: Evaluation order is

(A*(B+((C+D) * (E+F))/G)) *H
Converting expression in the braces, we get
=(A*(B+[(CD+) *(EF+)]/G)) *H=A*(B+ (CD+EF+ *)/G) * H
=A* (B+(CD+EF+ *G/)) * H=(A* (BCD + EF + *G/+))* H
=(ABCD+EF + *G/ + H = ABCD +EF +*G/+ *H*

Example: Give postfix from for A+[(B+C) + (D+E) * F]/G

Solution:
Evaluation order is: A +[{(B+C) + ((D+E) * F)}/G
Converting expressions in braces, we get
=A + [{(BC +) + (DE+) * F}/G] = A+ [{(BC +) + (DE + F *)}/G]
=A + [{BC + DE +F * +}/G] = A + [BC +DE +F * +G/]
=ABC +DE +F * +G / +

Example: Give postfix form of expression for the following: NOT A FOR NOT B NOT C

Solution:
The order of evaluation will be
((NOT A) OR ((NOT B) AND (NOT C)))
(As priority order of NOT, AND, OR)
= ((A NOT) OR ((B NOT) AND (C NOT)))
= ((A NOT) OR ((B NOT C NOT AND))
= A NOT B NOT C NOT AND OR
While converting from infix to prefix form, operation are put before the operands. Rest
of the conversion procedure is similar to that of infix to postfix conversion.
Example: Evaluation the postfix expression AB + C × D / IF A =2, B =3, C =4 and D
=5.

Solution. The expression given is AB + C × D/

Starting from left to right
Example: Evaluated the expression 562 + * 124 /- in tabular form showing stack
status every step.