forked from HarshCasper/NeoAlgo
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Double_Ended_queue.py
163 lines (141 loc) · 3.4 KB
/
Double_Ended_queue.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
'''
DOUBLE ENDED QUEUE
Double ended queue or dequeue is a special type of queue
wherein elements can be inserted or deleted from both ends
i.e front and rear
'''
# to insert an element to the front of double ended queue
def enqueue_front(n):
global rear
global front
global dequeue
# If dequeue is not full
if ((rear + 1) % 10 != front):
# If dequeue is empty insert as first element
if front == -1:
front = 0
rear = 0
# decrement front in circular manner and insert
else:
front = (front + 9) % 10
dequeue[front] = n
# to insert an element to the rear of double ended queue
def enqueue_rear(n):
global rear
global front
global dequeue
if ((rear + 1) % 10 != front):
if (rear == -1):
front = 0
rear = 0
# increment rear in circular manner and insert
else:
rear = (rear + 1) % 10
dequeue[rear] = n
# to delete an element and return it from the front of dequeue
def delete_front():
global rear
global front
global dequeue
item = -1
# If dequeue is empty
if (front == -1):
return -1
else:
item = dequeue[front]
# if there is only one element
if (front == rear):
front = -1
rear = -1
else:
front = (front + 1) % 10
return item
# to delete an element and return it from the rear of dequeue
def delete_rear():
global rear
global front
global dequeue
item = -1
if (rear == -1):
return -1
else:
item = dequeue[rear]
if (front == rear):
front = -1
rear = -1
else:
rear = (rear + 9) % 10
return item
# to display the double ended queue from front to rear
def display():
global rear
global front
global dequeue
if (front <= rear):
for i in range(front, rear+1):
print(dequeue[i], end=" ")
else:
for i in range(front, 10):
print(dequeue[i], end=" ")
for i in range(0, rear+1):
print(dequeue[i], end=" ")
print("\n")
# driver code
def main():
global dequeue
global rear
global front
rear = -1
front = -1
dequeue = [None]*10
# menu driven program to insert,delete or display dequeue
print("1.Enqueue front\n2.Enqueue rear\n3.Delete front\n4.Delete rear")
print("5.Display\n6.Exit\nChoose an option")
opt = int(input())
while opt != 6:
if opt == 1:
n = int(input("Enter the value to be inserted: "))
enqueue_front(n)
if opt == 2:
n = int(input("Enter the value to be inserted: "))
enqueue_rear(n)
if opt == 3:
print(str(delete_front())+" is deleted")
if opt == 4:
print(str(delete_rear())+" is deleted")
if opt == 5:
display()
print("Choose an option")
opt = int(input())
main()
'''
SAMPLE I/O:
1.Enqueue front
2.Enqueue rear
3.Delete front
4.Delete rear
5.Display
6.Exit
Choose an option
1
Enter the value to be inserted: 1
Choose an option
2
Enter the value to be inserted: 2
Choose an option
1
Enter the value to be inserted: 3
Choose an option
2
Enter the value to be inserted: 4
Choose an option
3
3 is deleted
Choose an option
5
1 2 4
Choose an option
6
Time Complexity: O(1)
Space complexity: O(1)
'''