DATA STRUCTURES
It represents how data is stored/organized in Computer’s Memory.
A data structure defines a mechanism to store, organize and access data along
with operations (processing) can be efficiently performed on the data.
Simple data structures : Built from primitive data types(integers, real, character,
Boolean) Example : Arrays
Compound data Structures: Simple data structures are used to form more complex
data structure. They are classified into two types :-
Linear: means elements are stored in sequential order Example : Stack, queue,
linked list
Non – Linear : Data can be stored as 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.
Operations on Stack:-
PUSH
POP
PEEK
Overflow and Underflow case:
Overflow: It refers to a situation , when one tries to push an element in stack/
Queue, that is full. In python , (stack is implemented as list). Since list can grow,
OVERFLOW condition does not arise until all memory is exhausted.
Underflow :- It refers to a situation when one tries to pop or delete an item
from an empty stack or queue.
Implementation of stack using list
Q1. 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) peep(BookStack) : This function displays the topmost element of the stack
without deleting it. If the stack is empty, the function display ‘None’.
Q2. 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 returns it.
If the stack is already empty, the function should display “Empty”.
Write function Disp_even() to display all element 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]
Q3. 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.
Q4. 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
Q5. 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 name
of the city and country, which are not in India and 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 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”, 3405]
The output should be:
[“Columbo”, “Sri Lanka”]
[“Dubai”, “UAE”]
[“Naypyidaw”, “Myanmar”]
Stack Empty
Q6. Assertion(A): In Python, a stack can be implemented using a list.
Reasoning(R): A stack is an ordered linear list of elements that works on the
principle of First In First Out(FIFO).
(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.
Q7. 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 :
[“MCA”, 200000, 3]
[“MBA”, 500000, 2]
[“BA”, 100000, 3]
The stack should contain
[“MBA”, 500000, 2]
[“MCA”, 200000, 3]
Underflow
Q8. A list contains following record of customer:
[Customer_name, Room Type]
Write the following user defined functions to perform given operations on the stack
named “Hotel” :
(i) Push_Cust() – To Push customers names of those customers who are staying
in “Delux” Room Type.
(ii) Pop_Cust() – To Pop the names of customers from the stack and display
them. Also, display “Underflow” when there are no customers in the stack.
For example :
If the lists with customer details are as follows :
[“Siddharth”, “Delux”],
[“Rahul”, “Standard”],
[“Jerry”, “Delux”]
The stack should contain
[“Siddharth”, “Jerry”]
The output should be:
Jerry
Siddharth
Underflow
Q9. 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
Q10. Differentiate between Push and Pop operations in the context of stacks.
Ans:-
PUSH is the operation of insertion of an element in a stack at its topmost
location.
POP is the operation of deletion of the topmost element of the stack.
Q11. 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
Q12. “Stack is a linear data structure which follows a particular order in which the
operations are performed.” What is the order in which the operations are performed
in a stack? Name the List method/function available in Python which is used to
remove the last element from a list implemented stack. Also write an example using
Python statements for removing the last element of the list.
Ans:-
Order of operations performed in a stack is LIFO(Last In First Out)
The List method in Python to remove the last element from an implemented
stack is pop()
Example: L=[10,20,30,40]
[Link]() OR [Link](-1)
Q13. 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 All.
The program should then 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 All.
Thereafter, pop each word from the list NoVowel and display the popped word. When the stack
is empty, display the message “EmptyStack”.
For example:
If the Words accepted and pushed into the list All are
[‘Dry’, ‘LIKE’, ‘RHYTHM’, ‘WORK’, ‘GYM’]
Then the stack NoVowel should store
[‘DRY’, ‘RHYTHM’, ‘GYM’]
And the output should be displayed as
GYM RHYTHM DRY EmptyStack
Q14. 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 NUM. The program should then use
the function Push3_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
Q15. Write the definition of a function POP_PUSH(LPop, LPush, N ) in Python. The
function should Pop out the last N elements of the list LPop and Push them into the
list LPush.
For example: If the contents of the list LPop are [10,15,20,30] and value of N passed
is 2, then the function should create the list LPush as [30,20] and the list LPop should
now contain [10,15]
NOTE: If the value of N is more than the number of elements present in LPop, then
display the message “Pop not possible”.
Q16. Write a function in Python POPSTACK(L) where L is a stack implemented by a
list of numbers. The function returns the value deleted from the stack.
Ans:-
def POPSTACK(L):
if len(L)>0:
return [Link]()
else:
return None
OR
def POPSTACK(L):
return [Link]()
Q17. 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
the stack
(iii) 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”,”999999999999”,”Goa”]
[“Julee”, “888888888888”,”Mumbai”]
[“Murgan”,”777777777777”,”Cochin”]
[“Ashmit”,”101010101010”,”Goa”]
The stack should contain
[“Ashmit”,”101010101010”]
[“Gurdas”,”999999999999”]
The output should be:
[“Ashmit”,”101010101010”]
[“Gurdas”, “999999999999”]
The output should be:
[“Ashmit”,”101010101010”]
[“Gurdas”,”999999999999”]
Stack Empty
Q18. 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 in the stack who have price
greater than 75.
Also display the count of elements pushed into the stack.
For example: If the dictionary contains the following data:
Ditem={“Pen”,106, “Pencil”:59, “Notebook”:80, “Eraser”:25}
The stack should contain Notebook Pen
The count of elements in the stack is 2
Q19. Give any two characteristics of stacks.
Ans:-
Characteristics of Stacks:
(A) It is a LIFO data structure
(B) The insertion and deletion happens at one end i.e. from the top of the
stack
Q20. Julie has created a dictionary containing names and marks as key value pairs of
6 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 75.
Pop and display the content of the stack.
For example: If the sample content of the dictionary is as follows:
R={“OM”:76, “JAI”:45, “BOB”:89, “ALI”:65, “ANU”:90, “TOM”:82}
The output from the program should be:
TOM ANU BOB OM
Q21. Alam has a list containing 10 integers. You need to help him create a program
with separate user defined functions to perform the following operations based on
this list.
Traverse the content of the list and push the even numbers into a stack.
For example: If the sample Content of the list is as follows:
N=[12,13,34,56,21,79,98,22,35,38]
Sample Output of the code should be:
38 22 98 56 34 12
Q22. Write a function in Python PUSH(Arr), where Arr is a list of numbers. From this
list push all numbers divisible by 5 into a stack implemented by using a list. Display
the stack if it has at least one element, otherwise display appropriate error message.
Ans:-