logo

En in Python

Deque (Doubly Ended Queue) in Python wordt geïmplementeerd met behulp van de module collecties . Deque heeft de voorkeur boven een lijst in de gevallen waarin we snellere append- en pop-bewerkingen vanaf beide uiteinden van de container nodig hebben, omdat deque een O(1) tijdcomplexiteit voor append- en pop-bewerkingen in vergelijking met een lijst die O(n)-tijdcomplexiteit biedt.

Soorten beperkte Deque-invoer

    Invoer beperkt deque: invoer is aan één kant beperkt, terwijl verwijdering aan beide kanten is toegestaan. Output Restricted Deque: de uitvoer is aan één kant beperkt, maar invoeging is aan beide kanten toegestaan.

Voorbeeld: Python-code om te demonstreren

Python3








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

javascript voor vervolgkeuzelijst



>

>

Uitvoer

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

Operaties op deque

Voorbeeld 1: Items efficiënt toevoegen

    append() :- Deze functie wordt gebruikt om de waarde in zijn argument in te voegen aan het rechteruiteinde van de deque. appendleft() : - Deze functie wordt gebruikt om de waarde in zijn argument in te voegen aan de linkerkant van de 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)>

>

>

Uitvoer

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

Raadpleeg het einde voor complexiteitsanalyse.

Voorbeeld 2: Items efficiënt uitklappen

    pop() : - Deze functie wordt gebruikt om een ​​argument aan de rechterkant van de deque te verwijderen. popleft() : - Deze functie wordt gebruikt om een ​​argument aan de linkerkant van de deque te verwijderen.

Python3


Java-einde



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

>

>

Uitvoer

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

Raadpleeg het einde voor complexiteitsanalyse.

Voorbeeld 3: Toegang tot items in een deque

    index(ele, beg, end): - Deze functie retourneert de eerste index van de waarde vermeld in de argumenten, beginnend met zoeken vanaf beg tot eindindex. insert(i, a) :- Deze functie voegt de waarde in die wordt vermeld in argumenten(a) bij index(i) gespecificeerd in argumenten. remove() :- Deze functie verwijdert de eerste keer dat de waarde vermeld in de argumenten voorkomt. count() : - Deze functie telt het aantal keren dat de waarde in de argumenten voorkomt.

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

>

>

Uitvoer

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

Raadpleeg het einde voor complexiteitsanalyse.

Voorbeeld 4: Grootte van een deque

    len(dequeue): - Geeft de huidige grootte van de dequeue terug.

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>

>

>

Uitvoer

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>

Raadpleeg het einde voor complexiteitsanalyse.

Voorbeeld 5: Voor- en achterkant van een deque

    Deque[0]: - We hebben toegang tot het voorste element van de deque door middel van indexering met de[0]. Deque[-1]: - We hebben toegang tot het achterste element van de deque door middel van indexering met 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>

>

>

Uitvoer

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

Raadpleeg het einde voor complexiteitsanalyse.

Voorbeeld 6: Verschillende bewerkingen op deque

    extend(iterable): - Deze functie wordt gebruikt om meerdere waarden toe te voegen aan het rechteruiteinde van de deque. Het doorgegeven argument is itereerbaar. extendleft(iterable): - Deze functie wordt gebruikt om meerdere waarden toe te voegen aan de linkerkant van de deque. Het doorgegeven argument is itereerbaar. De volgorde is omgekeerd als gevolg van linkse toevoegingen. reverse() : - Deze functie wordt gebruikt om de volgorde van deque-elementen om te keren. roteren() : - Deze functie roteert de deque met het getal dat is opgegeven in de argumenten. Als het opgegeven getal negatief is, vindt rotatie naar links plaats. Anders is de rotatie naar rechts.

Python3




tekenreeks vergelijken c#

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

>

>

Uitvoer

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

Raadpleeg het einde voor complexiteitsanalyse.

Complexiteitsanalyse:

Methoden

Tijdcomplexiteit

Hulpruimte

toevoegen()

O(1)

O(1)

links toevoegen()

O(1)

O(1)

knal()

O(1)

O(1)

popleft()

O(1)

O(1)

index(ele, bedelen, einde)

OP)

O(1)

invoegen(ik, een)

java elseif

OP)

O(1)

verwijderen()

OP)

O(1)

graaf()

OP)

O(1)

gewoon (uit de wachtrij)

O(1)

formaatreeks java

O(1)

Deque[0]

O(1)

O(1)

Vraag[-1]

O(1)

O(1)

uitbreiden (itereerbaar)

PIJL)

O(1)

extendleft(itereerbaar)

PIJL)

O(1)

achteruit()

OP)

O(1)

draaien()

PIJL)

O(1)