Deque (Doubly Ended Queue) Python tiek ieviesta, izmantojot moduli kolekcijas . Deque tiek dota priekšroka nevis sarakstam gadījumos, kad nepieciešamas ātrākas pievienošanas un popoperācijas no abiem konteinera galiem, jo deque nodrošina O(1) laika sarežģītība pievienošanas un pop operācijām, salīdzinot ar sarakstu, kas nodrošina O(n) laika sarežģītību.
Ierobežotās deque ievades veidi
- Input Restricted Deque: ievade ir ierobežota vienā galā, bet dzēšana ir atļauta abos galos. Output Restricted Deque: izvade ir ierobežota vienā galā, bet ievietošana ir atļauta abos galos.
Piemērs: Python kods demonstrēšanai
Python3
from> collections>import> deque> > # Declaring deque> queue>=> deque([>'name'>,>'age'>,>'DOB'>])> > print>(queue)> |
>
>Izvade
deque(['name', 'age', 'DOB'])>
Operācijas uz deque
1. piemērs: vienumu efektīva pievienošana
- append() :- Šī funkcija tiek izmantota, lai argumentā ievietotu vērtību deque labajā galā. appendleft() :- Šī funkcija tiek izmantota, lai argumentā ievietotu vērtību deque kreisajā galā.
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)> |
>
>Izvade
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])>
Sarežģītības analīzei skatiet galu.
2. piemērs: vienumu efektīva izgrūšana
- pop() :- Šī funkcija tiek izmantota, lai izdzēstu argumentu no deque labās puses. popleft() :- Šī funkcija tiek izmantota, lai izdzēstu argumentu no deque kreisā gala.
Python3
kā java ģenerēt nejaušus numurus
# 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)> |
>
>Izvade
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])>
Sarežģītības analīzei skatiet galu.
3. piemērs. Piekļuve vienumiem dekā
- index(ele, beg, end) :- Šī funkcija atgriež pirmo argumentos minētās vērtības indeksu, sākot meklēšanu no sākuma līdz beigu indeksam. insert(i, a) :- Šī funkcija ievieto argumentos(a) minēto vērtību argumentos norādītajā indeksā(i). remove() :- Šī funkcija noņem pirmo argumentos minētās vērtības gadījumu. count() :- Šī funkcija saskaita argumentos minēto vērtību gadījumu skaitu.
Python3
# 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)> |
>
>Izvade
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])>
Sarežģītības analīzei skatiet galu.
4. piemērs. Dekas lielums
- len(dequeue) :- atgriež pašreizējo atkāpšanās lielumu.
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> |
>
>Izvade
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>
Sarežģītības analīzei skatiet galu.
5. piemērs. Dekas priekšpuse un aizmugure
- Deque[0]: mēs varam piekļūt deque priekšējam elementam, izmantojot indeksēšanu ar de[0]. Deque[-1] :- Mēs varam piekļūt deque aizmugurējam elementam, izmantojot indeksēšanu ar 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> |
>
>Izvade
Current Deque: deque([1, 2, 3, 4, 5, 6]) Front element of the deque: 1 Back element of the deque: 6>
Sarežģītības analīzei skatiet galu.
6. piemērs: dažādas darbības ar deque
- paplašināt (iterējams): - šo funkciju izmanto, lai deque labajā galā pievienotu vairākas vērtības. Pieņemtais arguments ir atkārtojams. extendleft (iterable) :- šo funkciju izmanto, lai pievienotu vairākas vērtības deque kreisajā galā. Pieņemtais arguments ir atkārtojams. Kreiso pielikumu rezultātā secība tiek apgriezta. reverse() :- Šī funkcija tiek izmantota, lai mainītu deque elementu secību. rotate() :- Šī funkcija pagriež deque par argumentos norādīto skaitli. Ja norādītais skaitlis ir negatīvs, notiek pagriešana pa kreisi. Citādi rotācija ir pa labi.
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)> |
>
>Izvade
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])>
Sarežģītības analīzei skatiet galu.
Sarežģītības analīze:
| Metodes | Laika sarežģītība | Palīgtelpa |
|---|---|---|
| pievienot () | O(1) | O(1) |
| appendleft() | O(1) | O(1) |
| pop () | O(1) | O(1) |
| popleft() | O(1) | O(1) |
| indekss (ele, beg, end) | O(N) | O(1) |
| ievietot (i, a) | O(N) | O(1) |
| noņemt () | O(N) | O(1) |
| skaitīt () | O(N) | O(1) |
| tikai (nolikt rindā) | O(1) | O(1) |
| Deque[0] | O(1) | O(1) |
| Deque[-1] | O(1) | O(1) |
| paplašināt (atkārtojams) | bultiņa) | O(1) |
| pagarināts pa kreisi (atkārtojams) | bultiņa) | O(1) |
| reverse() | O(N) | O(1) grep komanda Linux |
| pagriezt () | bultiņa) | O(1) |