thumnail_optimized.png

큐(Queue)

queue_optimized.png

큐는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 **FIFO(First In First Out)**구조로 데이터를 저장한다. 쉽게 이야기 하면 은행에서 번호표를 뽑을 때 가장 먼저 번호표를 뽑은 사람이 번호표를 늦게 뽑은 사람보다 빠르게 업무를 볼 수 있는 것처럼 생각하면 된다.

큐는 가장 일찍 추가된 데이터를 Front, 마지막에 추가된 데이터를 Rear라고 한다. 그리고 큐에 Enqueue를 통해 데이터를 하나씩 추가를 할 때마다 Rear가 입력된 데이터로 변경이 되고, Dequeue를 통해 큐의 데이터를 하나씩 제거해 나가면 기존의 Front는 제거되고 가장 앞에 있는 데이터가 Front가 된다.

정리를 해보면 다음과 같다.

  • Front: 큐 자료구조에서 가장 앞에 있는 데이터 (가장 일찍 추가된 데이터)
  • Rear: 큐 자료구조에서 가장 뒤에 있는 데이터 (가장 나중에 추가된 데이터)
  • Enqueue: 큐 자료구조 맨 뒤에 새로운 데이터를 추가
  • Dequeue: 큐 자료구조 맨 앞에있는 데이터를 제거

큐는 배열로도 구현할 수 있고 링크드 리스트로도 구현을 할 수 있는데 배열로 구현할 경우 치명적인 단점이 생긴다. 데이터를 추가하거나 제거할 때마다 데이터가 들어가있는 인덱스를 모두 수정해야 하기 때문에 자료구조의 크기가 클수록 효율성이 떨어지게 된다. 그래서 배열로 큐를 구현할때는 원형 큐로 구현한다.

원형 큐(Circle Queue)

circle_queue_optimized.png

큐를 배열로 구현하면 다음과 같이 정해진 길이의 큐를 원형으로 구현하게 된다. 원형큐의 RearFront0인덱스에서 부터 시작하며 Enqueue가 이뤄지면 Rear + 1의 인덱스에 데이터가 들어가게 된다. 반대로 Dequeue가 이뤄지면 Front + 1의 인덱스의 데이터를 제거하게 된다.

원형 큐는 FrontRear의 인덱스가 같으면 큐가 비어있는 것이고, Rear + 1Front와 같으면 큐가 가득 차있는 것이다.

덱(Deque)

deque_optimized.png

덱은 Double-ended Queue의 약자로 큐의 데이터 삽입, 제거를 양방향 모두에서 가능하도록 구현한 자료구조이다. 앞, 뒤에서 삽입, 제거 연산이 일어나기 때문에 보통 양방향 링크드 리스트로 구현한다.