logo

Och i Python

Deque (Double Ended Queue) i Python implementeras med hjälp av modulen samlingar . Deque föredras framför en lista i de fall vi behöver snabbare append- och pop-operationer från båda ändarna av behållaren, eftersom deque ger en O(1) tidskomplexitet för append- och popoperationer jämfört med en lista som ger O(n) tidskomplexitet.

Typer av begränsad deque-ingång

    Input Begränsad Deque: Inmatning är begränsad i ena änden medan radering är tillåten i båda ändar. Output Restricted Deque: utgången är begränsad i ena änden men insättning är tillåten i båda ändarna.

Exempel: Python-kod för att demonstrera

Python3








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



>

>

Produktion

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

Operationer på bord

Exempel 1: Lägga till artiklar effektivt

    append() :- Den här funktionen används för att infoga värdet i dess argument till höger i dequen. appendleft() :- Den här funktionen används för att infoga värdet i dess argument till vänster i 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)>

>

mikrolitisk kärna
>

Produktion

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 slutet för komplexitetsanalys.

Exempel 2: Popping objekt effektivt

    pop() :- Denna funktion används för att ta bort ett argument från den högra änden av dequen. popleft():- Denna funktion används för att ta bort ett argument från den vänstra änden av dequen.

Python3


python lista initialisera



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

>

>

Produktion

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 slutet för komplexitetsanalys.

Exempel 3: Tillgång till föremål i en deque

    index(ele, beg, end):- Den här funktionen returnerar det första indexet för värdet som nämns i argumenten, och börjar söka från början till slutindex. infoga(i, a) :- Denna funktion infogar värdet som nämns i argument(a) vid index(i) specificerat i argument. remove() :- Denna funktion tar bort den första förekomsten av värdet som nämns i argument. count() :- Denna funktion räknar antalet förekomster av värde som nämns i argument.

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

>

>

Produktion

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 slutet för komplexitetsanalys.

Exempel 4: Storleken på en deque

    len(dequeue):- Returnera den aktuella storleken 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>

>

>

Produktion

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 slutet för komplexitetsanalys.

Exempel 5: Fram- och baksidan av en deque

    Deque[0] :- Vi kan komma åt det främre elementet i dequen genom att indexera med de[0]. Deque[-1] :- Vi kan komma åt bakre delen av dequen genom att indexera med de[-1].

Python3




vad är bikupa

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

>

>

Produktion

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

Se slutet för komplexitetsanalys.

Exempel 6: Olika operationer på bord

    extend(iterable) :- Den här funktionen används för att lägga till flera värden i den högra änden av dequen. Argumentet som passerats är iterabelt. extendleft(iterable):- Denna funktion används för att lägga till flera värden i den vänstra änden av dequen. Argumentet som passerats är iterabelt. Ordningen är omvänd som ett resultat av vänster tillägg. reverse() :- Denna funktion används för att vända om ordningen på deque-element. rotate() :- Den här funktionen roterar dequen med det antal som anges i argumenten. Om det angivna talet är negativt sker rotation åt vänster. Annars är rotationen åt höger.

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

>

>

Produktion

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 slutet för komplexitetsanalys.

Komplexitetsanalys:

Metoder

upcasting

Tidskomplexitet

Hjälputrymme

bifoga()

O(1)

O(1)

appendleft()

O(1)

O(1)

pop()

O(1)

O(1)

popleft()

O(1)

O(1)

index(ele, beg, slut)

PÅ)

O(1)

infoga(i, a)

PÅ)

O(1)

avlägsna()

PÅ)

O(1)

räkna()

PÅ)

O(1)

bara (av kö)

O(1)

O(1)

Deque[0]

O(1)

O(1)

Deque[-1]

O(1)

O(1)

förlänga (iterbar)

PIL)

O(1)

extendleft(iterable)

PIL)

O(1)

omvänd()

Ersätt java sträng

PÅ)

O(1)

rotera()

PIL)

O(1)