DATA STRUCTURES – STACK IMPLEMENTATION

Python Core Data Types:

Numeric – int, float, complex

Sequence – string , list , tuple

Mapping – dictionary

Sets – Set

Special – None

Boolean - boolean

Data Structure:

It represents how Data is stored /Organized in Computer’s Memory. A Data structure defines a mechanism
to store, organise and access data along with operations.

Implementation of Data Structure can be done in two ways:

Simple Data Structure: Built from Primitive Data Types (Integer, float, Boolean, Complex, String)

Compound Data Structure: Simple Data structure is used to form more complex data Structure. They are
classified into two Types.

1. Linear Data structure: Means elements are stored in sequential order example: Stack, Queue,
Linked list.

2. Non -Linear Data structure: Data can be stored in multilevel structure. Example: Trees, Graphs

Stack

✓ Stack is a linear Data Structure

✓ Stack is a list of elements in which an element may be inserted or deleted only at one end, called
the TOP of the stack.
✓ It follows the principle Last in First out( LIFO)
✓ LIFO means the element inserted last would be the first to be deleted.

Operation On stacks using list:

Declare my stack variable: stack =[]

PUSH: Insertion of an element on top of the stack is called PUSH.

[Link](item)

POP: Removal an element from the top of stack is called POP. (First check if the stack if empty)

[Link]()

DISPLAY: To display the elements of the stack. (First check if the stack if empty)

for i in range(len(stack)-1, -1, -1):

print(stack[i])
 or for i in stack[::-1]

print(i)

PEEK: To display the stack’s top without removing it. It is also called as inspection. (First check if the stack if
empty)

stack[-1] or stack[len(stack)-1]

Overflow : It refers to as situation, when one tries to push an element in stack that is full.

Underflow: It refers to a situation when one tries to pop/delete from empty stack.

if stack==[]: or if len(stack)==0:

#Basic Stack Program

stack=[]

def push(stack,item):

[Link](item)

print(item," got appended to the stack")

def pop(stack): # compulsory check if stack is empty

if stack==[]:

print("Underflow. No items to delete")

else:

print([Link]())

def peek(stack): # compulsory check if stack is empty

if stack==[]:

print("Underflow. No items in stack")

else:

print(stack[-1])

def display(stack): # reverse order

for i in range(len(stack)-1,-1,-1):

print(stack[i])

while True:

print("---------------------------------------")

print("[Link] [Link] 3. Peek 4. Display [Link]")

ch=int(input("enter Choice"))
 if ch==1:

item=int(input("enter item"))

push(stack,item)

elif ch==2:

pop(stack)

elif ch==3:

peek(stack)

elif ch==4:

display(stack)

elif ch==5:

print("Program Over")

break

else:

print("Enter a valid choice")

Applications of Stack

• Reversing a line
• Conversion of arithmetic expressions in high-level programming language into machine readable
form. Evaluation of postfix expression.

IMPORTANT POINTS

1. In stack operation, push() method takes the stack and the item to push as parameter ( def push(stack ,
item) . def push()) and pop() method takes the stack alone as the parameter and the item to be pushed is
got as input inside the function. (def push(stack) or def pop(stack)). Display() method takes the stack alone
as the parameter (def display(stack))

2. When pop() function is asked, first check if the stack is empty and display “Stack Underflow” , else use
the syntax of pop function to pop the last element from the stack. Kindly note that only when an element is
to be removed from stack, use pop method.

Syntax for pop is <stack name> . pop()

def pop(stack):
if stack==[]:
print(“Stack Underflow”)
else:
print([Link]())

3. When display() function is asked, first check if the stack is empty and display “Stack Underflow” , else
always display the stack in reverse order.
 def display(stack):
if stack==[]:
print(“stack underflow”)
else:
print(“the stack elements are””)
for i in range(len(stack)-1,-1,-1):
print(stack[i])

4. If the output in the question is like If all the elements from the stack should be popped out and displayed
and finally underflow message has to be printed:
The pop operation must display
Govind
vishwa
Balu
UNDER FLOW
Then the pop function should be coded in the following format.
def pop(stack):
while True:
if stack==[]:
print(“underflow”)
break
else:
print([Link]())

5. Use variable name as “stack” if no name is given in the question. Declare the stack variable before the
function definition.
stack = []
6. For questions like
a) For example : if the list with customer details are as follows:

[“sid”,”Delux”]
[“Rahul”,”Standard”]
[“Jerry”,”Delux”]
Consider that only one single list is passed to the push operation and not nested list.
Stack=[]
def push(stack , L): # where L contains [customer_name,Room Type].
if L[1]==”Delux”:

b) For example : if the list with customer details are as follows :

[[“sid”,”Delux”] , [“Rahul”,”Standard”] , [“Jerry”,”Delux”]]

Consider the element as nested list
Stack=[]
def push(stack , L): # L contains nested list
for I in L:
if I[1]==”Delux”:
 STACK PROGRAMS

1. You have a stack named MovieStack that contains records of movies. Each movie record is represented
as a list containing movie_title, director_name, and release_year. Write the following user-defined
functions in Python to perform the specified operations on the stack MovieStack:
(I) push_movie(MovieStack, new_movie): This function takes the stack MovieStack and a new movie record
new_movie as arguments and pushes the new movie record onto the stack.
(II) pop_movie(MovieStack): This function pops the topmost movie record from the stack and returns it. If
the stack is empty, the function should display "Stack is empty".
(III) peek_movie(MovieStack): This function displays the topmost movie record from the stack without
deleting it. If the stack is empty, the function should display "None".

MovieStack=[ ]
def push_movie(MovieStack, new_movie):
[Link](new_movie)

def pop_movie(MovieStack):
if MovieStack == []:
print("Stack is empty" )
else:
return [Link]()

def peek_movie(MovieStack):
if MovieStack == []:
print("None" )
else:
print(MovieStack[-1])

2. Write the definition of a user-defined function push_odd(M) which accepts a list of integers in a
parameter M and pushes all those integers which are odd from the list M into a Stack named OddNumbers.
Write the function pop_odd() to pop the topmost number from the stack and return it. If the stack is
empty, the function should display "Stack is empty".
Write the function disp_odd() to display all elements of the stack without deleting them. If the stack is
empty, the function should display "None".
For example:
If the integers input into the list NUMBERS are: [7, 12, 9, 4, 15]
Then the stack OddNumbers should store: [7, 9, 15]

Odd_numbers=[ ]
def push_odd(M, odd_numbers):
for i in M:
if i % 2 != 0:
odd_numbers.append(i)

def pop_odd(odd_numbers):
if odd_numbers == []:
print("Stack is empty" )
else:
return odd_numbers.pop()
def disp_odd(odd_numbers):
if odd_numbers == []:
print("None" )
 else:
for i in range(len(odd_numbers)-1,-1,-1):
print(odd_numbers[ i ])

3. A dictionary, StudRec, contains the records of students in the following pattern:

{admno: [m1, m2, m3, m4, m5]}, i.e., Admission No. (admno) as the key and 5 subject
marks in list as the value. Write the following user-defined functions to perform the specified operations on
the stack named BRIGHT.
(i) Push_Bright(StudRec): it takes the dictionary as an argument and pushes the admno of the dictionary
into the stack named BRIGHT of those students with a total mark >350.
For Example: if the dictionary StudRec contains the following data:
StudRec={101:[80,90,80,70,90], 102:[50,60,45,50,40], 103:[90,90,99,98,90]}
Thes Stack BRIGHT Should contain: [101,103]
(ii) Pop_Bright(): It pops all the element from the stack and displays them. Also, the
function should display “Bright is Empty” when there are no elements in the stack.
The Output Should be:
103
101
Bright is Empty

BRIGHT = []
def Push_Bright(StudRec):
for i in StuRec:
total = StuRec[i][0]+ StuRec[i][1]+ StuRec[i][2]+ StuRec[i][3]+ StuRec[i][4]
if total > 350:
[Link](i)

def Pop_Bright():
while True:
if BRIGHT == [ ]:
print('Bright is Empty')
break
else:
print([Link]())

4. You have a stack named OrderStack that contains order records. Each order record is represented as a
list containing order_id, customer_name, and order_date.
Write the following user-defined functions in Python to perform the specified operations on the stack
OrderStack:
• push_order(OrderStack, new_order): This function takes the stack OrderStack and a new order
record new_order as arguments. It only adds the order to the stack if the order ID is greater than 1000.
• pop_order(OrderStack): This function pops the topmost order record from the stack and returns it.
If the stack is already empty, the function should display "Underflow".
• peek_order(OrderStack): This function displays the topmost element of the stack without deleting
it. If the stack is empty, the function should display 'None'.

Orderstack=[ ]
def push_order(OrderStack, new_order):
if new_order[0] > 1000:
[Link](new_order)
def pop_order(OrderStack):
if OrderStack == []:
print(“Underflow”)
else:
return [Link]()

def peek_order(OrderStack):
if OrderStack == []:
print(“None)
else:
print( OrderStack[-1])
5. Vedika has created a dictionary containing names and marks as key-value pairs of 5 students. Write a
program, with separate user-defined functions to perform the following operations:
Push the keys (name of the student) of the dictionary into a stack, where the corresponding value (marks)
is greater than 70. Pop and display the content of the stack.
The dictionary should be as follows:
d={“Ramesh”:58, “Umesh”:78, “Vishal”:90, “Khushi”:60, “Ishika”:95}
The Stack should contain: [“Umesh”, “Vishal”, “Ishika”]
stack=[]
def push(stack,d):
for i in d:
if d[i]>70:
[Link](i)
def pop(stack):
while True:
if stack==[]:
print(“Stack Empty”)
break
else:
print([Link]())

6. A stack named FruitStack, implemented using list, contains records of some fruits. Each record is
represented as a dictionary with keys “Name”,”Orgin”,”Price” and “Expiry”. A sample record is given here:

{“Name”:”Apple” , “Origin”:”France” , “Price:120 , “Expiry”:”12-08-2025”}

Write the following user-defined functions in python to perform the specific operations on FruitStack.

a) Push_fruit(FruitStack, Fruit) : This function takes the stack FruitStack and a new record Fruit as
arguments and pushes the record stored in Fruit onto FruitStack IF THE Price is less than 100.
b) Pop_fruit(FruitStack) : This function pops the topmost record from the stack and returns it. If the
stack is already empty, the function should display “UNDERFLOW”
c) Display(FruitStack) : This function displays all the elements of the stack starting from the topmost
element. If the stack is empty, the function should display “EMPTY STACK”.

def push_fruit(FruitStack, Fruit):

if Fruit['Price']<100:

[Link](Fruit)
 def pop_fruit(FruitStack):

if FruitStack==[]:

print('UNDERFLOW')

else:

return [Link]()

def display(FruitStack):

if FruitStack==[]:

print('EMPTY STACK')

else:

for ele in FruitStack[::-1]:

print(ele)

7. Write a Python program to accept 10 integers from the user. If the entered number is a three digit even
integer, push it onto a stack. After all inputs are taken, pop all the three-digit even integers from the stack
and display them. For example, if the user enters 12, 31, 320, 457, 6, 92, 924, 220, 1, 218, then the stack
should contain :
320, 924, 220, 218
and the output of the program should be :
218 220 924 320

Stack=[]

for i in range(10):

Num=int(input("Integer:"))

if Num>=100 and Num<=999 and Num%2==0:

[Link](Num)

while Stack:

print([Link](), end=' ')

8. A dictionary, StudRec, contains the records of students in the following pattern:

{admno: [m1, m2, m3, m4, m5]}, i.e., Admission No. (admno) as the key and 5 subject
marks in list as the value. Write the following user-defined functions to perform the specified operations on
the stack named BRIGHT.
(i) Push_Bright(StudRec): it takes the dictionary as an argument and pushes the admno of the dictionary
into the stack named BRIGHT of those students with a total mark >350.
For Example: if the dictionary StudRec contains the following data:
StudRec={101:[80,90,80,70,90], 102:[50,60,45,50,40], 103:[90,90,99,98,90]}
Thes Stack BRIGHT Should contain: [101,103]
(ii) Pop_Bright(): It pops all the element from the stack and displays them. Also, the
function should display “Bright is Empty” when there are no elements in the stack.
The Output Should be:
103
101
Bright is Empty
BRIGHT=[]
def Push_Bright(StudRec,BRIGHT):
for i in StudRec:
marks=StudRec[i]
if sum(marks)>350:
[Link](i)
def Pop_Bright(BRIGHT):
while True:
if BRIGHT==[]:
print(“BRIGHT IS EMPTY”)
break
else:
print([Link]())

9. A list containing records of products as

L = [("Laptop", 90000), ("Mobile", 30000), ("Pen", 50), ("Headphones", 1500)]
Write the following user-defined functions to perform operations on a stack named Product to:

I. Push_element() – To push an item containing the product name and price of products costing more
than 50 into the stack.
Output: [('Laptop', 90000), ('Mobile', 30000), ('Headphones', 1500)]
II. Pop_element() – To pop the items from the stack and display them. Also, display "Stack Empty"
when there are no elements in the stack.
Output:
('Headphones', 1500)
('Mobile', 30000)
('Laptop', 90000)
Stack Emply

Product=[]
def Push_element(L,Product):
for i in L: # for i in range(len(L)):
if i[1]>50: # if L[i][1]>50:
[Link](i)
def Pop_element(Product):
while True:
if Product==[]:
print(“Stack empty”)
break
else:
print([Link]())

10. You have a stack named BooksStack that contains records of books. Each book record is
represented as a list containing book_title, author_name, and publication_year.

Write the following user-defined functions in Python to perform the specified operations on the stack
BooksStack:
I push_book(BooksStack, new_book): This function takes the stack BooksStack and a new book
record new_book as arguments and pushes the new book record onto the stack.
II pop_book(BooksStack): This function pops the topmost book record from the stack and returns
it. If the stack is already empty, the function should display "Underflow".
III peek(BookStack): This function displays the topmost element of the stack without deleting it. If
the stack is empty, the function should display 'None'.

BooksStack=[]
def push_book(BooksStack,new_book):
[Link](new_book)
def pop_book(BooksStack):
if BooksStack==[]:
print(“Underflow”)
else:
return [Link]()
def peek(BooksStack):
if BooksStack==[]:
print(“None”)
else:
print(BooksStack[-1])

11. Write the definition of a user-defined function push_even(N) which accepts a list of integers in a
parameter 'N' and pushes all those integers which are even from the list 'N' into a stack named
'EvenNumbers'.

Write function pop_even() to pop the topmost number from the stack and return it. If the stack is already
empty, the function should display 'Empty'.Write function

Disp_even() to display all elements of the stack without deleting them. If the stack is empty, the function
should display 'None'. For example, if the integers input into the list 'VALUES' are: [10, 5, 8, 3, 12]then the
stack 'EvenNumbers' should store: [10, 8, 12]

EvenNumbers=[]
def push_even(N,EvenNumbers):
for i in N:
if i%2==0:
[Link](i)
def pop_even(EvenNumbers):
if EvenNumbers==[]:
print(“Empty”)
else:
return [Link]()
def Disp_even():
if EvenNumbers==[]:
print(“None”)
else:
for i in EvenNumbers[::-1]:
print(i)

12. A list, NList contains following record as list elements:[City, Country, distance from Delhi]

Each of these records are nested together to form a nested list. Write the following user-defined functions in
Python to perform the specified operations on the stack named travel.
(i) Push_element(NList):It takes the nested list as an argument and pushes a list object containing the name
of the city and country, which are not in India and whose distance is less than 3500 km from Delhi.(ii)
Pop_element():It pops the objects from the stack and displays them. Also, the function should display
"Stack Empty" when there are no elements in the stack.

For example:If the nested list contains the following data:NList = [['New York', 'U.S.A', 11734],
['Naypyidaw', 'Myanmar', 3219], ['Dubai', 'UAE', 2194], ['London', 'England', 6693], ['Gangtok', 'India',
1580], ['Columbo', 'Sri Lanka', 3405]]The stack should contain:['Naypyidaw', 'Myanmar'], ['Dubai',
'UAE'],['Columbo', 'Sri Lanka']

The output should be:['Columbo', 'Sri Lanka'] , ['Dubai', 'UAE'], ['Naypyidaw', 'Myanmar'] ,Stack Empty

travel=[]
def Push_element(NList):
for i in Nlist:
if i[1] != “India” and i[2] < 3500:
[Link]([i[0],i[1]])
def Pop_element():
while True:
if travel==[]:
print(“Stack Empty”)
break
else:
print([Link]( ) , end=”, “)

13. Write a function in Python, Push(SItem) where SItem is a dictionary containing the details of stationary
items: {Sname : price}. The function should push the names of those items into the stack whose price is
greater than 75. Also display the count of elements pushed into the stack. For example: If the dictionary
contains the following data: SItem = {'Pen':106, 'Pencil':59, 'Notebook':80, 'Eraser':25}The stack should
contain:

Notebook
Pen

The output should be: The count of elements in the stack is 2

Stack=[]
def Push(SItem, Stack):
for i in SItem:
if SItem[i] > 75:
[Link](i)
print("The count of elements in the stack is " , len(Stack))

14. A stack, named ClrStack, contains records of some colors. Each record is represented as a tuple
containing four elements:(ColorName, RED, GREEN, BLUE)ColorName is a string, and RED, GREEN,
BLUE are [Link] example, a record in the stack may be:('Yellow', 237, 250, 68)

Write the following user-defined functions in Python to perform the specified operations on ClrStack:

(i) push_Clr(ClrStack, new_Clr): This function takes the stack ClrStack and a new record new_Clr as
arguments and pushes this new record onto the stack.
(ii) pop_Clr(ClrStack): This function pops the topmost record from the stack and returns it. If the stack is
already empty, the function should display the message:Underflow

(iii) isEmpty(ClrStack): This function checks whether the stack is empty. If the stack is empty, the function
should return True, otherwise the function should return False.

15. Write the following user-defined functions in Python:

(i) push_trail(N, myStack): Here N and myStack are lists, and myStack represents a stack. The function
should push the last 5 elements from the list N onto the stack myStack. For example, if the list N is:[1, 2, 3,
4, 5, 6, 7] then the function push_trail() should push the elements: 3, 4, 5, 6, 7 onto the stack. Therefore, the
value of stack will be:[3, 4, 5, 6, 7]. Assume that N contains at least 5 elements.

(ii) pop_one(myStack): The function should pop an element from the stack myStack, and return this
element. If the stack is empty, then the function should display the message:

16. A stack named KeyStack contains records of some computer keyboards. Each record is represented as a
list containing Make, Keys, Connectivity. The Make and Connectivity are strings, and Keys is an integer.
For example, a record in the stock may be ('Hitech', 105, 'USB').

Write the following user-defined functions in Python to perform the specified operations on KeyStack:

push_key(KeyStack, new_key): This function takes the stock KeyStack and a new record new_key as
arguments and pushes this new record onto the stack.

pop_key(KeyStack): This function pops the topmost record from the stack and returns it. If the stack is
already empty, the function should display the message "Underflow".

isEmpty(KeyStack): This function checks whether the stack is empty. If the stack is empty, the function
should return True, otherwise the function should return False.

17. Write the following user-defined functions in Python:

push_vowels(S, St): Here S is a string and St is a list representing a stack. The function should push all the
vowels of the string S onto the stack St.
For example, if the string S is "Easy Concepts", then the function push_vowels() should push the elements
'E', 'a', 'o', 'e' onto the stack.
pop_one(St): The function should pop an element from the stack St and return this element. If the stack is
empty, then the function should display the message "Stack Underflow", and return None.
display_all(St): The function should display all the elements of the stack St, without deleting them. If the
stack is empty, the function should display the message "Empty Stack".

18. Consider a list named Nums which contains random integers.

Write the following user-defined functions in Python and perform the specified operations on a stack
named BigNums.

i. PushBig(): It checks every number from the list Nums and pushes all such numbers which have 5 or more
digits into the stack BigNums.

ii. PopBig(): It pops the numbers from the stack BigNums and displays them. The function should also
display "Stack Empty" when there are no more numbers left in the stack.
Example: If the list Nums contains the following data:
Nums = [213, 10025, 167, 254923, 14, 1297653, 31498, 386, 92765]

Then on execution of PushBig(), the stack BigNums should store:

[10025, 254923, 1297653, 31498, 92765]

And on execution of PopBig(), the following output should be displayed:

92765
31498
1297653
254923
10025
Stack Empty

19. A dictionary emp contains eno and age of employees. Two empty list stack_eno and stack_age will be
used as stack. Two functions push_emp() and pop_emp() are defined and perform the following operations:

(a) Push_emp() :- It reads dictionary emp and add keys into stack_eno and values into stack_age for all
employees whose age is more than 45.

(b) Pop_emp() :- it removes last eno and age from both list and print “underflow” if there is nothing to
remove. For example

emp={101:56,102:45,103:38,104:47,105:35,106:28} values of stack_eno and stack_age after push_emp()

[101,104] and [56,47]

20. A dictionary, d_city contains the records in the following format: {state:city} Define the following
functions with the given specifications:

(i) push_city(d_city) : It takes the dictionary as an argument and pushes all the cities in the stack CITY
whose states are of more than 4 characters.

(ii) pop_city(): this function pops the cities and displays “Stack empty” when there are no more cities in the
stack.

(iii) peek(d_city) : This function displays the topmost element of the stack without deleting it. If the stack is
empty the function should display ‘None’.
21. Write a function in Python push(EventDetails) where EventDetails is a dictionary containing the
number of persons attending the events– {EventName : NumberOfPersons}. The function should push the
names of those events in the stack named ‘BigEvents’ which have number of persons greater than 200. Also
display the count of elements pushed on to the stack.

Write the function pop(BigEvents) that removes the top element of the stack on its each call. Also write the
function calls. For example: If the dictionary contains the following data: EventDetails ={“Marriage”:300,
“Graduation Party”:1500, “Birthday Party”:80, “Get together” :150}

The stack should contain :-

Marriage

Graduation Party

The output should be: The count of elements in the stack is 2