큐(추상 데이터 유형)

이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다.(2014년 1월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

FIFO(선입선출) 큐 표현

컴퓨터 과학에서 큐는 시퀀스로 유지되는 엔티티의 집합으로 시퀀스의 한쪽 끝에 엔티티를 추가하고 시퀀스의 다른 끝에서 엔티티를 제거함으로써 변경할 수 있습니다.일반적으로 요소가 추가되는 순서의 끝을 큐의 뒷면, 꼬리 또는 뒷면이라고 하며, 요소가 제거되는 끝을 큐의 선두 또는 앞면이라고 합니다.이는 사람들이 상품이나 서비스를 기다리기 위해 줄을 설 때 사용되는 단어와 유사합니다.

큐의 후면에 요소를 추가하는 동작을 enqueue라고 하며, 전면에서 요소를 제거하는 동작을 dequeue라고 합니다.큐를 해제하지 않고 큐를 해제할 다음 요소의 값을 반환하는 피크 또는 전면 작업을 포함하는 다른 작업도 허용될 수 있습니다.

큐의 연산은 First-In-First-Out(FIFO; 선입선출) 데이터 구조입니다.FIFO 데이터 구조에서는 큐에 추가된 첫 번째 요소가 가장 먼저 삭제됩니다.이는 새 요소를 추가한 후에는 이전에 추가한 모든 요소를 삭제해야 새 요소를 제거할 수 있다는 요구 사항과 동일합니다.큐는 선형 데이터 구조, 더 추상적으로 순차 집합의 예입니다.큐는 액세스 루틴과 결합된 데이터 구조, 추상 데이터 구조 또는 클래스로 객체 지향 언어에서 구현되는 컴퓨터 프로그램에서 일반적입니다.일반적인 실장은 순환 버퍼와 링크 리스트입니다.

큐는 데이터, 객체, 인물 또는 이벤트와 같은 다양한 엔티티가 저장되고 나중에 처리될 수 있도록 보관되는 컴퓨터 과학, 전송 및 운영 연구 서비스를 제공합니다.이러한 컨텍스트에서 큐는 버퍼 기능을 수행합니다.큐의 또 다른 용도는 폭 우선 검색 구현입니다.

큐의 실장

이론적으로 큐의 특징 중 하나는 특정 용량이 없다는 것입니다.이미 포함된 요소의 수에 관계없이 항상 새 요소를 추가할 수 있습니다.또한 비어 있을 수도 있습니다. 이 경우 새 요소가 다시 추가될 때까지 요소를 제거할 수 없습니다.

고정 길이 배열은 용량이 제한되지만 항목을 대기열 선두로 복사해야 하는 것은 사실이 아닙니다.어레이를 닫힌 원으로 만들고, 그 원 안에서 머리와 꼬리를 끝없이 떠다니게 하는 간단한 트릭으로 어레이에 저장된 아이템을 이동할 필요가 없습니다.n이 배열 크기일 경우 인덱스 모듈 n을 계산하면 배열이 원으로 바뀝니다.이는 여전히 개념적으로 가장 간단한 방법으로 큐를 고급 언어로 구성하는 방법이지만, 어레이 인덱스를 0 및 어레이 크기와 비교해야 하기 때문에 약간 속도가 느려집니다.이는 어레이 인덱스가 경계를 벗어나 있는지 확인하는 데 걸리는 시간과 비슷하기 때문입니다.단, 일부 언어에서는 마찬가지입니다.빠르고 지저분한 구현 또는 포인터 구문이 없는 고급 언어에서 선택하는 방법입니다.어레이 크기는 미리 선언해야 하지만 일부 구현에서는 오버플로가 발생할 때 선언된 어레이 크기를 두 배로 늘립니다.객체 또는 포인터가 있는 대부분의 현대 언어들은 동적 목록용 라이브러리를 구현하거나 함께 제공합니다.이러한 데이터 구조는 메모리 제약 외에 고정된 용량 제한을 지정하지 않았을 수 있습니다.큐 오버플로는 요소를 풀큐에 추가하려고 하면 발생하고 큐 언더플로우는 빈 큐에서 요소를 삭제하려고 하면 발생합니다.

경계 큐는 고정된 ^[1]개수의 항목으로 제한된 큐입니다.

FIFO 큐에는 몇 가지 효율적인 구현이 있습니다.효율적인 구현은 O(1) 시간 내에 큐잉 및 큐잉 해제 작업을 수행할 수 있는 구현입니다.

• 링크 리스트
  • 이중 링크 리스트는 양 끝에 O(1) 삽입 및 삭제가 있기 때문에 큐에서는 자연스러운 선택입니다.
  • 일반적인 단일 링크 리스트는 한쪽 끝에만 효율적으로 삽입 및 삭제할 수 있습니다.단, 첫 번째 노드 외에 마지막 노드에 대한 포인터를 유지하는 작은 변경으로 효율적인 큐를 구현할 수 있습니다.
• 수정된 동적 어레이를 사용하여 구현된 디큐

큐 및 프로그래밍 언어

큐는 개별 데이터 타입으로 실장할 수도 있고 더블 엔드 큐(deque)의 특수한 경우로 간주할 수도 있으며 개별적으로 실장할 수도 없습니다.예를 들어 Perl과 Ruby는 양쪽 끝에서 배열을 푸시 및 팝할 수 있으므로 푸시 및 시프트 기능을 사용하여 목록을 큐잉 및 디큐잉할 수 있습니다(또는 반대로 unshift 및 ^[2]팝을 사용할 수 있습니다).단, 이러한 조작이 효율적이지 않은 경우도 있습니다.

C++의 표준 템플릿 라이브러리는 "queue"템플릿 클래스는 푸시/팝 조작으로만 제한됩니다.J2SE5.0 이후 Java 라이브러리에는Queue큐 동작을 지정하는 인터페이스.클래스의 실장에는, 다음과 같은 것이 포함됩니다.LinkedList및 (J2SE 1.6 이후)ArrayDequePHP는 SplQueue 클래스와 beanstalk'd 및 Gearman과 같은 서드파티 라이브러리를 가지고 있습니다.

예

JavaScript에 구현된 단순 큐:

학급 큐 {     컨스트럭터() {         이것..항목들 = [];     }      큐잉(요소) {         이것..항목들.밀다(요소);     }      큐잉을 해제하다() {         돌아가다 이것..항목들.교대하다();     } } 

순수하게 기능하는 구현

큐는 순수하게 기능하는 데이터 ^[3]구조로도 구현할 수 있습니다.두 가지 구현이 있습니다.첫 번째는 동작당 평균${\displaystyle }$O($)$ {$displaystyle O$(1$)}$만 달성합니다.즉, 상각시간은 ${\displaystyle \mathrm{O}(}$1$)\displaystyle$O(1)이지만 개별$$조작은 $)\displaystyle$ O$(n)$를 취할 수 있습니다.여기서 n은 큐 내의 요소 수입니다.두 번째 실장은 실시간큐라고^[4] 불리며, O(1) 최악의 경우에 큐를 조작으로 영속적으로 유지할 수 있습니다.이 방법은 구현이 더 복잡하기 때문에 메모가 있는 느린 목록이 필요합니다.

상각 큐

이 큐의 데이터는 f$${\$displaystyle$$f$} 및 r {\$displaystyle$ r$\}$이라는 이름의 2개의 단일 링크 목록에 저장됩니다.$목록{\displaystyle }$ f$\displaystyle$f에는$$ 큐의 앞부분이 포함됩니다.$목록{\displaystyle }$ r$\displaystyle$r은$$ 나머지 요소(큐의 후면)를 역순으로 유지합니다.$f\displaystyle$$$f의$$$선두$에 노드를 추가하면 큐의 선두에 쉽게 삽입할 수 있습니다$.또한$ r\$displaystyle$ r이 비어$$ 있지 $않은{\displaystyle }$$경우{\displaystyle }$ $r$$\$$displaystyle$r의 선두에 있는 노드를 삭제하면 큐의 끝에서 쉽게 삭제할 수 있습니다$.$$r$\$displaystyle$ r이$$ 비어 있는 $경우{\displaystyle }$ $list{\displaystyle }$ f$\$displaystyle은$f}$가 반전되어 r$\displaystyle$에 할당되고 r$\displaystyle$의 헤드가 삭제됩니다.

삽입("enqueue")에는 항상 O${\displaystyle (}$1$)\displaystyle$O($1)$ 시간이$$ $걸립니다{\displaystyle }$.$목록{\displaystyle }$ r$\displaystyle$r이$$ 비어 있지 않은 경우 제거("dequeue")에 O${\displaystyle }$($)$ {$displaystyle$O(1)가 사용됩니다$$.r$${\$displaystyle$ r$}$이(가) 비어 있는 $경우{\displaystyle }$, 그 반대가 O$)$ {$displaystyle$ O$(n)}$가 $됩니다{\displaystyle }$.$여기$서$$n {$displaystyle$ n$}$은$$f {\$displaystyle$ f$}$의 $요소$ 개수입니다.단$,$ 상각된 시간은 O${\displaystyle (}$ ${\displaystyle 1}$)$${$displaystyle$$$O($1)$이라고 할 수 있습니다.각 요소를 삽입할 때 각 요소에 대해 일정한 비용을 할당합니다.

실시간 큐

실시간 큐는 상각 없이 모든 작업에 대해 O${\displaystyle }$( ${\displaystyle 1}$)$${$displaystyle$ O$$ (1$)} 시간$을 $달성$합니다.$이$ 설명은 기술적인 것이므로 $목록$에서는 $displaystyle$$$l은$$그$$ 길이를 나타내고, CONS${\displaystyle }$(${\displaystyle }$( h ${\displaystyle ,}$ t $)$는 빈 목록을 ${\displaystyle \mathrm{나타내며}}$, $CONS$( ($$ , t $)$는 헤드가 h이고 꼬리가 t인 목록을 나타냅니다$$.

큐 구현에 사용되는 데이터 구조는 3개의 단일 링크 리스트$({\displaystyle f,r}$ ,${\displaystyle s}$)({$displaystyle (f, r, s$)})로$$ 구성됩니다.여기서 f는 큐의 앞부분, r은 큐의 뒷부분입니다.이 구조의 불변성은 s가 r$displaystyle$ r$)$의 첫 번째 요소가 없는 f의 후면, ${\displaystyle 즉}$ s ${\displaystyle =f}$ -${\displaystyle }{\displaystyle r}$(\$displaystyle$ s $= f$ - r $\}$ 입니다$.{\displaystyle }$큐의 꼬리(${\displaystyle \mathrm{CONS}}$ ${\displaystyle (}$ (${\displaystyle x}$ ,$f$) ,${\displaystyle r}$ ,${\displaystyle s}$){ $display$( \ $operatorname${ CONS $}$ ( $x$, $f$, s ) , s ) $、$ s )는${\displaystyle \mathrm{거의}}$ f , s , r ${\displaystyle ,}$ r , s )입니다.$isplaystyle (f,r,s)$ 및$$ 요소${\displaystyle x}$를${\displaystyle }$(${\displaystyle f,}$r,s$)$에${\displaystyle }$삽입하는 것은 ($,$r${\displaystyle ,}$$s$${\displaystyle )}$ {$displaystyle$${\displaystyle }$($,$$,$s$)\}$에 거의 (f$,\operatorname {CONS}$ ($x,r,s$)}입니다${\displaystyle .이}$ 두 결과 모두 s -$$ style에 거의 ${\displaystyle 일치}$합니다.그런 다음$$를 만족시키려면 보조 $함수{\displaystyle }$ u x {\$displaystyle$ ${\displaystyle \mathrm{aux}}$$}$s$${\$displaystyle$ s$}$가 빈 목록인지 $여부$에 따라 두 가지 경우를 ${\displaystyle 고려}$해야 합니다. 이 ${\displaystyle 경우}$ r${\displaystyle }$= ${\displaystyle \mathrm{f}}$ + 1 {\$displaystyle$ r $= f$ +$1$ 또는 그렇지 않습니다.정식 정의는 aux "${\displaystyle }$(${\displaystyle f}$ ,${\displaystyle r}$ , ${\displaystyle \mathrm{Cons}}$" (${\displaystyle \mathrm{\_}}$ ,${\displaystyle s}$) ${\displaystyle =}$ (${\displaystyle f}$ ,${\displaystyle r}$ ,${\displaystyle s}$ )$$\ $displaystyle \operatorname { aux$} ($f , r$ , s )$=$ ($f$ ,$r$ ,$$${\displaystyle \text{s}}$ )${\displaystyle \mathrm{및<img\; alt="\{\backslash displaystyle\; \backslash operatorname\; \{aux\}\; (f,r,\backslash operatorname\; \{Cons\}\; (\backslash \_,s))=(f,r,s)\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/7422e0514cb6e65ce380bb4d160bd96b3aefe8f6"\; style="vertical-align:\; -0.838ex;\; width:30.426ex;\; height:2.843ex;">}}$ aux${\displaystyle }$" ( f ,${\displaystyle r}$ ,${\displaystyle }$NIL )${\displaystyle =}$ (${\displaystyle f}$ , r , nil )입니다${\displaystyle {.}^{}}$$NIL})=(f', {\text{)$$NIL}}},$f$$$'}.$ $여기$서 f$${\(\$displaystyle$ f$')$ 뒤에 r이 반전됩니다.

f를 반환하고 r을 반환하는 함수 f${\displaystyle ,}$r$displaystyle \operatorname {reverse}(f,r))$를 reverse로 ${\displaystyle \mathrm{호출}}$합니다.또한 이 함수가 호출될 때 ${\displaystyle r}$ ${\displaystyle =}$ ${\displaystyle \mathrm{f}}$ +$$1$(\backslash$$displaystyle$ r $= f$ +$1$)이라고 가정합니다.$보다$ 정확하게는 r ${\displaystyle =f}$ +$$ (\$displaystyle$$$r $= f$ +$1$과 같이 입력 3개의 목록으로 받아들여 f, r의 반전 및 a의 연계를 반환하는 느린 ${\displaystyle \mathrm{함수}}$ 회전$$δ ($f$,$r$,${\displaystyle a}$ $)$를 정의합니다$$.${\displaystyle \mathrm{그런}}$ 다음 역방향 ${\displaystyle (}$( ${\displaystyle f}$, r ) $=$ ${\displaystyle \mathrm{회전}(}$( ${\displaystyle f}$ ,${\displaystyle \text{r}}$ ,${\displaystyle }$NIL$$){ displaystyle \$operatorname { display$} ($f$ , r )=\$operatorname { display$} ($f$ ,$r$ , { \ $text$} )$NIL$회전의 유도 정의는 회전 ${\displaystyle }$ (${\displaystyle \text{NIL}}$ , ${\displaystyle \mathrm{Cons}}$ ${\displaystyle (}$ (${\displaystyle y}$ ,${\displaystyle \text{NIL}}$) ,${\displaystyle }$a ) ${\displaystyle =}$ ${\displaystyle \mathrm{단점}}$ ${\displaystyle }$ (${\displaystyle y}$ ,${\displaystyle a}$) { $displaystyle \operatorname$ {$}$ ( \ $text$ {$$} )입니다.$NIL}},\operatorname {Cons}(y,{\text{)$$NIL}}), a)$${\displaystyle =}$\$operatorname {Cons}(y,$a$$)} 및 ${\displaystyle \mathrm{회전}\mathrm{cons}}$(${\displaystyle \mathrm{CONS}}$ ${\displaystyle }$(${\displaystyle x}$, ${\displaystyle f}$ ), ${\displaystyle \mathrm{CONS},}$(${\displaystyle }$y${\displaystyle }$, ${\displaystyle r}$ ${\displaystyle ),}$ a )= ${\displaystyle \mathrm{회전}}$ ( ${\displaystyle x}$, ${\displaystyle r}$, ${\displaystyle \mathrm{CONS}}$⁡ ( ${\displaystyle f}$,${\displaystyle r}$ $),$ cons ） { $displaystyle \operatorname {cons$} ( \$opername$ {cons$})$$time$은 O${\displaystyle }$(${\displaystyle r}$) { $displaystyle$O ($r$ )$$。단, 느린 평가가 사용되므로 계산에 의해 결과가 강제될 때까지 계산이 지연됩니다.

데이터 구조 내의 목록에는 두 가지 목적이 있습니다.이 목록은 f${\displaystyle }$-$r의 카운터$ ${\displaystyle 역할}$을 합니다. 실제로 s가 빈 목록인 경우에만 f ${\displaystyle =}$r {$displaystyle$ f$$$=$r$}$입니다$.$이 카운터를 사용하면 후면이 전면 목록보다 길지 않도록 할 수 있습니다.또한 f의 꼬리인 s를 사용하면 각 tail 및 insert 조작 중에 (lazy) list f의 일부를 강제로 계산한다.따라서 f ${\displaystyle =}{\displaystyle r}$ { $displaystyle$ f =$$r $\}$일 경우 목록 f는 완전히 강제됩니다.그렇지 않은 경우 f의 내부 표현은 ...의 부록이 될 수 있다.더 이상 고정 시간 작업이 아닐 것입니다.

「 」를 참조해 주세요.

• 순환 버퍼
• 더블 엔드 큐(디큐)
• priority 큐
• 큐잉 이론
• 스택(추상 데이터 유형)– 큐의 "반대": LIFO(Last In First Out)

레퍼런스

일반 참고 자료

• 이 문서에는 NIST 문서의 퍼블릭 도메인 자료가 포함되어 있습니다.

추가 정보

• 도널드 크누트.The Art of Computer Programming, Volume 1: Fundamental Algorithms, 제3판.애디슨 웨슬리, 1997년ISBN 0-201-89683-4.섹션 2.2.1: 스택, 큐, 디큐, 페이지 238–243.
• 토마스 H. 코먼, 찰스 E. 리저슨, 로널드 L. 리베스트, 클리포드 스타인.알고리즘 소개, 제2판MIT Press and McGraw-Hill, 2001.ISBN 0-262-03293-7.섹션 10.1: 스택 및 큐, 페이지 200–204.
• 윌리엄 포드, 윌리엄 탑데이터 구조(C++ 및 STL, Second Edition 포함)프렌티스 홀, 2002년ISBN 0-13-085850-1.8장: 큐와 우선순위 큐, 페이지 386–390.
• 아담 드로즈덱.데이터 구조 및 알고리즘(C++, 제3판).Thomson Course Technology, 2005.ISBN 0-534-49182-0.4장: 스택 및 큐, 페이지 137–169.

외부 링크

Wikimedia Commons에는 큐 데이터 구조와 관련된 미디어가 있습니다.

• STL 퀵레퍼런스
• 스택, 큐, 디큐 및 Red-Black Tree의 VBScript 구현