[알고리즘] 2.2.자료구조 : 큐(Queue) 이해하기

  개요

큐의 구조는 스택과 다르게 '선입선출'의 구조를 가지고 있습니다. 스택은 막힌 박스와 같아 먼저 들어온 것이 가장 나중에 나가는 구조지만, 큐는 먼저 들어온 것이 먼저 나가는 구조입니다. 좋은 예로 은행에 있는 번호표가 있습니다. 은행에 방문하여 기다리는데, 저보다 늦게 온 다른 분이 먼저 업무를 본다면 기분이 나쁘겠죠? 이러한 상황을 만들지 않기 위해 은행에서는 번호표를 나눠줍니다. 먼저 온 손님은 늦게 온 손님보다 먼저 서비스를 받게 하기 위해서죠. 이러한 은행의 번호표의 체계가 큐(Queue)입니다. 

은행의 번호표를 다시 한번 생각해보죠. 제가 619번의 번호표를 뽑았다고 가정하여 봅시다. 지금은 618번 까지 서비스를 받고 있는 상태이고요. 그러면 번호표 시스템 내부에서는 다음 서비스를 받을 번호를 어떻게 기억을 해야 할까요? 그리고 가장 나중에 온 손님이 번호표를 뽑았을 때 몇 번의 번호표를 줘야할지 어떻게 기억할까요? 번호표 기계도 프로그래밍으로 구현된 하나의 프로그램인데, 1번부터 확인하면서 이 손님이 서비스를 받았는지 안받았는지 확인하며 다음으로 호출할 번호를 정할까요? 이러면 너무 비효율적입니다. 단순하게 생각하면 서비스를 받을 처음 위치와 마지막의 위치만 기억하면 모든게 쉽게 풀립니다. 이 위치들을 큐(Queue)에서는 front, rear라고 하죠. 

위 그림을 보면 Deletion, Insertion이라는 용어가 있습니다. 이 용어보다는 많은 사람들이 Dequeue, Enqueue라는 용어를 사용합니다. Enqueue는 위 그림에서 Insertion과 같습니다. 마지막으로 온 손님에게 번호표를 주는 것이죠. 그럼 Dequeue는 서비스를 받은 번호표는 대기목록에서 지우는 것입니다. 그래야 다음으로 호출할 번호를 알 수가 있죠. 

정리를 해보면

(1) Enqueue : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표 발부

(2) Dequeue : 큐 맨 앞쪽의 요소를 삭제, 창구에서 서비스를 받은 손님의 번호표를 대기목록에서 삭제

(3) Peek : front에 위치한 데이터를 읽음, 다음 서비스를 받을 손님이 누구인지 확인

(4) front : 큐의 맨 앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호

(5) rear : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호

  구현에 앞서

스택과 마찬가지로 배열과 연결리스트를 이용하여 구현할 수 있습니다. 배열과 연결리스트 모두 장단점이 존재하기 때문에, 그 상황에 맞게 사용할 자료구조를 정하면 됩니다. 우선 배열과 연결리스트로 큐(Queue)를 구현 할 건데, 구현을 하면서 치명적인 문제점을 발견하게 될 것입니다. 이 문제점을 해결하기 위해 원형-큐(Circular Queue)가 있는데 이는 다음에 정리하도록 하겠습니다. 

  구현

2017/02/16 - [Programming/Algorithm] - [알고리즘] 2.2.자료구조 : 배열을 이용한 큐(Queue) 구현

2017/02/16 - [Programming/Algorithm] - [알고리즘] 2.2.자료구조 : 연결리스트를 이용한 큐(Queue) 구현