logo

І на Python

Deque (Doubly Ended Queue) у Python реалізовано за допомогою модуля колекції . Deque є кращим над списком у випадках, коли нам потрібні швидші операції додавання та висунення з обох кінців контейнера, оскільки deque забезпечує О(1) часова складність для операцій додавання та висунення порівняно зі списком, який надає O(n) часову складність.

Типи обмеженого введення Deque

    Deque з обмеженим введенням: введення обмежено з одного боку, а видалення дозволено з обох кінців. Обмеження виводу Deque: вихід обмежений на одному кінці, але вставка дозволена на обох кінцях.

Приклад: код Python для демонстрації

Python3








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



>

>

Вихід

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

Операції над deque

Приклад 1: Ефективне додавання елементів

    append() :- Ця функція використовується, щоб вставити значення в її аргументі в правий кінець двох рядків. appendleft() :- Ця функція використовується для вставлення значення в її аргументі в лівий кінець дек.

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

спати в javascript
>

>

Вихід

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

Зверніться до кінця для аналізу складності.

Приклад 2: Ефективне видалення предметів

    pop() :- Ця функція використовується для видалення аргументу з правого кінця другої чергування. popleft() :- Ця функція використовується для видалення аргументу з лівого кінця багатоканальної послідовності.

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

>

>

Вихід

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

Зверніться до кінця для аналізу складності.

Приклад 3: Доступ до елементів у черзі

    index(ele, beg, end) :- Ця функція повертає перший індекс значення, згаданого в аргументах, починаючи пошук від початку до кінця індексу. insert(i, a) :- Ця функція вставляє значення, згадане в arguments(a) за індексом(i), вказаним в arguments. remove() :- Ця функція видаляє перше входження значення, згаданого в аргументах. count() :- Ця функція підраховує кількість входжень значення, згаданого в аргументах.

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

>

>

Вихід

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

Зверніться до кінця для аналізу складності.

Приклад 4: Розмір дека

    len(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>

>

>

Вихід

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>

Зверніться до кінця для аналізу складності.

Приклад 5: передня та задня сторони дека

    Deque[0] : - Ми можемо отримати доступ до початкового елемента deque за допомогою індексації за допомогою de[0]. Deque[-1] : - Ми можемо отримати доступ до заднього елемента deque за допомогою індексації за допомогою 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>

>

>

Вихід

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

Зверніться до кінця для аналізу складності.

Приклад 6: Різні операції над дек

    extend(iterable) :- Ця функція використовується для додавання кількох значень у правий кінець двох рядів. Переданий аргумент повторюється. extendleft(iterable) :- Ця функція використовується для додавання кількох значень у лівому кінці ряду. Переданий аргумент повторюється. Порядок змінюється в результаті додавання зліва. reverse() :- Ця функція використовується для зміни порядку елементів deque. rotate() :- Ця функція обертає двічі на число, вказане в аргументах. Якщо вказане число від'ємне, поворот відбувається вліво. В іншому випадку обертання праворуч.

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

>

>

Вихід

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

Зверніться до кінця для аналізу складності.

Аналіз складності:

методи

Складність часу

Допоміжний простір

додати()

О(1)

О(1)

appendleft()

О(1)

О(1)

поп()

О(1)

О(1)

popleft()

О(1)

О(1)

index(ele, beg, end)

O(N)

О(1)

вставити (i, a)

O(N)

О(1)

видалити()

O(N)

О(1)

рахувати()

O(N)

О(1)

просто (виключити з черги)

О(1)

О(1)

Deque[0]

О(1)

О(1)

Deque[-1]

О(1)

О(1)

розширити (повторюється)

СТРІЛКА)

О(1)

extendleft (ітераційний)

СТРІЛКА)

О(1)

зворотний()

O(N)

О(1)

обертати()

СТРІЛКА)

О(1)