[자료구조] 큐
스택의경우, 나중에 들어온 데이터가 먼저 나가는 구조인데 반하여 큐(queue)는 먼저 들어온 데이터가 먼저 나가는 구조로 이러한 특성을 선입선출(FIFO: First-In First-Out)이라고 한다. 큐의 예로는 매표소에서 표를 사기 위해 늘어선 줄을 들 수 있겠다. 줄에 있는 사람들 중 가장 앞에 있는 사람(즉 가장 먼저 온 사람)이 가장 먼저 표를 사게 될 것이다. 나중에 온 사람들은 줄의 맨 뒤에 서야 할 것이다.
큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. 구조상으로 큐가 스택과 다른 점은 스택의 경우, 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다는 것이다.
위의 그림과 같이, 큐에서 삽입이 일어나는 곳을 후단(rear)라고 하고 삭제가 일어나는 곳을 전단(front)라고 한다.
객체 : 0개 이상의 요소들로 구성된 선형 리스트
연산 :
create(max_size) ::=
최대 크기가 max_size인 공백큐를 생성한다.
init(q) ::=
큐를 초기화한다.
is_empty(q) ::=
if(size == 0) return TRUE;
else return FALSE;
is_full(q) ::=
if(size == max_size) return TRUE;
else return FALSE;
enqueue(q, e) ::=
if(is_full(q)) queue_full 오류;
else q의 끝에 e를 추가한다.
dequeue(q) ::=
if(is_empty(q)) queue_empty 오류;
else q의 맨 앞에 있는 e를 제거하여 반환한다.
peek(q) ::=
if(is_empty(q)) queue_empty 오류;
else q의 맨 앞에 있는 e를 읽어서 반환한다.
추상 자료형 큐의 연산들은 추상 자료형 스택과 아주 유사하다. is_empty 연산은 큐가 비어있으면 TRUE를 반환하고 그렇지 않으면 FALSE를 반환한다. is_full 연산은 큐가 가득 찼으면 TRUE를, 그렇지 않으면 FALSE를 반환한다.
큐도 스택과 마찬가지로 "프로그래머의 도구"로서 폭넓게 이용된다. 많이 이용되는 분야는 컴퓨터를 이용하여 현실 세계의 실제상황을 시뮬레이션 하는 곳이다.
예를 들면 은행에서 기다리는 사람들의 대기열, 공항에서 이륙하는 비행기들, 인터넷에서 전송되는 데이터 패킷들을 모델링하는데 큐가 이용된다.
큐는 운영 체제에세도 중요하게 사용된다. 보통 컴퓨터와 주변기기 사이에는 항상 큐가 존재한다. 그 이유는 컴퓨터의 CPU와 주변기기 사이에는 속도 차이가 있기 때문에 CPU를 효율적으로 사용하기 위하여 큐가 존재한다.
예를 들면 운영 체제에는 인쇄 작업큐가 존재한다. 프린터는 속도가 늦고 상대적으로 컴퓨터의 CPU는 속도가 빠르기 때문에 CPU는 빠른 속도로 인쇄 데이터를 만든 다음, 인쇄 작업 큐에 저장하고 다른 작업으로 넘어간다. 프린터는 인쇄 작업 큐에서 데이터를 가져다가 인쇄한다.
키보드와 컴퓨터 사이에도 큐가 존재한다. 컴퓨터가 다른 작업을 하고 있더라도 사용자가 키보드를 누르면 키 스트로크 데이터가 큐에 저장된다. 애플리케이션은 시간이 날 때마다 키 스트로크 데이터를 큐에서 가져가게 된다.
큐도 스택과 마찬가지로 배열과 연결 리스트를 이용하여 구현할 수 있다.
선형 큐의 응용: 작업 스케줄링
운영 체제는 많은 작업들을 동시에 실행해야 한다. 만약 CPU가 하나뿐이고 모든 작업들은 우선순위를 가지지 않는다고 가정하면 작업들은 운영 체제에 들어간 순서대로 처리될 것이다. 이럴 때는 큐를 사용하여서 작업들을 처리할 수 있다.
참고
- C언어로 쉽게 풀어쓴 자료구조 책