DATA STRUCTURE
In computer science, a data structure is defined as a specialized format for organizing,
processing, retrieving, and storing data. It provides a way to manage and manipulate
data efficiently, based on the operations that need to be performed.
STACKS
● Definition: A stack is a linear data structure that follows the Last In, First Out
(LIFO) principle. The last element added is the first one to be removed.
● Analogy: Think of a stack of plates; you can only add or remove the top of the
stack.
BASIC OPERATIONS ON STACKS
● Push: Adds an element to the top of the stack.
● Pop: Removes the element from the top of the stack.
● Peek/Top: Returns the element at the top of the stack without removing it.
● IsEmpty: Checks if the stack is empty.
● Size: Returns the number of elements in the stack.
APPLICATIONS OF STACKS
1. Reversing a word/line: This can be accomplished by pushing each character onto a
stack as it is read. When the line is finished, characters are popped off the stack and
they will come off in the reverse order.
2. The compilers use stacks to store the previous state of a program when a function
is called during recursion.
3. Undo mechanism in Text editors by keeping all the text changes in a stack.
IMPLEMENTATION OF STACKS USING LIST
The implementation of stack can be done using a list. We can restrict the list operations
so that insertion and deletion can be done at top end only.
Basic operations performed on stack are:
1. Creating a stack
2. Push/Adding elements to the stack
3. Checking for empty stack
4. Pop/Deleting elements from a stack
5. Traversal/Displaying a stack
List methods used and Important things to remember while implementing stacks
through python program
1) [Link](element) – It is used to implement push operations(used to append or
add elements at the end of the list)
2) [Link]() –It is used to implement pop operations(removing elements at the end). It
also returns the element deleted.
3) list[::-1]-List slicing is used to print the elements in the reverse order from top to
bottom]
4) top=len(list)-1 (index of last element)
5) stack - LIFO(Last In First Out)
6) Adding an element is called Push and deleting an element is called Pop. ( through
one end(Top) only)
PROGRAM TO IMPLEMENT THE STACK
We will first write the definition of the following functions and then we will call them
through a menu-based program.
● Push() (to add elements)
● Pop() (to delete last element)
● Peek() ( to view top most element)
● Isempty() ( returns true when the stack is empty, false otherwise)
● Display() ( display the stack, vertically, Top to down)
def push(element,stk): #element to be pushed and stk is a
list
[Link](element)
def pop1(stk): #removes one element,which is added last
if stk==[]:
print("Underflow")
else:
x=[Link]()
print(x, "deleted")
def peek(stk): # display top element
if stk==[]:
print("underflow")
else:
print(stk[-1]) # print last element(topmost)
def display(stk):
if stk!=[]:
print("stack elements top to down")
stack=stk[::-1]
for i in stack:
print(i)
else:
print('Underflow')
def isEmpty(stk):
if stk==[]:
return True
else:
return False
# Menu based program to call the above functions
stk=[] # initialise the stack
while True:
print("Press 1 to add an element: ")
print("Press 2 to delete an element: ")
print("Press 3 to display the elements of the stack: ")
print("Press 4 to check if the stack is empty or not: ")
print("Press 5 to view the topmost element: ")
choice=int(input("Enter your choice: "))
if choice==1:
x=int(input("Enter the element to be pushed: "))
push(x,stk)
elif choice==2:
pop1(stk)
elif choice==3:
display(stk)
elif choice==4:
print(isEmpty(stk)) # print the return value T/F
elif choice==5:
peek(stk)
else:
print("wrong choice!!")
ch=input("\nPress y to continue: ")
if ch!="y":
break
PRACTICE QUESTIONS BASED ON CBSE PREVIOUS YEAR
QUESTIONS:
Please note that in the above program the PUSH() function was adding only ONE
element when called and similarly the POP1() function was deleting ONE element.
However, in the following programs, the push function may add multiple elements to
the stack in one go and pop1() function may delete the entire stack (as per the question
asked)
Q1. Write the code for the two functions given below:
(i) PUSH(N): This function accepts a list of names, N as parameters. It then pushes only
those names in the stack named OnlyA which contain the letter 'A'.
(ii) POPA(OnlyA): This function pops each name from the stack OnlyA and displays it.
When the stack is empty, the message "EMPTY" is displayed.
For example : If the names in the list N are ['ANKITA', 'NITISH', 'ANWAR', 'DIMPLE',
'HARKIRAT']
Then the stack OnlyA should store ['ANKITA', 'ANWAR', 'HARKIRAT'] And the output
should be displayed as HARKIRAT ANWAR ANKITA EMPTY
SOLUTION:
def PUSH(N, OnlyA):
for name in N:
if 'A' in name:
[Link](name)
def POPA(OnlyA):
while OnlyA!=[]: #while stack is not empty, keep deleting
x=[Link]()
print(x,end=" ")
print("EMPTY")
OnlyA=[]
N=['ANKITA', 'NITISH', 'ANWAR', 'DIMPLE', 'HARKIRAT']
PUSH(N, OnlyA)
POPA(OnlyA)
Q2. Write a function in Python, Push (Vehicle) where, Vehicle is a dictionary containing
details of vehicles {Car_Name: Maker}.
The function should push the name of car manufactured by "TATA' (including all the
possible cases like Tata, TaTa, etc.) to the stack. For example:
If the dictionary contains the following data:
Vehicle={"Santro": "Hyundai", "Nexon": "TATA", "Safari": "Tata"} The stack should
contain
Safari
Nexon
SOLUTION:
def Push(stack, Vehicle):
for i in Vehicle: # here i is dict key
if Vehicle[i].lower()=="tata":
[Link](i)
Vehicle={"Santro":"Hyundai","Nexon": "TATA", "Safari":
"Tata"}
stack=[] # initialize the stack
Push(stack, Vehicle) # function call
print(stack)
Q3 Write the following user defined functions :
i) pushEven(N) This function accepts a list of integers named N as parameters. It then
pushes only even numbers into the stack named EVEN.
ii) popEven(EVEN) This function pops each integer from the stack EVEN and displays
the popped value. When the stack is empty, the message "Stack Empty" is displayed.
For example : If the list N contains [10,5,3,8,15,4] Then the stack, EVEN should store
[10,8,4] And the output should be 4 8 10 Stack Empty
def pushEven(EVEN, N): # N is a list of integers
for i in N:
if i%2==0:
[Link](i)
def popEven(EVEN):
while EVEN!=[]:
print([Link]())
print("Stack empty")
N=[10,5,3,8,15,4]
EVEN=[]
pushEven(EVEN, N) #FUNCTION CALL
popEven(EVEN) #FUNCTION CALL
Q4.
i) Write the definition of a user defined function Push3_5 (N) which accepts a list of
integers in a parameter N and pushes all those integers which are divisible by 3 or
divisible by 5 from the list N into a list named Only3_5.
ii) Write a program in Python to input 5 integers into a list named NUM.
The program should then use the function Push 3_5() to create the stack of the list
only3_5. Thereafter pop each integer from the list Only3_5 and display the popped
value. When the list is empty, display the message "StackEmpty".
For example:
If the integers input into the list NUM are:
[10, 6, 14, 18, 30]
Then the stack Only3_5 should store
[10, 6, 18, 30]
And the output should be displayed as
30 18 6 10 StackEmpty
Solution:
i)
def Push3_5(N, Only3_5): #Only3_5 is a stack, N is list of
int
for i in N:
if i%3 == 0 or i%5 == 0:
Only3_5.append(i)
ii)
Num=[]
for i in range(5):
x=int(input("Enter a number: "))
[Link](x)
only3_5=[]
Push3_5(Num, only3_5) # function call
#NEXT, POP ELEMENTS
while only3_5!=[]:
x=only3_5.pop()
print(x)
print("Stack Empty")
Q5. A list contains following record of a customer:
[Customer_name, Phone_number, City]
Write the following user defined functions to perform given operations on the stack
named ‘status’:
(i) Push_element() - To Push an object containing name and Phone number of
customers who live in Goa to the stack
(ii) Pop_element() - To Pop the objects from the stack and display them. Also, display
“Stack Empty” when there are no
elements in the stack.
For example:
If the lists of customer details are:
[“Gurdas”, “99999999999”,”Goa”]
[“Julee”, “8888888888”,”Mumbai”]
[“Murugan”,”77777777777”,”Cochin”]
[“Ashmit”, “1010101010”,”Goa”]
The stack should contain
[“Ashmit”,”1010101010”]
[“Gurdas”,”9999999999”]
The output should be:
[“Ashmit”,”1010101010”]
[“Gurdas”,”9999999999”]
Stack Empty
Solution:
def Push_element(List, status): # List such as [“Gurdas”,
“99999999999”,”Goa”]
if List[2].lower()=="goa":
newlist=[List[0], List[1]]
[Link](newlist)
def Pop_element(status):
while status!=[]:
print([Link]())
print("Stack Empty")
status=[]
Push_element(["Gurdas", "99999999999","Goa"], status)
Push_element(["Julee", "8888888888","Mumbai"],status)
Push_element(["Murugan","77777777777","Cochin"],status)
Push_element(["Ashmit", "1010101010","Goa"], status)
Pop_element(status)
Q6. 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.
For 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
SOLUTION:
def PushBig(Nums, BigNums): #BigNums is stack, Nums is a list
of int
for i in Nums:
if len(str(i))>=5:
[Link](i)
def PopBig(BigNums):
while BigNums!=[]:
x=[Link]()
print(x)
print("Stack Empty")
BigNums=[] # initialise the stack
Nums = [213,10025,167,254923, 14, 1297653, 31498,386,92765]
PushBig(Nums, BigNums)
PopBig(BigNums)
Q7. 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 5 characters.
(ii) pop_city(): This function pops the cities and displays "Stack empty" when there are
no more cities in the stack.
def push_city(d_city,CITY):#d_city is a dict of state:city
for i in d_city: # i is key, the state
if len(i)>5:
[Link](d_city[i]) # d_city[i] is city
def pop_city(CITY):
while CITY!=[]:
x=[Link]()
print(x)
print("Stack empty")
d_city={"Madhya Pradesh": "Bhopal", "Bihar": "Patna",
"Gujrat": "Gandhinagar"}
CITY=[]
push_city(d_city, CITY)
pop_city(CITY)