Deque (cola de doble terminación) en Python se implementa mediante el módulo colecciones . Se prefiere deque a una lista en los casos en los que necesitamos operaciones de agregar y extraer más rápidas desde ambos extremos del contenedor, ya que deque proporciona una O(1) complejidad de tiempo para operaciones de agregar y extraer en comparación con una lista que proporciona complejidad de tiempo O(n).
Tipos de entrada deque restringida
- Deque restringido de entrada: la entrada está limitada en un extremo, mientras que se permite la eliminación en ambos extremos. Salida restringida Deque: la salida está limitada en un extremo pero se permite la inserción en ambos extremos.
Ejemplo: código Python para demostrar
Python3
from> collections>import> deque> > # Declaring deque> queue>=> deque([>'name'>,>'age'>,>'DOB'>])> > print>(queue)> |
>
>Producción
deque(['name', 'age', 'DOB'])>
Operaciones en deque
Ejemplo 1: Agregar elementos de manera eficiente
- append(): – Esta función se utiliza para insertar el valor en su argumento en el extremo derecho de la deque. appendleft(): – Esta función se utiliza para insertar el valor en su argumento en el extremo izquierdo de la deque.
Python3
# 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)> |
>
>Producción
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])>
Consulte el final para el análisis de complejidad.
Ejemplo 2: hacer estallar artículos de manera eficiente
- pop(): – Esta función se utiliza para eliminar un argumento del extremo derecho de la deque. popleft(): – Esta función se utiliza para eliminar un argumento del extremo izquierdo de la deque.
Python3
# 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)> |
>
>Producción
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])>
Consulte el final para el análisis de complejidad.
Ejemplo 3: acceder a elementos en una cola
- index(ele, beg, end): – Esta función devuelve el primer índice del valor mencionado en los argumentos, comenzando la búsqueda desde el inicio hasta el final del índice. insertar (i, a): – Esta función inserta el valor mencionado en los argumentos (a) en el índice (i) especificado en los argumentos. remove(): – Esta función elimina la primera aparición del valor mencionado en los argumentos. count(): - Esta función cuenta el número de apariciones del valor mencionado en los argumentos.
Python3
patrón de diseño del constructor
# 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)> |
>
>Producción
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])>
Consulte el final para el análisis de complejidad.
Ejemplo 4: Tamaño de una deque
- len(quitar de cola): - Devuelve el tamaño actual de la cola.
Python3
# 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> |
>
>Producción
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>
Consulte el final para el análisis de complejidad.
Ejemplo 5: Anverso y reverso de un deque
- Deque[0]: - Podemos acceder al elemento frontal del deque usando la indexación con de[0]. Deque[-1]: – Podemos acceder al elemento posterior del deque usando la indexación con de[-1].
Python3
# 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> |
>
>Producción
Current Deque: deque([1, 2, 3, 4, 5, 6]) Front element of the deque: 1 Back element of the deque: 6>
Consulte el final para el análisis de complejidad.
Ejemplo 6: diferentes operaciones en deque
- extender (iterable): – Esta función se utiliza para agregar múltiples valores en el extremo derecho de la deque. El argumento pasado es iterable. extendleft(iterable): – Esta función se utiliza para agregar múltiples valores en el extremo izquierdo de la deque. El argumento pasado es iterable. El orden se invierte como resultado de los anexos izquierdos. inversa(): – Esta función se utiliza para invertir el orden de los elementos deque. rotar (): - Esta función rota la deque por el número especificado en los argumentos. Si el número especificado es negativo, la rotación se produce hacia la izquierda. De lo contrario, la rotación es hacia la derecha.
Python3
# 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)> |
>
>Producción
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])>
Consulte el final para el análisis de complejidad.
Análisis de complejidad:
| Métodos | Complejidad del tiempo | Espacio Auxiliar |
|---|---|---|
| adjuntar() | O(1) | O(1) |
| anexar a la izquierda() | O(1) | O(1) |
| estallido() | O(1) | O(1) |
| popizquierda() | O(1) | O(1) |
| índice(ele, inicio, fin) | EN) | O(1) |
| insertar(yo, a) | EN) | O(1) |
| eliminar() | EN) | O(1) |
| contar() | EN) | O(1) |
| solo (quitar de la cola) | O(1) | O(1) |
| Deque[0] | O(1) | O(1) |
| Deque[-1] | O(1) | O(1) |
| extender (iterable) | FLECHA) | O(1) |
| extender a la izquierda (iterable) | FLECHA) | O(1) |
| contrarrestar() | EN) | O(1) alquilar mapa |
| girar() | FLECHA) | O(1) |