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
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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
|
1 2 3 4 5 6 7 8 9 |
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
|
1 2 3 4 5 6 7 8 9 |
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?
- …