deque는 스택과 큐의 기능을 모두 가진 객체로 출입구를 양쪽에 가지고 있다. Show 스택처럼써도 되고, 큐처럼 써도 된다. 여러가지 메서드를 이용해서 이런 기능을 구현한다. 먼저 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
Example: Python code to demonstrate dequePython3
Output: deque(['name', 'age', 'DOB']) Operations on dequeExample 1: Appending Items Efficiently
Python3
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
Python3
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
Python3
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
Python3
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]) |