[자료구조] Queue

Queue

1.Queue란 무엇인가?

Queue는 선입선출(FIFO) 논리 기반으로 데이터를 저장하기 위해 개발된 선형적 자료구조다. Stack과 형태적으로 유사하다. 유일한 차이점은 Queue는 양 끝단이 열려있다는 것이다. 한쪽 끝으로는 데이터를 추가하고 반대쪽 끝으로는 데이터를 제거하는데 사용된다. 이때 데이터를 추가하는 작업을 Enque,제거하는 작업을 Deque 라고 한다.

2.Queue vs Array

Queue는 Array와도 동일한 형태를 보인다. 하지만 Array가 각각의 요소를 Index로 접근할 수 있는 것에 비해 Queue는 불가능하다. 오로지 양 끝단에서 데이터를 추가하거나 삭제하는 것만 가능하다.

3.Queue의 시간복잡도

Queue는 빅오 표기법으로 시간복잡도가 O(1)이다. Queue는 각각 Array,LinkedList로 구현할 수 있는데, Enque의 경우 어떠한 경우에도 O(1)이고 Deque는 상황에 따라 다른 시간복잡도를 보인다.

Array

Array로 구현된 Queue는 Deque시 O(N)만큼의 시간복잡도를 가진다. Array의 특성상 Index기반으로 구현되기 때문에 요소가 제거되면 각 요소의 Index를 -1 해줘야 하기 때문이다.

LinkedList

LinkedList로 구현된 Queue는 Deque도 O(1) 만큼의 시간복잡도를 가진다. Index가 없고 Node간의 연결만 존재하기 때문에 마지막 Node만 제거되면 추가 작업이 필요 없기 때문이다.

4.Queue in Python

Queue 자료구조는 Pyhton 내에서 deque로 구현되어있다. Queue라는 라이브러리가 존재하지만 일반적인 Queue 자료구조와는 사뭇 다르다. Queue의 내부 구조를 간단히 보면 threading 관련 내용이 눈에 띈다. 그래서 찾아보니 멀티 스레드 환경에서 스레드의 안전한 소통을 위해 만들어진 라이브러리 라는 설명이 있었다.

Queue의 내부 구조

collections.deque is an alternative implementation of unbounded queues with fast atomic append() and popleft() operations that do not require locking.

또, 공식문서의 내용처럼 deque가 대체제로써 훌륭하고 locking을 요구하지 않는다는다고 한다. 실제로 Queue의 내부에는 collections.deque로 구현된 내용을 찾아볼 수 있다. 즉 멀티 스레딩 환경이 아니라면, deque를 사용하는 것이 바람직 해보인다.