DATA STRUCTURES

• Data structure is A set of rules and operations to organize and store data in an efficient manner.
It is a way to store data in a structured way.
• Operations on data structure-
o Traversal
o Insertion
o Deletion
• Types of data structures:
├── Linear Data Structures
│ ├── List (or Array)
│ ├── Stack
│ ├── Queue
│ └── Linked List
│
└── Non-Linear Data Structures
├── Tree
└── Graph
• Built-in data structures available in Python: List, Tuple, Dictionary and Set.
61 | P a g e
 • User Defined data structures in Python: Stack, Queue, Tree, Linked List etc.
STACK:
• A Stack is a Linear data structure which works in LIFO (Last In First Out) manner (or we can say
FILO i.e. First In Last Out manner
• Insertion and Deletion of elements will be done only from one end known as TOP.
• In Python, we can use List data structure to implement Stack.
Application of Stack:
1. Expression Evaluation
2. String Reversal
3. Function Call
4. Browser History
5. Undo/Redo Operations
Operations on Stack:
The Stack supports following operations:
1. Push: It adds an element to the TOP of the Stack.
2. Pop: It removes an element from the TOP of the Stack.
3. Peek: It is used to know/display the value of TOP without removing it.
4. isEmpty: It is used to check whether Stack is empty.
OVERFLOW: It refers to the condition in which we try to PUSH an item in a Stack which is already FULL.

UNDERFLOW: It refers to the condition in which we are trying to POP an item from an empty Stack.

Stack Implementation in Python (Using List)

stack = []
# Function to push element into the stack
def push( ):
element = input("Enter element to push: ")
[Link](element)
print("Element pushed to stack.")
# Function to pop element from the stack

62 | P a g e
def pop_element( ):
if not stack:
print("Stack is empty!")
else:
element = [Link]( )
print("Element popped from stack.")
# Function to display stack
def display( ):
if not stack:
print("Stack is empty!")
else:
print("Stack elements (top to bottom):")
for item in reversed(stack):
print(item)

# Menu-driven program
while True:
print("\nSTACK OPERATIONS")
print("1. Push")
print("2. Pop")
print("3. Display")
print("4. Exit")
choice = int(input("Enter your choice (1-4): "))
if choice == 1:
push( )
elif choice == 2:
pop_element( )
elif choice == 3:
display( )
elif choice == 4:
print("Exiting program...")
break
else:
print("Invalid choice! Please try again.")
Multiple Choice Questions
1. What is the principle of a stack?
a) FIFO – First In First Out b) LIFO – Last In First Out
c) FILO – First In Last Out d) LILO – Last In Last Out
2. Which Python list method is used to add an element to the stack?
a) insert( ) b) add( ) c) append( ) d) push ( )
3. Which method is used to remove the top element from a stack implemented using a list?
a) remove( ) b) delete( ) c) pop( ) d) discard ( )
4. What will be the output of the following code?
stack = [10, 20, 30]
[Link]( )
print(stack)
63 | P a g e
 a) [10, 20, 30] b) [10, 20]
c) [20, 30] d ) Error
5. What happens if you call pop ( ) on an empty stack?
a) Returns None b) Raises IndexError
c) Returns -1 d) Does nothing
Answers
1. B 2. C 3. C 4. B 5. B

ASSERTION REASONING QUESTIONS.

Mark the correct choice as
(a) Both (A) and (R) are true and (R) is the correct explanation for (A).
(b) Both (A) and (R) are true and (R) is not the correct explanation for (A).
(c) (A) is true but (R) is false.
(d) (A) is false but(R) is true.
1. Assertion (A): In Python, a stack can be implemented using a list.
Reason (R): A stack is an ordered linear list of elements that works on the principle of First
In First Out (FIFO).
2. Assertion (A): A stack can be used to reverse the contents of a text file line by line.
Reason (R): In a stack, the last element inserted is the first to be removed (LIFO).
3. Assertion (A): Using a stack is an efficient method for checking matching brackets in a file
containing Python code.
Reason (R): Stack allows multiple ends for insertion and deletion of elements.
4. Assertion (A): A stack can be implemented using a list in Python to read a file and store each
word for later processing.
Reason (R): Lists in Python do not support push and pop operations.
Answers
1 C 2 A 3 C 4 C
Long Answer Questions
1. 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.
Ans CITY=[ ]
1(i) def push_city(d_city):
for c in d_city:
if len(c) > 4:
[Link](d_city[c])
1(ii) def pop_city( ):
while CITY:

64 | P a g e
 print([Link]( ))
else:
print("Stack empty")
2. 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
Ans def PushBig(Nums,BigNums):
for N in Nums:
if len(str(N)) >= 5:
[Link](N)
def PopBig(BigNums):
while BigNums:
print([Link]( ))
else:
print("Stack Empty")
3. A list contains following record of course details for a University:
[Course_name, Fees, Duration]
Write the following user defined functions to perform given operations on the stack
named 'Univ' :
(i) Push_element( ) - To push an object containing the Course_name, Fees and Duration
of a course, which has fees greater than 100000 to the stack.
(ii) Pop_element( ) - To pop the object from the stack and display it. Also, display
“Underflow” when there is no element in the stack.
For example:
If the lists of courses details are:

65 | P a g e
 ["MCA", 200000, 3]
["MBA", 500000, 2]
["BA", 100000, 3]
The stack should contain
["MBA", 500000, 2]
["MCA", 200000, 3]
Ans Univ=[]
def Push_element(Course):
for Rec in Course:
if Rec[1]>100000:
[Link](Rec)
def Pop_element( ):
while len(Univ)>0:
print([Link]( ))
else:
print("Underflow")
4. Write separate user defined functions for the following:
(i) PUSH(N) - This function accepts a list of names, N as parameter. 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
Ans OnlyA=[ ]
def PUSH(N):
for aName in N :
if 'A' in aName :
[Link](aName)
def POPA(OnlyA):
while OnlyA :
print([Link]( ), end=' ')
else :
print('EMPTY')
5. Write the following user defined functions:
(i) pushEven(N) - This function accepts a list of integers named N as parameter. It then
pushes only even numbers into the stack named EVEN.

66 | P a g e
 (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
Ans EVEN=[ ]
def pushEven(N):
for z in N :
if z%2==0 :
[Link](z)
def popEven(EVEN):
while EVEN :
print([Link]( ), end=' ')
else :
print('Stack Empty')
6. Write the definition of a user defined function PushNV(N) which accepts a list of strings in
the parameter N and pushes all strings which have no vowels present in it, into a list named
NoVowel.
Write a program in Python to input 5 Words and push them one by one into a list named
[Link] program should that use the function PushNV( ) to create a stack of words in the
list NoVowel so that it stores only those words which do not have any vowel present in it,
from the list [Link], pop each word from the list NoVowel and display the popped
word. When the stack is empty, display the message "EmptyStack".
Ans def PushNV(N):
for W in N :
for C in W :
if [Link]( ) in 'AEIOU':
break
else:
[Link](W)
All=[ ]
NoVowel=[ ]
for i in range(5) :
[Link](input('Enter a Word: '))
PushNV(All)
while NoVowel :
print([Link]( ), end=' ')
else :
print('EmptyStack')

67 | P a g e