Python의 Deque(이중 종료 대기열)는 모듈을 사용하여 구현됩니다. 컬렉션 . Deque는 컨테이너의 양쪽 끝에서 더 빠른 추가 및 팝 작업이 필요한 경우 목록보다 Deque가 선호됩니다. 오(1) O(n) 시간 복잡도를 제공하는 목록과 비교하여 추가 및 팝 작업의 시간 복잡도입니다.
제한된 Deque 입력 유형
- 입력 제한 Deque : 한쪽 끝에서는 입력이 제한되고 양쪽 끝에서는 삭제가 허용됩니다. 출력 제한 Deque : 출력은 한쪽 끝에서 제한되지만 삽입은 양쪽 끝에서 허용됩니다.
예: 시연할 Python 코드
파이썬3
from> collections>import> deque> > # Declaring deque> queue>=> deque([>'name'>,>'age'>,>'DOB'>])> > print>(queue)> |
>
>산출
deque(['name', 'age', 'DOB'])>
데크에 대한 작업
예 1: 효율적으로 항목 추가
- append() :- 이 함수는 인수의 값을 deque의 오른쪽 끝에 삽입하는 데 사용됩니다. appendleft() :- 이 함수는 인수의 값을 deque의 왼쪽 끝에 삽입하는 데 사용됩니다.
파이썬3
arraylist에서 제거
# 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)> |
>
>산출
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() :- 이 함수는 deque의 오른쪽 끝에서 인수를 삭제하는 데 사용됩니다. popleft() :- 이 함수는 데크의 왼쪽 끝에서 인수를 삭제하는 데 사용됩니다.
파이썬3
최초의 노트북
# 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) :- 이 함수는 beg부터 end 인덱스까지 검색을 시작하여 인수에 언급된 값의 첫 번째 인덱스를 반환합니다. insert(i, a) :- 이 함수는 인수(a)에 언급된 값을 인수에 지정된 인덱스(i)에 삽입합니다. 제거() :- 이 함수는 인수에 언급된 값의 첫 번째 항목을 제거합니다. count() :- 이 함수는 인수에 언급된 값의 발생 횟수를 계산합니다.
파이썬3
# 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) :- dequeue의 현재 크기를 반환합니다.
파이썬3
# 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>
복잡성 분석은 끝을 참조하세요.
DBMS의 산성 속성
예제 5: 데크의 앞면과 뒷면
- Deque[0] :- de[0]을 사용한 인덱싱을 사용하여 deque의 앞 요소에 액세스할 수 있습니다. Deque[-1] :- de[-1]을 사용한 인덱싱을 사용하여 deque의 뒤쪽 요소에 액세스할 수 있습니다.
파이썬3
# 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: deque에 대한 다양한 작업
- extend(iterable) :- 이 함수는 deque의 오른쪽 끝에 여러 값을 추가하는 데 사용됩니다. 전달된 인수는 반복 가능합니다. extendleft(iterable) :- 이 함수는 데크의 왼쪽 끝에 여러 값을 추가하는 데 사용됩니다. 전달된 인수는 반복 가능합니다. 왼쪽 추가로 인해 순서가 반전됩니다. reverse() :- 이 함수는 deque 요소의 순서를 바꾸는 데 사용됩니다. 회전() :- 이 함수는 인수에 지정된 수만큼 데크를 회전합니다. 지정된 숫자가 음수이면 왼쪽으로 회전됩니다. 그렇지 않으면 오른쪽으로 회전합니다.
파이썬3
# 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) |
| 왼쪽에 추가() | 오(1) | 오(1) |
| 팝() | 오(1) | 오(1) |
| 팝레프트() | 오(1) | 오(1) |
| index(ele, 구걸, 끝) | 에) | 오(1) |
| 삽입(나, a) | 에) | 오(1) |
| 제거하다() | 에) | 오(1) |
| 세다() | 에) | 오(1) |
| 그냥 (큐에서 빼기) | 오(1) | 오(1) |
| 데크[0] | 오(1) | 오(1) |
| 데크[-1] | 오(1) | 오(1) |
| 확장(반복 가능) | 화살) | 오(1) 자바 부울 |
| 확장왼쪽(반복 가능) | 화살) | 오(1) |
| 뒤집다() | 에) | 오(1) |
| 회전() | 화살) | 오(1) |