큐(Queue)
큐는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 **FIFO(First In First Out)**구조로 데이터를 저장한다. 쉽게 이야기 하면 은행에서 번호표를 뽑을 때 가장 먼저 번호표를 뽑은 사람이 번호표를 늦게 뽑은 사람보다 빠르게 업무를 볼 수 있는 것처럼 생각하면 된다.
큐는 가장 일찍 추가된 데이터를 Front
, 마지막에 추가된 데이터를 Rear
라고 한다. 그리고 큐에 Enqueue
를 통해 데이터를 하나씩 추가를 할 때마다 Rear
가 입력된 데이터로 변경이 되고, Dequeue
를 통해 큐의 데이터를 하나씩 제거해 나가면 기존의 Front
는 제거되고 가장 앞에 있는 데이터가 Front
가 된다.
정리를 해보면 다음과 같다.
Front
: 큐 자료구조에서 가장 앞에 있는 데이터 (가장 일찍 추가된 데이터)Rear
: 큐 자료구조에서 가장 뒤에 있는 데이터 (가장 나중에 추가된 데이터)Enqueue
: 큐 자료구조 맨 뒤에 새로운 데이터를 추가Dequeue
: 큐 자료구조 맨 앞에있는 데이터를 제거
큐는 배열로도 구현할 수 있고 링크드 리스트로도 구현을 할 수 있는데 배열로 구현할 경우 치명적인 단점이 생긴다. 데이터를 추가하거나 제거할 때마다 데이터가 들어가있는 인덱스를 모두 수정해야 하기 때문에 자료구조의 크기가 클수록 효율성이 떨어지게 된다. 그래서 배열로 큐를 구현할때는 원형 큐로 구현한다.
원형 큐(Circle Queue)
큐를 배열로 구현하면 다음과 같이 정해진 길이의 큐를 원형으로 구현하게 된다. 원형큐의 Rear
과 Front
는 0
인덱스에서 부터 시작하며 Enqueue
가 이뤄지면 Rear + 1
의 인덱스에 데이터가 들어가게 된다. 반대로 Dequeue
가 이뤄지면 Front + 1
의 인덱스의 데이터를 제거하게 된다.
원형 큐는 Front
와 Rear
의 인덱스가 같으면 큐가 비어있는 것이고, Rear + 1
이 Front
와 같으면 큐가 가득 차있는 것이다.
덱(Deque)
덱은 Double-ended Queue의 약자로 큐의 데이터 삽입, 제거를 양방향 모두에서 가능하도록 구현한 자료구조이다. 앞, 뒤에서 삽입, 제거 연산이 일어나기 때문에 보통 양방향 링크드 리스트로 구현한다.