deque는 스택과 큐의 기능을 모두 가진 객체로 출입구를 양쪽에 가지고 있다.
스택처럼써도 되고, 큐처럼 써도 된다.
여러가지 메서드를 이용해서 이런 기능을 구현한다.
먼저 deque를 만들어보자
>>> from collections import deque
>>> dq = deque('love')
>>> dq
deque(['l', 'o', 'v', 'e'])
문자열을 이용해 deque를 만들면 각 문자가 요소로 된 리스트 형태의 deque가 만들어진다.
1. 스택 구현 : append(), pop()
스택은 마지막(오른쪽끝)에서 입출력한다.
입력시에는 append() 메서드를 이용하고, 출력시에는 pop()을 이용한다.
>>> dq.append('m') # 오른쪽 끝에 항목추가
>>> dq
deque(['l', 'o', 'v', 'e', 'm'])
>>> dq.pop() # 오른쪽 끝에 항목가져오면서 삭제
'm'
>>> dq
deque(['l', 'o', 'v', 'e'])
2. 큐 구현 : appendleft(), pop(), append(), popleft()
큐는 왼쪽(처음)에서 입력되고, 오른쪽(마지막)에서 출력된다.
오른쪽 출력 시는 위에서 봤던대로 pop()을 사용하면 된다.
왼쪽에 값을 입력할 때는 appendleft() 메서드를 사용한다.
반대로 오른쪽에 값을 넣고 싶으면 append(), 왼쪽에서 값을 빼고 싶으면 popleft()를 사용한다.
>>> dq.appendleft('I') # 왼쪽에서 'I'입력
>>> dq
deque(['I', 'l', 'o', 'v', 'e'])
>>> dq.pop() # 오른쪽에서 'e'출력
'e'
>>> dq
deque(['I', 'l', 'o', 'v'])
3. deque 확장하기 : extend(), extendleft()
deque를 확장할때는 extend() 메서드를 사용한다. 기본적으로 오른쪽으로 확장된다.
왼쪽으로 확장하고 싶을 때는 extendleft() 메서드를 사용한다.
>>> dq
deque(['l', 'o', 'v', 'e'])
>>> dq.extend('you') # 오른쪽으로 'y','o','u' 확장
>>> dq
deque(['l', 'o', 'v', 'e', 'y', 'o', 'u'])
>>> dq.extendleft('I') # 왼쪽으로 'I' 확장
>>> dq
deque(['I', 'l', 'o', 'v', 'e', 'y', 'o', 'u'])
4. 리스트처럼 사용 : insert(), remove()
deque는 리스트처럼 중간 내용을 수정하거나 새 항목을 입력하거나 삭제할 수 있다.
>>> dq
deque(['l', 'o', 'v', 'e'])
>>> dq[2]='n' # 인덱스를 이용한 항목 수정 'v' => 'n'
>>> dq
deque(['l', 'o', 'n', 'e'])
새 항목을 입력하거나 기본 항목을 삭제할 때는 insert()메서드와 remove()메서드를 사용한다.
>>> dq = deque('love')
>>> dq.insert(0, 'K') # 첫번째 항목에 'K'를 추가
>>> dq
deque(['K', 'l', 'o', 'v', 'e'])
>>> dq.insert(100, 'K') # 100번째 항목(없으니까 가장 큰 쪽에)에 'K' 추가
>>> dq
deque(['K', 'l', 'o', 'v', 'e', 'K'])
>>> dq.remove('K') # 'K'항목 삭제
>>> dq
deque(['l', 'o', 'v', 'e', 'K']) # 나도 몰랐었던 부분인데, 같은 항목이 있을때 지우면 왼쪽부터 삭제됨.
>>> dq.remove('K')
>>> dq
deque(['l', 'o', 'v', 'e']) # 오른쪽에 있는 'K'삭제
5. deque의 내용을 좌우로 반전 : reverse()
deque의 내용을 반전시키고 싶으면 reverse() 메서드를 사용하면 된다.
>>> dq
deque(['l', 'o', 'v', 'e'])
>>> dq.reverse()
>>> dq
deque(['e', 'v', 'o', 'l'])
Deque (Doubly Ended Queue) in Python is implemented using the module “collections“. Deque is preferred over a list in the cases where we need quicker append and pop operations from both the ends of the container, as deque provides an O(1) time complexity for append and pop operations as compared to a list that provides O(n) time complexity.
Types of Restricted Deque Input
- Input Restricted Deque: Input is limited at one end while deletion is permitted at both ends.
- Output Restricted Deque: output is limited at one end but insertion is permitted at both ends.
Example: Python code to demonstrate deque
Python3
from collections import deque
queue = deque(['name','age','DOB'])
print(queue)
Output:
deque(['name', 'age', 'DOB'])Operations on deque
Example 1: Appending Items Efficiently
- append():- This function is used to insert the value in its argument to the right end of the deque.
- appendleft():- This function is used to insert the value in its argument to the left end of the deque.
Python3
import collections
de = collections.deque([1, 2, 3])
print("deque: ", de)
de.append(4)
print("\nThe deque after appending at right is : ")
print(de)
de.appendleft(6)
print("\nThe deque after appending at left is : ")
print(de)
Output:
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])Example 2: Popping Items Efficiently
- pop():- This function is used to delete an argument from the right end of the deque.
- popleft():- This function is used to delete an argument from the left end of the deque.
Python3
import collections
de = collections.deque([6, 1, 2, 3, 4])
print("deque: ", de)
de.pop()
print("\nThe deque after deleting from right is : ")
print(de)
de.popleft()
print("\nThe deque after deleting from left is : ")
print(de)
Output:
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])Example 3: Accessing Items in a deque
- index(ele, beg, end):- This function returns the first index of the value mentioned in arguments, starting searching from beg till end index.
- insert(i, a) :- This function inserts the value mentioned in arguments(a) at index(i) specified in arguments.
- remove():- This function removes the first occurrence of the value mentioned in arguments.
- count():- This function counts the number of occurrences of value mentioned in arguments.
Python3
import collections
de = collections.deque([1, 2, 3, 3, 4, 2, 4])
print ("The number 4 first occurs at a position : ")
print (de.index(4,2,5))
de.insert(4,3)
print ("The deque after inserting 3 at 5th position is : ")
print (de)
print ("The count of 3 in deque is : ")
print (de.count(3))
de.remove(3)
print ("The deque after deleting first occurrence of 3 is : ")
print (de)
Output:
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])Example 4: Different operations on deque
- extend(iterable):- This function is used to add multiple values at the right end of the deque. The argument passed is iterable.
- extendleft(iterable):- This function is used to add multiple values at the left end of the deque. The argument passed is iterable. Order is reversed as a result of left appends.
- reverse():- This function is used to reverse the order of deque elements.
- rotate():- This function rotates the deque by the number specified in arguments. If the number specified is negative, rotation occurs to the left. Else rotation is to right.
Python3
import collections
de = collections.deque([1, 2, 3,])
de.extend([4,5,6])
print ("The deque after extending deque at end is : ")
print (de)
de.extendleft([7,8,9])
print ("The deque after extending deque at beginning is : ")
print (de)
de.rotate(-3)
print ("The deque after rotating deque is : ")
print (de)
de.reverse()
print ("The deque after reversing deque is : ")
print (de)
Output :
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])