Deque (dvigubai pasibaigusi eilė) Python yra įdiegta naudojant modulį kolekcijos . Deque yra teikiama pirmenybė sąrašui tais atvejais, kai reikia greitesnių pridėjimo ir iššokimo operacijų iš abiejų konteinerio galų, nes deque suteikia O(1) Pridėjimo ir iššokimo operacijų laiko sudėtingumas, palyginti su sąrašu, kuriame pateikiamas O(n) laiko sudėtingumas.
Riboto deque įvesties tipai
- Input Restricted Deque: įvestis ribojama viename gale, o ištrynimas leidžiamas abiejuose galuose. Output Restricted Deque: išvestis ribojama viename gale, bet leidžiama įterpti abiejuose galuose.
Pavyzdys: Python kodas, skirtas parodyti
Python3
from> collections>import> deque> > # Declaring deque> queue>=> deque([>'name'>,>'age'>,>'DOB'>])> > print>(queue)> |
>
>Išvestis
deque(['name', 'age', 'DOB'])>
Deque operacijos
1 pavyzdys: Veiksmingas elementų pridėjimas
- append() :- Ši funkcija naudojama įterpti vertę į savo argumentą į dešinįjį deque galą. appendleft() :- Ši funkcija naudojama įterpti vertę į argumentą kairėje deque pabaigoje.
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)> |
java string concat
>
>Išvestis
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])>
Dėl sudėtingumo analizės žr. pabaigą.
2 pavyzdys: efektyvus daiktų iššokimas
- pop() :- Ši funkcija naudojama norint ištrinti argumentą iš dešiniojo deque galo. popleft() :- Ši funkcija naudojama norint ištrinti argumentą iš kairiojo deque galo.
Python3
šališkumas ir dispersija
# 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)> |
>
>Išvestis
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])>
Dėl sudėtingumo analizės žr. pabaigą.
3 pavyzdys: prieiga prie elementų dekėje
- index(ele, beg, end) :- Ši funkcija grąžina pirmąjį argumentuose minimos reikšmės indeksą, pradedant paiešką nuo pradžios iki pabaigos indekso. insert(i, a) :- Ši funkcija įterpia argumentuose(a) paminėtą reikšmę į argumentuose nurodytą indeksą(i). remove() :- Ši funkcija pašalina pirmą argumentuose minimos reikšmės atvejį. count() :- Ši funkcija skaičiuoja argumentuose minimos reikšmės pasikartojimų skaičių.
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)> |
>
>Išvestis
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])>
Sudėtingumo analizės pabaigoje žr.
4 pavyzdys: Deque dydis
- len(dequeue) :- Grąžina dabartinį ištraukimo dydį.
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> |
>
>Išvestis
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>
Dėl sudėtingumo analizės žr. pabaigą.
5 pavyzdys: Deque priekis ir galas
- Deque[0] :- Mes galime pasiekti priekinį deque elementą naudodami indeksavimą su de[0]. Deque[-1] :- Galime pasiekti galinį deque elementą naudodami indeksavimą su de[-1].
Python3
linux paleisti komandą
# 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> |
>
>Išvestis
Current Deque: deque([1, 2, 3, 4, 5, 6]) Front element of the deque: 1 Back element of the deque: 6>
Dėl sudėtingumo analizės žr. pabaigą.
6 pavyzdys: įvairios operacijos su deque
- išplėsti (iterable) : Ši funkcija naudojama norint pridėti kelias vertes dešinėje deque pabaigoje. Priimtas argumentas yra kartojamas. Extendleft(iterable): Ši funkcija naudojama norint pridėti kelias vertes kairiajame deque gale. Priimtas argumentas yra kartojamas. Tvarka atšaukiama dėl kairiųjų priedų. reverse() :- Ši funkcija naudojama norint pakeisti deque elementų tvarką. rotate() :- Ši funkcija pasuka deque argumentuose nurodytu skaičiumi. Jei nurodytas skaičius yra neigiamas, sukimas vyksta į kairę. Kitu atveju sukimas vyksta į dešinę.
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)> |
>
>Išvestis
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])>
Dėl sudėtingumo analizės žr. pabaigą.
Sudėtingumo analizė:
| Metodai | Laiko sudėtingumas | Pagalbinė erdvė |
|---|---|---|
| pridėti () | O(1) | O(1) |
| priedas kairėje () | O(1) | O(1) |
| pop () | O(1) konvertuoti eilutę į java | O(1) |
| popleft () | O(1) | O(1) |
| indeksas (ele, beg, end) | O(N) | O(1) |
| įterpti (i, a) | O(N) | O(1) |
| pašalinti () | O(N) | O(1) |
| skaiciuoti () | O(N) | O(1) |
| tiesiog (įtraukti į eilę) | O(1) | O(1) |
| Deque[0] | O(1) | O(1) |
| Deque[-1] | O(1) | O(1) |
| pratęsti (kartojantis) | RODYKLĖ) | O(1) |
| išplėstinis kairysis (kartojantis) | RODYKLĖ) semantinė klaida | O(1) |
| atvirkščiai () | O(N) | O(1) |
| pasukti () | RODYKLĖ) | O(1) |