logo

Og i Python

Deque (Double Ended Queue) i Python implementeres ved hjelp av modulen samlinger . Deque foretrekkes fremfor en liste i tilfeller der vi trenger raskere append- og pop-operasjoner fra begge endene av beholderen, da deque gir en O(1) tidskompleksitet for append- og pop-operasjoner sammenlignet med en liste som gir O(n)-tidskompleksitet.

Typer begrenset Deque Input

    Input Restricted Deque: Input er begrenset i den ene enden mens sletting er tillatt i begge ender. Output Restricted Deque: utgangen er begrenset i den ene enden, men innsetting er tillatt i begge ender.

Eksempel: Python-kode for å demonstrere

Python3








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



>

>

Produksjon

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

Operasjoner på dekk

Eksempel 1: Effektivt legge til elementer

    append() :- Denne funksjonen brukes til å sette inn verdien i argumentet til høyre enden av dequen. appendleft() :- Denne funksjonen brukes til å sette inn verdien i argumentet til venstre enden av dequen.

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)>

>

>

Produksjon

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])>

Se slutten for kompleksitetsanalyse.

Eksempel 2: Popping elementer effektivt

    pop() :- Denne funksjonen brukes til å slette et argument fra høyre ende av deque. popleft():- Denne funksjonen brukes til å slette et argument fra venstre ende av 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)>

>

>

Produksjon

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])>

Se slutten for kompleksitetsanalyse.

Eksempel 3: Tilgang til gjenstander i en deque

    index(ele, beg, end):- Denne funksjonen returnerer den første indeksen av verdien nevnt i argumenter, og begynner å søke fra begynnelse til sluttindeks. insert(i, a) :- Denne funksjonen setter inn verdien nevnt i argumenter(a) ved indeks(i) spesifisert i argumenter. remove() :- Denne funksjonen fjerner den første forekomsten av verdien nevnt i argumenter. count() :- Denne funksjonen teller antall forekomster av verdi nevnt i argumenter.

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)>

>

>

Produksjon

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])>

Se slutten for kompleksitetsanalyse.

Eksempel 4: Størrelsen på en deque

    len(dequeue):- Returner gjeldende størrelse på dequeue.

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>

>

>

Produksjon

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>

Se slutten for kompleksitetsanalyse.

Eksempel 5: Forsiden og baksiden av en deque

    Deque[0] :- Vi kan få tilgang til frontelementet av deque ved å bruke indeksering med de[0]. Deque[-1] :- Vi kan få tilgang til bakelementet i deque ved å bruke indeksering med de[-1].

Python3




start mysql ubuntu på nytt
# 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>

>

>

Produksjon

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

Se slutten for kompleksitetsanalyse.

Eksempel 6: Ulike operasjoner på bord

    extend(iterable):- Denne funksjonen brukes til å legge til flere verdier på høyre side av deque. Argumentet som ble bestått er gjentakelig. extendleft(iterable):- Denne funksjonen brukes til å legge til flere verdier i venstre ende av deque. Argumentet som ble bestått er gjentakelig. Rekkefølgen er reversert som følge av venstre vedlegg. reverse() :- Denne funksjonen brukes til å reversere rekkefølgen på deque-elementer. rotate() :- Denne funksjonen roterer deque med tallet spesifisert i argumenter. Hvis tallet som er spesifisert er negativt, skjer rotasjon til venstre. Ellers er rotasjonen til høyre.

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)>

>

>

Produksjon

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])>

Se slutten for kompleksitetsanalyse.

Kompleksitetsanalyse:

Metoder

Tidskompleksitet

Auxiliary Space

legge til()

O(1)

O(1)

appendleft()

O(1)

O(1)

pop()

O(1)

O(1)

popleft()

O(1)

O(1)

indeks (ele, beg, slutt)

PÅ)

O(1)

sette inn(i, a)

PÅ)

O(1)

fjerne()

PÅ)

O(1)

telle()

PÅ)

O(1)

bare (avkø)

O(1)

O(1)

Deque[0]

O(1)

O(1)

Deque[-1]

O(1)

O(1)

forlenge (gjentagbar)

PIL)

O(1)

extendleft(iterbar)

PIL)

O(1)

omvendt()

PÅ)

O(1)

rotere()

PIL)

O(1)