이 문서는 Google Cloud Translation API를 사용해 자동 번역되었습니다.
어떤 문서는 원문을 읽는게 나을 수도 있습니다.
양단 큐라고도 하는 양단 큐는 스택 또는 큐와 유사한 순서가 지정된 항목 모음입니다. Deques는 스택과 대기열의 일반화입니다(이름은 "deck"으로 발음되며 "double-ended queue"의 줄임말임).
Deques는 일정한 시간에 데이터 구조의 양쪽 끝에서 항목을 추가하고 제거하는 것을 지원합니다. 반대로 큐와 스택은 항목을 추가하거나 제거하는 데 선형 시간이 필요합니다.
deque는 동적 배열 또는 연결 목록으로 구현할 수 있습니다.
동적 배열은 최대 항목 수를 미리 알고 있는 경우 deque에 적합합니다. 배열은 필요에 따라 크기를 조정할 수 있습니다.
동적 배열로 deque를 구현하기 위해 원형 배열을 사용할 수 있습니다. 이를 통해 deque에서 항목을 추가하거나 제거할 때 요소를 이동할 필요가 없습니다.
전면 및 후면 인덱스는 두 개의 변수로 추적할 수 있습니다. 앞쪽 인덱스는 deque의 첫 번째 요소 인덱스를 나타내고 뒤쪽 인덱스는 deque의 마지막 요소 인덱스를 나타냅니다.
deque 앞에 요소를 추가하려면 앞 인덱스를 줄이고 해당 인덱스에 요소를 삽입합니다. 앞 인덱스가 0보다 작으면 배열의 끝까지 래핑합니다.
deque 뒤에 요소를 추가하려면 뒤 인덱스를 증가시키고 해당 인덱스에 요소를 삽입합니다. 후면 인덱스가 배열의 크기와 같으면 배열의 시작 부분으로 돌아갑니다.
deque 앞의 요소를 제거하려면 앞 인덱스에서 요소를 제거하기만 하면 됩니다. deque의 뒤쪽에서 요소를 제거하려면 뒤쪽 인덱스에서 요소를 제거합니다.
최대 항목 수를 미리 알 수 없는 경우 연결 목록은 deque에 적합합니다.
연결 목록으로 deque를 구현하려면 이중 연결 목록을 사용할 수 있습니다. 이를 통해 일정한 시간에 deque의 양쪽 끝에서 항목을 추가하고 제거할 수 있습니다.
전면 및 후면 포인터는 두 개의 변수로 추적할 수 있습니다. 앞쪽 포인터는 deque의 첫 번째 노드를 나타내고 뒤쪽 포인터는 deque의 마지막 노드를 나타냅니다.
deque 앞에 요소를 추가하려면 목록 앞에 요소를 삽입하기만 하면 됩니다. deque 뒤에 요소를 추가하려면 목록 뒤에 요소를 삽입합니다.
deque 앞의 요소를 제거하려면 목록 앞의 요소를 제거하기만 하면 됩니다. deque 뒤의 요소를 제거하려면 목록 뒤의 요소를 제거합니다.
Deques에는 많은 응용 프로그램이 있습니다. 보다 일반적인 응용 프로그램 중 일부는 아래에 설명되어 있습니다.
큐는 항목을 한쪽 끝에 추가하고 다른 쪽 끝에서 제거할 수 있는 데이터 구조입니다. 대기열은 종종 FIFO(First-In, First-Out) 데이터 구조라고 합니다.
대기열은 deque로 구현할 수 있습니다. 큐에 항목을 추가하려면 deque 뒤에 항목을 추가합니다. 대기열에서 항목을 제거하려면 deque 앞에서 항목을 제거합니다.
스택은 한쪽 끝에서만 항목을 추가하고 제거할 수 있는 데이터 구조입니다. 스택은 종종 후입선출(LIFO) 데이터 구조라고 합니다.
스택은 deque로 구현할 수 있습니다. 스택에 항목을 추가하려면 deque 앞에 항목을 추가합니다. 스택에서 항목을 제거하려면 deque 앞에서 항목을 제거합니다.
회문(palindrome)은 앞뒤로 같은 단어, 구 또는 숫자입니다. 예를 들어 "racecar"와 "1001"은 회문입니다.
단어가 회문인지 확인하기 위해 deque를 사용할 수 있습니다. deque 뒤에 단어의 각 문자를 추가합니다. 그런 다음 deque에서 각 문자를 제거하고 deque 앞쪽의 해당 문자와 비교합니다. 모든 문자가 일치하면 단어는 회문입니다.
데크에는 다음과 같은 시간 복잡성이 있습니다.
여기서 n은 deque의 항목 수입니다.
데크에는 다음과 같은 공간 복잡성이 있습니다.
여기서 n은 deque에 저장할 수 있는 최대 항목 수입니다.