Le operazioni minime per una coda doppia (double ended queue)
Si può scegliere se aggiungere/togliere in prima/ultima posizione
- add_front(x), aggiunge x al primo posto della coda
- add_rear(x), aggiunge x all’ultimo posto della coda
- x <– remove_front(), restituisce l’elemento al primo posto e lo elimina
- x <– remove_rear(), restituisce l’elemento all’ultimo posto e lo elimina
- is_empty(), la coda è vuota?
Classe
class D_E_Queue: # Double Ended Queue
def __init__(self):
self._lista=[]
def add_front(self, x):
self._lista.append(x)
def add_rear(self, x):
self._lista.insert(0, x)
def remove_front(self):
return self._lista.pop()
def remove_rear(self):
return self._lista.pop(0)
def is_empty(self):
return (len(self._lista) == 0)
Test 1
class D_E_Queue:
...
coda_doppia=D_E_Queue() # []
coda_doppia.add_rear(18) # [18]
coda_doppia.add_rear(1) # [1, 18]
coda_doppia.add_front(28) # [1, 18, 28]
print(coda_doppia.empty()) # False
print(coda_doppia.remove_front()) # [1, 18] 28
print(coda_doppia.empty()) # False
print(coda_doppia.remove_rear()) # [18] 1
print(coda_doppia.empty()) # False
print(coda_doppia.remove_front()) # [] 18
print(coda_doppia.empty()) # True
Test 2
Utilizza la coda doppia come stack
class D_E_Queue:
...
coda_doppia = D_E_Qeque() # []
for x in range(5):
coda_doppia.add_front(x)
print(coda_doppia._lista) # [0, 1, 2, 3, 4]
while(not coda_doppia.is_empty()):
print(coda_doppia.remove_front()) # 4 3 2 1 0
print(coda_doppia._lista) # []
Test 3
Utilizza la coda doppia come coda
class D_E_Queue:
...
coda_doppia = D_E_Qeque() # []
for x in range(5):
coda_doppia.add_rear(x)
print(coda_doppia._lista) # [4, 3, 2, 1, 0]
while(not coda_doppia.is_empty()): # []
print(coda_doppia.remove_front()) # 0 1 2 3 4
print(coda_doppia._lista) # []
Continua…
- n <– size(), quanti elementi contiene?
- …