[Section 3] 큐(Queue)의 종류와 개념 이해하기

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

선형 자료구조는 자료를 순차적으로 구성하였기 때문에 그 정보에 접근하기 위한 알고리즘은 역시 순차적이다. 이러한 선형 자료구조의 종류에는  리스트, 스택 그리고 큐가 존재한다. 만약 연결 리스트의 알고리즘 개념에 기반하여 자료 구조를 이해했다면, 지금 부터는 그 종류와 개념만으로 스스로 구현해 볼 수 있을 것이다. 이번 시간에는 큐(Queue)의 종류와 그 개념을 이해해 보도록 한다.

1.  큐 자료 구조의 이해

연결 리스트, 스택에 이어 큐(Queue) 자료 구조 개념을 이해해보자. 이들은 모두 선형 자료구조로 형태가 매우 유사하다. 큐 개념 또한 스택과 리스트와 다를 바 없다. 다음의 그림을 참고하자.

 

큐(Queue) 구조의 이해

 

얼핏 보기에는 연결 리스트와 비슷한 구조이지만, 후면의(Rear) 포인터가 존재한다. 이는 데이터의 삽입과 삭제가 정해진 구조이다. 예를 들면, 후면으로 데이터가 삽입되고 앞면(Front)으로 데이터가 삭제되는 방식이다. 이는 은행에서 줄을 서는 과정에 비유되기도 한다. 번호표가 데이터 삽입이고 삭제가 번호표의 호출에 비유하자면 가장 먼저 들어온 데이터부터 삭제되는 방식이다.

 

* 이를 영어로 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 리스트라고도 부른다.

 

 

큐 자료 구조는 순서를 유지하는 측면에서 필요한 자료구조이다. 데이터의 삽입과 삭제가 순차적으로 이루어지는 모습은 마치 은행에서 대기표를 뽑아 기다리는 사람과 같다.

 

* 만약에 삽입 혹은 삭제되는 데이터가 비어있으면 언더플로우(underflow)라는 용어를 사용하고, 데이터가 차 있는 상태를 오버 플로우(overflowe)라고 한다. 

 

* 프로그래밍 용도에 따라서 데이터는 삽입과 삭제보다는 인큐(enQueue)와 디큐(DeQueue)라는 용어가 더 적절하다. 데이터가 순차적으로 다른 곳으로 이동하거나 사용되는 용도일 수 도 있으니 말이다.

 

2.  큐 자료 구조의 종류와 ADT _ 단순 원형 배열, 연결 리스트 큐

큐는 배열로 쉽게 구현하는 것이 가능하다. 그리고 배열의 한정적 사이즈 문제는 간단히 원형의 형태로 구현하면 해결될 수 있다. 따라서 배열로 구현한 큐는 단순 원형 배열(Simple Circular Array)이라고 부른다. 그리고 연결 리스트로도 큐를 구현할 수 있는데, 연결 리스트의 헤드 포인트는 앞면(Front) 포인터가 되고 마지막 노드를 가리키는 포인터는 후면(Rear) 포인터가 된다.

 

* 다음의 그림을 참고하자. 

 

단순 원형 배열과 연결 리스트 큐의 구조

* 이 두 종류의 큐는 공간 복잡도 O(n)을 제외하고 모든 ADT 기능의 시간 복잡도가 O(1)이다. 

 

큐의 메인 ADT는 인큐와 디큐로써, 데이터의 삽입과 삭제 기능을 구현할 수 있다. 그리고 보조 ADT는 프로그래밍의 용도에 맞게 사용자가 적절한 기능을 구현할 수 있다.