큐(Queue,deque,list)

정의 및 장단점

큐는 선입선출,FIFO(First In First Out)의 방식이다. 

가정 먼저 들어온 데이터가 가장 먼저 나간다. 제일 먼저 들어온 데이터를 HEAD, 맨 뒤의 데이터를 TAIL이라고 한다.

구현방법

파이썬에서는 리스트방식 또는 라이브러리를 이용한 방식으로 나뉜다.

 

리스트방식: 

pop(0) 또는 insert(0,x)등의 방법은 복잡도가 O(n)이므로 아래의 다른 방법보다 불리하다.

리스트의 마지막 원소의 삭제는 O(1)이지만, 첫번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)입니다. 자료구조 뒤에서 추가/삭제는 덱과 리스트는 속도 차이가 없지만, 첫번째 원소를 추가 삭제한다면 극명한 속도 차이가 발생합니다.

데이터가 커지고 데이터의 양끝에서 처리가 일어나면 리스트보다 deque를 이용하는 것이 유리할 수 있다.

>>> queue = [4, 5, 6]
>>> queue.append(7)
>>> queue.append(8)
>>> queue
[4, 5, 6, 7, 8]
>>> queue.pop(0)
4
>>> queue.pop(0)
5
>>> queue
[6, 7, 8]

 

Queue 라이브러리방식:

리스트나 디큐와 다르게 일방향이다. 인덱스접근이 불가능하다.

>>> from queue import Queue
>>>
>>> que = Queue()
>>> que.put(4)
>>> que.put(5)
>>> que.put(6)
>>> que.get()
4
>>> que.get()
5
>>> que.get()
6

 

deque 라이브러리 방식:

double ended queue 의 약자로 데이터를 양방향에서 추가하고 제어할 수 있는 자료 주고입니다.

리스트에는 없는 popleft()메서드를 지원한다.

>>> from collections import deque
>>>
>>> queue = deque([4, 5, 6])
>>> queue.append(7)
>>> queue.append(8)
>>> queue
deque([4, 5, 6, 7, 8])
>>> queue.popleft()
4
>>> queue.popleft()
5
>>> queue
deque([6, 7, 8])

popleft()뿐만 아니다 appendleft()메소드도 지원한다,.

>>> from collections import deque
>>>
>>> queue = deque([4, 5, 6])
>>> queue.appendleft(3)
>>> queue.appendleft(2)
>>> queue
deque([2, 3, 4, 5, 6])
>>> queue.pop()
6
>>> queue.pop()
5
>>> queue
deque([2, 3, 4])

양쪽에 대한 연산에 이점이 있지만 무작위 접근에 대한 시간 복잡도가 리스트와 달리 O(n)이다.

내부적으로 linked list를 사용하기에 i번째 데이터에 접근시 i번의 순회(iteration)이 필요하다.

양끝 데이터에 대한 접근이 유리하지만 중간데이터는 상대적으로 느리다.