logo

I en Python

Deque (Cua de doble finalització) a Python s'implementa mitjançant el mòdul col·leccions . Deque es prefereix a una llista en els casos en què necessitem operacions d'afegir i pop més ràpides des dels dos extrems del contenidor, ja que deque proporciona un O(1) complexitat de temps per a les operacions d'afegir i pop en comparació amb una llista que proporciona complexitat de temps O(n).

Tipus d'entrada de Deque restringida

    Entrada restringida Deque: l'entrada està limitada en un extrem mentre que la supressió està permesa als dos extrems. Sortida Restringida Deque: la sortida està limitada a un extrem, però es permet la inserció als dos extrems.

Exemple: codi Python per demostrar

Python 3








from> collections>import> deque> > # Declaring deque> queue>=> deque([>'name'>,>'age'>,>'DOB'>])> > print>(queue)>



>

>

Sortida

deque(['name', 'age', 'DOB'])>

Operacions sobre deque

Exemple 1: afegir elements de manera eficient

    append() :- Aquesta funció s'utilitza per inserir el valor del seu argument a l'extrem dret del deque. appendleft() :- Aquesta funció s'utilitza per inserir el valor del seu argument a l'extrem esquerre del deque.

Python 3




# importing 'collections' for deque operations> import> collections> # initializing deque> de>=> collections.deque([>1>,>2>,>3>])> print>(>'deque: '>, de)> # using append() to insert element at right end> # inserts 4 at the end of deque> de.append(>4>)> # printing modified deque> print>(>' The deque after appending at right is : '>)> print>(de)> # using appendleft() to insert element at left end> # inserts 6 at the beginning of deque> de.appendleft(>6>)> # printing modified deque> print>(>' The deque after appending at left is : '>)> print>(de)>

>

>

Sortida

deque: deque([1, 2, 3]) The deque after appending at right is : deque([1, 2, 3, 4]) The deque after appending at left is : deque([6, 1, 2, 3, 4])>

Consulteu el final per a l'anàlisi de complexitat.

Exemple 2: esclatar elements de manera eficient

    pop() :- Aquesta funció s'utilitza per eliminar un argument de l'extrem dret del deque. popleft() :- Aquesta funció s'utilitza per eliminar un argument de l'extrem esquerre del deque.

Python 3




# importing 'collections' for deque operations> import> collections> # initializing deque> de>=> collections.deque([>6>,>1>,>2>,>3>,>4>])> print>(>'deque: '>, de)> # using pop() to delete element from right end> # deletes 4 from the right end of deque> de.pop()> # printing modified deque> print>(>' The deque after deleting from right is : '>)> print>(de)> # using popleft() to delete element from left end> # deletes 6 from the left end of deque> de.popleft()> # printing modified deque> print>(>' The deque after deleting from left is : '>)> print>(de)>

>

>

Sortida

dfs vs bfs
deque: deque([6, 1, 2, 3, 4]) The deque after deleting from right is : deque([6, 1, 2, 3]) The deque after deleting from left is : deque([1, 2, 3])>

Consulteu el final per a l'anàlisi de complexitat.

Exemple 3: Accés a elements en un deque

    index(ele, beg, end):- Aquesta funció retorna el primer índex del valor esmentat als arguments, començant la cerca des de l'índex beg fins al final. insert(i, a):- Aquesta funció insereix el valor esmentat en arguments (a) a l'índex (i) especificat en arguments. remove() :- Aquesta funció elimina la primera ocurrència del valor esmentat als arguments. count() :- Aquesta funció compta el nombre d'ocurrències del valor esmentades als arguments.

Python 3




# Python code to demonstrate working of> # insert(), index(), remove(), count()> # importing 'collections' for deque operations> import> collections> # initializing deque> de>=> collections.deque([>1>,>2>,>3>,>3>,>4>,>2>,>4>])> # using index() to print the first occurrence of 4> print> (>'The number 4 first occurs at a position : '>)> print> (de.index(>4>,>2>,>5>))> # using insert() to insert the value 3 at 5th position> de.insert(>4>,>3>)> # printing modified deque> print> (>'The deque after inserting 3 at 5th position is : '>)> print> (de)> # using count() to count the occurrences of 3> print> (>'The count of 3 in deque is : '>)> print> (de.count(>3>))> # using remove() to remove the first occurrence of 3> de.remove(>3>)> # printing modified deque> print> (>'The deque after deleting first occurrence of 3 is : '>)> print> (de)>

>

>

Sortida

The number 4 first occurs at a position : 4 The deque after inserting 3 at 5th position is : deque([1, 2, 3, 3, 3, 4, 2, 4]) The count of 3 in deque is : 3 The deque after deleting first occurrence of 3 is : deque([1, 2, 3, 3, 4, 2, 4])>

Consulteu el final per a l'anàlisi de complexitat.

Exemple 4: Mida d'un deque

    len(decua):- Retorna la mida actual de la cua.

Python 3




# Python Program to demonstrate> # how to find size of a Dequeue> from> collections>import> deque> # initializing deque> de>=> deque([>1>,>2>,>3>,>4>,>5>,>6>])> print>(>'Current Deque: '>, de)> # printing current size of deque> print>(f>'Size of Deque: {len(de)}'>)> # using pop() to delete element from right end> # deletes 6 from the right end of deque> de.pop()> # printing modified deque> print>(>' The deque after deleting from right is: '>, end>=> '')> print>(de)> # printing current size of deque> print>(f>'Size of Deque: {len(de)}'>)> # This code is contributed by Susobhan Akhuli>

>

>

Sortida

Current Deque: deque([1, 2, 3, 4, 5, 6]) Size of Deque: 6 The deque after deleting from right is: deque([1, 2, 3, 4, 5]) Size of Deque: 5>

Consulteu el final per a l'anàlisi de complexitat.

Exemple 5: davant i darrere d'un deque

    Deque[0] :- Podem accedir a l'element frontal del deque mitjançant la indexació amb de[0]. Deque[-1] :- Podem accedir a l'element posterior del deque mitjançant la indexació amb de[-1].

Python 3




# Python Program to demonstrate> # accessing the front and back of a Deque> from> collections>import> deque> # initializing deque> de>=> deque([>1>,>2>,>3>,>4>,>5>,>6>])> print>(>'Current Deque: '>, de)> # Accessing the front element of the deque> print>(>'Front element of the deque:'>, de[>0>])> # Accessing the back element of the deque> print>(>'Back element of the deque:'>, de[>->1>])> # This code is contributed by Susobhan Akhuli>

>

>

Sortida

Current Deque: deque([1, 2, 3, 4, 5, 6]) Front element of the deque: 1 Back element of the deque: 6>

Consulteu el final per a l'anàlisi de complexitat.

Exemple 6: Diferents operacions sobre deque

    extend(iterable):- Aquesta funció s'utilitza per afegir diversos valors a l'extrem dret de la deque. L'argument passat és iterable. extendleft(iterable):- Aquesta funció s'utilitza per afegir diversos valors a l'extrem esquerre del deque. L'argument passat és iterable. L'ordre s'inverteix com a resultat dels annexos esquerre. reverse() :- Aquesta funció s'utilitza per invertir l'ordre dels elements deque. rotate() :- Aquesta funció gira el deque pel nombre especificat als arguments. Si el nombre especificat és negatiu, la rotació es produeix a l'esquerra. En cas contrari, la rotació és a la dreta.

Python 3




# Python code to demonstrate working of> # extend(), extendleft(), rotate(), reverse()> # importing 'collections' for deque operations> import> collections> # initializing deque> de>=> collections.deque([>1>,>2>,>3>,])> # using extend() to add numbers to right end> # adds 4,5,6 to right end> de.extend([>4>,>5>,>6>])> # printing modified deque> print> (>'The deque after extending deque at end is : '>)> print> (de)> # using extendleft() to add numbers to left end> # adds 7,8,9 to left end> de.extendleft([>7>,>8>,>9>])> # printing modified deque> print> (>'The deque after extending deque at beginning is : '>)> print> (de)> # using rotate() to rotate the deque> # rotates by 3 to left> de.rotate(>->3>)> # printing modified deque> print> (>'The deque after rotating deque is : '>)> print> (de)> # using reverse() to reverse the deque> de.reverse()> # printing modified deque> print> (>'The deque after reversing deque is : '>)> print> (de)>

>

>

Sortida

The deque after extending deque at end is : deque([1, 2, 3, 4, 5, 6]) The deque after extending deque at beginning is : deque([9, 8, 7, 1, 2, 3, 4, 5, 6]) The deque after rotating deque is : deque([1, 2, 3, 4, 5, 6, 9, 8, 7]) The deque after reversing deque is : deque([7, 8, 9, 6, 5, 4, 3, 2, 1])>

Consulteu el final per a l'anàlisi de complexitat.

Anàlisi de complexitat:

Mètodes

Complexitat temporal

Espai Auxiliar

afegir()

O(1)

O(1)

apèndixesquerra()

O(1)

O(1)

pop()

O(1)

O(1)

popleft()

O(1)

O(1)

índex (ele, beg, end)

O(N)

O(1)

inseriu (i, a)

O(N)

O(1)

eliminar ()

O(N)

O(1)

comptar ()

O(N)

O(1)

només (retirar la cua)

O(1)

O(1)

Deque[0]

O(1)

O(1)

Deque[-1]

O(1)

O(1)

estendre (iterable)

FLECHA)

O(1)

estendre a l'esquerra (iterable)

FLECHA)

O(1)

revés ()

O(N)

O(1)

comanda grep a linux

girar ()

FLECHA)

O(1)