[자료구조] 큐 (Queue)

큐란?

큐는 스택과 함께 대표되는 선형 자료구조이다. 큐는 스택과 다르게 들어오는 방향과 나가는 방향이 정해져 있다.

선입선출(FIFO) 자료구조로 큐 안에 먼저 입력된 원소가 큐에서 꺼낼 때도 제일 먼저 출력된다.

계산대에 줄을 선 사람들 (들어온 순서대로 먼저 계산을 하고 나가는 모습) 이나 프린터기에서 먼저 들어온 순서대로 인쇄가 되는 모습을 생각하면 된다.

 

큐 안에 원소를 집어넣는 enque 연산, 맨 먼저 입력된 원소를 출력하는 deque 연산을 갖고

추가적으로 필요에 따라 가장 앞선 원소를 확인하는 front 연산이나 가장 마지막 원소를 확인하는 rear 연산을 구현할 수 있다.

 

큐 연산의 전체적인 모습

 

큐를 배열로 구현할 때는 몇가지 문제점이 존재한다. enqueue를 할 때는 문제가 발생하지 않지만 deque를 할 때 문제가 발생한다. 계속 데이터가 앞으로 밀려나가고 deque된 자리에는 데이터가 들어가지 않는 문제가 발생하는데 이런 문제점은 원형 버퍼(원형 큐)를 이용하면 해결 가능하다.

 

이외에도 deque연산을 해서 배열의 처음 부분의 원소를 출력하면 나머지 원소들의 자리를 한 칸씩 앞으로 옮겨줘야하는데 이런 경우 매 deque연산마다 O(n)이라는 시간이 걸린다. 이 문제점은 이중 연결리스트를 사용하면 쉽게 해결할 수 있는데 이렇게 만들어진 자료구조를 데크(Deque)라고 한다.

 

데크(Deque)

기본적인 큐는 rear에서는 원소의 입력을, front에서는 원소의 출력을 할 수 있다. 데크는 이중 연결리스트를 이용해 구현되는데 큐와는 다르게 앞뒤 어디서든 원소의 입력과 출력이 가능하다. 또 deque 연산을 해도 시간복잡도 O(1)을 갖기 때문에 배열로 구현된 큐에 비해 훨씬 빠른 속도를 가질 수 있다. 

 

이중 연결리스트로 구현된 데크

리스트와 다르게 맨 앞의 노드를 삭제하면 O(1)로 원소를 삭제할 수 있고 마지막 원소를 사용할 때도 마찬가지이다. 파이썬은 collections에서 deque를 기본적으로 지원하므로 별도로 구현할 필요없이 사용할 수 있다는 장점이 있다.