[자료구조] 큐 (Queue)와 데크 (Deque)

이전의 후위표기식 문제를 해결하는데에는 스택 (Stack) 자료구조가 활용되었다.
이번에는 또다른 자료구조인 큐 (Queue) 에 대해 이해해 보고자한다.

1. 큐 (Queue)

큐 (Queue)
후입선출 (LIFO) 이었던 Stack 과 달리 큐는 선입선출을 기본으로 하는 자료구조형이다.
First In First Out으로 먼저 담긴 값이 먼저 반환되는것을 의미한다.

예시로는 티켓부스에서 티켓을 구매하기 위해 줄선 모습을 상상하면된다. 먼저 줄 선 사람이 먼저 티켓을 구매하는 것이 선입선출의 예 이다.
업무로 연관을 지어보면, 본인이 일하는 회사의 프로그램 구조에서는 이 "큐" 를 적극 활용하고 있다.
"유저의 여러 액션을 하나의 메세지로 만들어 이를 하나의 SQS에 전송하고 하고 FIFO 방식으로 전달된 메세지들을 SQS에서 처리하여 각 기능을 담당하는 프로젝트를 호출" 하게 된다.

만약 이런 구조에서 Stack방식을 활용했다면 가장 먼저 요청들어온 유저 액션이 가장 나중에 처리되었을 것이다.

이처럼 먼저들어온것을 먼저 처리해 주는 방식이 FIFO 방식의 큐 자료구조이다.

2. 큐 (Queue) 와 데크 (Deque)

앞서 말했듯 큐 는 FIFO 방식이다. 이때 "입"과 "출"의 방향은 단방향이다. 양쪽에서 데이터를 넣고, 양쪽에서 빼는 구조는 아닌 것이다.
이와 달리 python에 존재하는 내장함수 deque는 FIFO 방식의 큐를 기반으로 한 양방향 큐 자료구조이다.

이미지 출처 :  https://www.studytonight.com/java-examples/arraydeque-in-java

양방향 출입을 허용하는 데크 (Deque) 는 때론 스택, 때론 큐 를 대체할수 있으며 list 구조에서 데이터 삽입, 반출하는 때 보다 단축된 시간복잡도를 갖는다고 한다. (이 부분은 시간복잡도에 대해 더 이해해야 할듯)

3. python의 데크 (Deque) 사용법

데크는 단방향인 큐와 달리 양방향 이라고 했다. 따라서 좌, 우 모두 값 추가가 가능하며 좌, 우 모두 값 삭제도 가능하다.
queue 자료구조에서 값의 입, 출은 append와 pop 으로 수행한다.
deque 에서는 이를 양방향으로 진행하기 위해 appendleft 와 popleft 를 지원한다.

시간복잡도 | deque함수 | 설명
O(1)    | deque.append(x) : x를 데크의 오른쪽 끝에 삽입 : [0,0,0] -> [0,0,0,x]

O(1)    | deque.appendleft(x) : x를 데크의 왼쪽 끝에 삽입 : [0,0,0] -> [x,0,0,0]

O(1)    | deque.pop() : 데크의 오른쪽 끝 값 삭제 : [y,0,0,x] -> [y,0,0]

O(1)    | deque.popleft() : 데크의 왼쪽 끝 값 삭제 : [y,0,0,x] -> [0,0,x]

O(k)    | deque.extend(array) : 배열 array를 순환하면서 데크의 오른쪽에 추가 : [0,1,2].extend([a,b,c]) -> [0,1,2,a,b,c]

O(k)    | deque.extendleft(array) : 배열 array를 순환하면서 데크의 왼쪽에 추가 : [0,1,2].extendleft([a,b,c]) -> [c,b,a,0,1,2]

O(N)    | deque.reverse() : 데크의 요소들을 제자리에서 순서를 뒤집고 None을 반환 : [1,2,3,4] -> [4,3,2,1]

O(N)    | deque.remove(x) : x를 데크에서 찾아 삭제. 이때 값 x 가 없으면 ValueError가 발생한다.

O(K)    | deque.rotate(num) : 데크를 num만큼 회전한다 (양수면 오른쪽, 음수는 왼쪽으로) : 이때 동작은 pop 된 값을 append 하는것과 일치하다.

deque의 append, appendleft, pop, popleft 등을 활용하여 주어진 리스트에서 주어진 우선순위에 따라 특정 값이 몇번째로 처리되는지에 대한 문제를 해결할 수 있다.