Data Structure and Algorithm (BTech-3rd Sem)
Unit-1
1. Ticket Booking System Using Queue (Python)
global f
f=0
def t_movie(): #this t_movie function is used to select movie name
global f
f = f+1
print("which movie do you want to watch?")
print("1,movie 1 ")
print("2,movie 2 ")
print("3,movie 3")
print("4,back")
movie = int(input("choose your movie: "))
if movie == 4:
center()
theater()
return 0
if f == 1:
theater()
# this theater function used to select screen
def theater():
print("which screen do you want to watch movie: ")
print("1,SCREEN 1")
print("2,SCREEN 2")
print("3,SCREEN 3")
a = int(input("choose your screen: "))
ticket = int(input("number of ticket do you want?: "))
timing(a)
# this timing function used to select timing for movie
def timing(a):
time1 = {
"1": "10.00-1.00",
"2": "1.10-4.10",
"3": "4.20-7.20",
"4": "7.30-10.30"
}
time2 = {
"1": "10.15-1.15",
"2": "1.25-4.25",
"3": "4.35-7.35",
"4": "7.45-10.45"
}
time3 = {
"1": "10.30-1.30",
"2": "1.40-4.40",
"3": "4.50-7.50",
"4": "8.00-10.45"
}
if a == 1:
print("choose your time:")
print(time1)
t = input("select your time:")
x = time1[t]
print("successful!, enjoy movie at "+x)
elif a == 2:
print("choose your time:")
print(time2)
t = input("select your time:")
x = time2[t]
print("successful!, enjoy movie at "+x)
elif a == 3:
print("choose your time:")
print(time3)
t = input("select your time:")
x = time3[t]
print("successful!, enjoy movie at "+x)
return 0
def movie(theater):
if theater == 1:
t_movie()
elif theater == 2:
t_movie()
elif theater == 3:
t_movie()
elif theater == 4:
city()
else:
print("wrong choice")
def center():
print("which theater do you wish to see movie? ")
print("1,Inox")
print("2,Icon")
print("3,pvp")
print("4,back")
a = int(input("choose your option: "))
movie(a)
return 0
# this function is used to select city
def city():
print("Hi welcome to movie ticket booking: ")
print("where you want to watch movie?:")
print("1,city 1")
print("2,city 2 ")
print("3,city 3 ")
place = int(input("choose your option: "))
if place == 1:
center()
elif place == 2:
center()
elif place == 3:
center()
else:
print("wrong choice")
city() # it calls the function city
Implement Stack using Queues
1. Using 2 Queses(Push in O(n) and Pop() in O(1))
from collections import deque
class myStack:
def __init__(self):
self.q1 = deque()
self.q2 = deque()
def push(self, x):
# Push x first in empty q2
[Link](x)
# Push all the remaining
# elements in q1 to q2.
while len(self.q1) != 0:
[Link](self.q1[0])
[Link]()
# swap the names of two queues
self.q1, self.q2 = self.q2, self.q1
def pop(self):
# if no elements are there in q1
if len(self.q1) == 0:
return
[Link]()
def top(self):
if len(self.q1) == 0:
return -1
return self.q1[0]
def size(self):
return len(self.q1)
if __name__ == '__main__':
st = myStack()
[Link](1)
[Link](2)
[Link](3)
print([Link]())
[Link]()
print([Link]())
[Link]()
print([Link]())
print([Link]())
Output:
3
2
1
1
2. Using 2 Queses(Push in O(1) and Pop() in O(n))
from collections import deque
class myStack:
def __init__(self):
self.q1 = deque()
self.q2 = deque()
# insert element
def push(self, x):
[Link](x)
# remove top element
def pop(self):
if not self.q1:
return
while len(self.q1) != 1:
[Link]([Link]())
[Link]()
self.q1, self.q2 = self.q2, self.q1
# return top element
def top(self):
if not self.q1:
return -1
while len(self.q1) != 1:
[Link]([Link]())
temp = [Link]()
[Link](temp)
self.q1, self.q2 = self.q2, self.q1
return temp
# return current size
def size(self):
return len(self.q1)
if __name__ == '__main__':
st = myStack()
[Link](1)
[Link](2)
[Link](3)
print([Link]())
[Link]()
print([Link]())
[Link]()
print([Link]())
print([Link]())
Output:
3
2
1
1
3. Using Single Queue - Push in O(n) and Pop() in
O(1)
from collections import deque
class myStack:
def __init__(self):
self.q = deque()
# push element on top
def push(self, x):
[Link](x)
sz = len(self.q)
for i in range(sz - 1):
[Link](self.q[0])
[Link]()
# remove top element
def pop(self):
if self.q:
[Link]()
# return top element
def top(self):
if not self.q:
return -1
return self.q[0]
# return current size
def size(self):
return len(self.q)
if __name__ == '__main__':
st = myStack()
[Link](1)
[Link](2)
[Link](3)
print([Link]())
[Link]()
print([Link]())
[Link]()
print([Link]())
print([Link]())
Output:
3
2
1
1