큐 (자료 구조)
| 큐 | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
 선입 선출 큐의 표현 | ||||||||||||||||||||||||
| ||||||||||||||||||||||||
컴퓨터 과학에서 큐(queue)는 엔티티의 정렬된 컬렉션 역할을 하는 추상 자료형이다. 관례적으로 요소가 추가되는 큐의 끝을 큐의 뒤, 꼬리 또는 후단이라고 한다. 요소가 제거되는 큐의 끝을 큐의 머리 또는 전단이라고 한다. 큐라는 이름은 상품이나 서비스를 기다리기 위해 줄 서 있는 사람들을 묘사하는 단어에 대한 유추이다. 큐는 두 가지 주요 연산을 지원한다.
- 인큐(Enqueue): 큐의 후단에 요소를 하나 추가한다.
- 디큐(Dequeue): 큐의 전단에서 요소를 하나 제거한다.
다른 연산도 허용될 수 있으며, 종종 다음 디큐될 요소의 값을 디큐하지 않고 반환하는 피크(peek) 또는 전단 연산이 포함된다.
큐의 연산은 큐에 추가된 첫 번째 요소가 첫 번째로 제거되기 때문에 선입 선출 (FIFO) 자료 구조가 된다. 이는 새 요소가 추가되면, 이 새 요소를 제거하기 전에 이전에 추가된 모든 요소를 제거해야 한다는 요구 사항과 동일하다. 큐는 선형 자료 구조의 한 예이며, 더 추상적으로는 순차 컬렉션이다. 큐는 컴퓨터 프로그램에서 일반적이며, 접근 루틴과 결합된 자료 구조로 구현되거나, 추상 자료 구조로 또는 객체 지향 언어에서 클래스로 구현된다. 큐는 원형 버퍼 및 연결 리스트로 구현되거나, 스택 포인터와 베이스 포인터를 모두 사용하여 구현될 수 있다.
큐는 컴퓨터 과학, 교통, 운용과학 분야에서 데이터, 객체, 사람 또는 이벤트와 같은 다양한 엔티티가 저장되고 나중에 처리될 수 있도록 보관되는 서비스를 제공한다. 이러한 맥락에서 큐는 버퍼 기능을 수행한다. 큐의 또 다른 사용법은 너비 우선 탐색 구현에 있다.
큐 구현
[편집]이론적으로 큐의 한 가지 특징은 특정 용량을 가지고 있지 않다는 것이다. 이미 포함된 요소의 수에 관계없이 항상 새 요소를 추가할 수 있다. 또한 비어 있을 수도 있으며, 이 시점에서는 새 요소가 다시 추가될 때까지 요소를 제거하는 것이 불가능하다.
고정 길이 배열은 용량이 제한적이지만, 항목을 큐의 머리 쪽으로 복사해야 하는 것은 아니다. 배열을 닫힌 원형으로 만들고 머리와 꼬리가 그 원형 안에서 끝없이 움직이게 하는 간단한 트릭은 배열에 저장된 항목을 이동할 필요가 없게 만든다. 이 배열의 크기라면, 으로 나눈 나머지를 인덱스로 계산하면 배열이 원형이 된다. 이는 여전히 고급 언어에서 큐를 구성하는 개념적으로 가장 간단한 방법이지만, 배열 인덱스를 0과 배열 크기와 비교해야 하므로 약간 속도가 느려진다. 이는 일부 언어에서 배열 인덱스가 범위를 벗어났는지 확인하는 데 걸리는 시간과 비슷하지만, 포인터 구문이 없는 빠르고 간단한 구현이나 모든 고급 언어에 있어서는 확실히 선택될 방법일 것이다. 배열 크기는 미리 선언되어야 하지만, 일부 구현에서는 오버플로가 발생할 때 선언된 배열 크기를 단순히 두 배로 늘린다. 객체 또는 포인터를 사용하는 대부분의 현대 언어는 동적 리스트를 구현하거나 해당 라이브러리를 제공한다. 이러한 자료 구조는 메모리 제약 외에는 고정된 용량 제한을 지정하지 않을 수도 있다. 큐 오버플로는 가득 찬 큐에 요소를 추가하려 할 때 발생하며, 큐 언더플로는 비어 있는 큐에서 요소를 제거하려 할 때 발생한다.
유계 큐(bounded queue)는 고정된 수의 항목으로 제한된 큐이다.[1]
FIFO 큐에는 몇 가지 효율적인 구현 방법이 있다. 효율적인 구현이란 큐에 넣기(en-queuing) 및 큐에서 빼기(de-queuing) 작업을 O(1) 시간에 수행할 수 있는 것을 말한다.
- 연결 리스트
- 이중 연결 리스트는 양쪽 끝에서 O(1) 삽입 및 삭제가 가능하므로 큐에 적합하다.
- 일반 단일 연결 리스트는 한쪽 끝에서만 효율적인 삽입 및 삭제가 가능하다. 그러나 작은 수정—첫 번째 노드 외에 마지막 노드에 대한 포인터를 유지하는 것—을 통해 효율적인 큐를 구현할 수 있다.
- 수정된 동적 배열을 사용하여 구현된 덱
큐와 프로그래밍 언어
[편집]큐는 별도의 자료형으로 구현되거나, 덱 (자료 구조)의 특별한 경우로 간주되어 별도로 구현되지 않을 수도 있다. 예를 들어, 펄과 루비는 배열의 양쪽 끝에서 푸시와 팝을 허용하므로, push 및 shift 함수를 사용하여 리스트에 요소를 넣고(enqueue) 빼낼 수 있다(또는 반대로 unshift와 pop을 사용할 수 있다).[2] 그러나 어떤 경우에는 이러한 작업이 효율적이지 않을 수 있다.
C++의 표준 템플릿 라이브러리는 푸시/팝 작업으로만 제한되는 "queue" 템플릿 클래스를 제공한다. J2SE 5.0부터 자바 라이브러리에는 큐 작업을 지정하는 Queue 인터페이스가 포함되어 있다. 구현 클래스에는 LinkedList와 (J2SE 1.6부터) ArrayDeque가 있다. PHP에는 SplQueue 클래스와 beanstalk'd 및 Gearman과 같은 서드파티 라이브러리가 있다.
예시
[편집]타입스크립트로 구현된 단순 큐:
class Queue<T> {
private items: T[] = [];
enqueue(element: T): void {
this.items.push(element);
}
dequeue(): T | undefined {
return this.items.shift();
}
isEmpty(): boolean {
return this.items.length === 0;
}
}
순수 함수형 구현
[편집]큐는 순수 함수형 자료 구조로도 구현될 수 있다.[3] 두 가지 구현 방식이 있다. 첫 번째는 평균적으로 연산만을 달성한다. 즉, 분할 상환 시간은 이지만, 개별 연산은 큐의 요소 수 에 대해 이 걸릴 수 있다. 두 번째 구현은 실시간 큐라고 불리며[4] 큐를 영속 자료 구조로 만들고 최악의 경우 O(1) 시간에 연산을 수행한다. 이는 더 복잡한 구현이며 느긋한 계산법과 메모이제이션을 사용하는 지연 목록이 필요하다.
분할 상환 큐
[편집]이 큐의 데이터는 와 이라는 두 개의 단일 연결 리스트에 저장된다. 리스트 는 큐의 앞부분을 담고 있다. 리스트 은 나머지 요소(큐의 뒷부분)를 역순으로 담고 있다. 의 머리에 노드를 추가하여 큐의 앞에 삽입하는 것은 쉽다. 그리고 이 비어있지 않으면, 의 머리에 있는 노드를 제거하여 큐의 끝에서 제거하는 것은 쉽다. 이 비어있을 때, 리스트는 역순으로 바뀌어 에 할당된 후 의 머리가 제거된다.
삽입 ("인큐")은 항상 시간이 걸린다. 제거 ("디큐")는 리스트가 비어있지 않을 때 시간이 걸린다. 이 비어있을 때, 역순으로 만드는 데는 에 있는 요소 수 에 대해 이 걸린다. 하지만, 이는 분할 상환 시간이라고 말할 수 있는데, 의 모든 요소는 삽입되어야 했고, 역순으로 각 요소에 대해 삽입되었을 때 상수 비용을 할당할 수 있기 때문이다.
실시간 큐
[편집]실시간 큐는 분할 상환 없이 모든 연산에 대해 시간을 달성한다. 이 논의는 기술적이므로, 리스트 에 대해 은 그 길이를 나타내고, NIL은 빈 리스트를 나타내며, 는 머리가 h이고 꼬리가 t인 리스트를 나타낸다는 것을 상기하자.
큐를 구현하는 데 사용되는 자료 구조는 세 개의 단일 연결 리스트 로 구성된다. 여기서 f는 큐의 앞부분이고 r은 큐의 뒷부분(역순)이다. 구조의 불변성은 s가 f의 뒷부분에서 첫 개의 요소를 제외한 것이라는 점, 즉 이다. 큐 의 꼬리는 거의 이고, 에 요소 x를 삽입하는 것은 거의 이다. 거의라고 말하는 이유는 이 두 결과 모두에서 이기 때문이다. 따라서 불변성을 만족시키기 위해 보조 함수 를 호출해야 한다. 가 빈 리스트인 경우, 즉 인 경우와 그렇지 않은 경우의 두 가지를 고려해야 한다. 형식적인 정의는 이고 이다. 여기서 은 f 다음에 r이 역순으로 붙은 것이다.
를 f 뒤에 r을 뒤집은 것을 반환하는 함수라고 부르자. 또한 이라고 가정하는데, 이 함수가 호출될 때 그러한 경우이기 때문이다. 더 정확하게는, 인 세 개의 리스트를 입력으로 받아 f, 뒤집힌 r, 그리고 a의 연결을 반환하는 느긋한 함수 를 정의한다. 그러면 이다. rotate의 귀납적 정의는 이며 이다. 실행 시간은 이지만, 느긋한 계산법이 사용되므로, 계산은 결과가 계산에 의해 강제될 때까지 지연된다.
자료 구조의 리스트 s는 두 가지 목적을 가지고 있다. 이 리스트는 의 카운터 역할을 하는데, 실제로 s가 빈 리스트일 때만 이다. 이 카운터는 후면이 전면 리스트보다 길어지지 않도록 보장한다. 또한 f의 꼬리인 s를 사용하면 각 꼬리 및 삽입 작업 동안 (느긋한) 리스트 f의 일부 계산이 강제된다. 따라서 일 때 리스트 f는 완전히 강제된다. 그렇지 않다면 f의 내부 표현은 append of append of... of append가 될 수 있었고, 강제화는 더 이상 상수 시간 연산이 아닐 것이다.
같이 보기
[편집]각주
[편집]- ↑ “Queue (Java Platform SE 7)”. Docs.oracle.com. 2014년 3월 26일. 2014년 5월 22일에 확인함.
- ↑ “Class Array”.
- ↑ Okasaki, Chris. “Purely Functional Data Structures” (PDF).
- ↑ Hood, Robert; Melville, Robert (November 1981). 《Real-time queue operations in pure Lisp》. 《Information Processing Letters》 13. 50–54쪽. doi:10.1016/0020-0190(81)90030-2. hdl:1813/6273.