Deque의 응용, 장점 및 단점

Deque 또는 이중 종료 큐는 이중 종료 큐와 유사한 기능을 제공하는 순차 선형 수집 데이터 큐입니다. 이 데이터 구조에서는 데이터 처리에 있어 FIFO(선입선출) 규칙을 따르지 않습니다. 이 데이터 구조는 요소가 큐의 끝에 삽입되고 맨 앞에서 제거되기 때문에 deque라고도 합니다. deque를 사용하면 양쪽 끝에서만 데이터를 추가하고 제거할 수 있습니다. Deque 연산의 시간 복잡도는 O(1)입니다. 데크에는 두 가지 종류가 있어요 -

• 입력이 제한되어 있습니다

• 단일 종단 입력 제한.

• 양쪽 끝에서 데이터 삭제를 허용합니다.

• 출력 제한

• 단일 종단 출력 제한.

• 양쪽 끝에 데이터를 삽입할 수 있습니다.

다음 명령은 코더가 데크에서 데이터 세트 풀링을 사용하여 다양한 작업을 수행하는 데 도움이 됩니다. -

• push_back() - 데크 뒤에서 요소를 삽입합니다.

• push_front() - 데크 앞에서 요소를 삽입합니다.

• pop_back() - 데크 뒷면에서 요소를 제거합니다.

• pop_front() - 데크 앞부분의 요소를 제거합니다.

• front() - 데크의 앞부분 요소를 반환합니다.

• back() - 데크 뒤에 있는 요소를 반환합니다.

• at() - 지정된 인덱스를 설정/반환합니다.

• size() - 요소 수를 반환합니다.

• empty() - 데크가 비어 있으면 true를 반환합니다.

원형 배열에서는 deque 연산을 사용할 수 있습니다. 어레이가 가득 차면 처음부터 프로세스를 시작할 수 있습니다. 그러나 선형 배열의 경우 배열이 가득 차면 더 이상 데이터를 삽입할 수 없습니다. 그러면 "오버플로 팝업"이 표시됩니다.

양단 큐 적용

Deque에는 다양한 실시간 애플리케이션이 있습니다.

• 작업 일정 신청용.

• O(1) 시간 안에 시계 방향 및 반시계 방향 회전 작업을 수행할 수 있습니다.

• deque 알고리즘은 웹 브라우저 기록에도 존재합니다.

• 정렬 시 실행 취소 작업을 수행합니다.

양단 큐의 장점

데크에는 많은 장점이 있습니다.

• 앞뒤에서 데이터를 추가하고 삭제할 수 있습니다.

• 그들의 크기는 역동적입니다.

• Deque는 작업 수행에 효율적인 타이밍을 제공합니다.

• 여기에서는 LIFO 스택이 사용됩니다.

• 여기서는 재배포가 불가능합니다.

• 이것은 적절한 동기화를 통한 스레드로부터 안전한 프로세스입니다.

• 캐시 친화적입니다.

양단 큐의 단점

이중 대기열의 단점은

• Deque 프로세스 메모리 소비율이 높습니다.

• 다중 스레드 동기화 문제가 있습니다.

• 일부 플랫폼에서는 사용할 수 없습니다.

• 정렬 작업을 구현하는 데 적합하지 않습니다.

• Deque에는 기능이 더 적습니다.

양단 큐 연산 알고리즘

• 1단계 - 크기 n의 deque 배열을 고려합니다.

• 2단계 - 두 포인터를 "front=-1"(앞을 의미) 및 "rear=0"(설정을 의미)으로 설정합니다.

이 프로세스에는 여러 하위 부분이 있습니다. Deque에서는 여러 작업을 수행할 수 있습니다. 여기에 요약해 보겠습니다.

• deque의 앞부분부터 데이터를 삽입하는 알고리즘:-

• 1단계 - 전면 위치를 확인하세요.

• 2단계 - "front

• 3단계 - 그렇지 않으면 "front"를 1 줄여야 합니다.

• 4단계 - 배열 전면에 새 키 요소를 추가합니다.

• deque 뒤에 데이터를 삽입하는 알고리즘:-

• 1단계 - 배열이 꽉 찼는지 확인하세요.

• 2단계 - 가득 차면 "rear=0"을 적용합니다.

• 3단계 - 그렇지 않으면 "rear" 값을 1만큼 늘립니다.

• 4단계 - "array[rear]"에 새 키를 다시 추가합니다.

• deque 앞의 데이터를 삭제하는 알고리즘:-

• 1단계 - 데크가 비어 있는지 확인하세요.

• 2단계 - 목록이 비어 있으면("front=-1") 언더플로 상태이므로 삭제를 수행할 수 없습니다.

• 3단계 - 데크에 요소가 하나만 있는 경우. 그런 다음 "앞=뒤=-1"입니다.

• 4단계 - 그렇지 않으면 "front"가 끝에 있고 "front=0"으로 설정됩니다.

• 5단계 - 그렇지 않으면 앞=앞+1입니다.

• deque 뒷면에서 데이터를 삭제하는 알고리즘:-

• 1단계 - 데크가 비어 있는지 확인하세요.

• 2단계 - 비어 있으면("front=-1") 삭제를 수행할 수 없습니다. 이는 언더플로우 상태입니다.

• 3단계 - deque에 데이터가 하나만 있는 경우 "front=rear=-1"입니다.

• 4단계 - 그렇지 않은 경우 아래 단계를 따르세요.

• 5단계 - 후면이 전면인 경우 "rear=0"입니다. 전면 "후면 = n-1"로 이동합니다.

• 6단계 - 그렇지 않으면 후면=후면-1입니다.

• deque가 비어 있는지 확인하는 알고리즘:-

• 1단계 - front=-1이면 데크가 비어 있습니다.

• deque가 가득 찼는지 확인하는 알고리즘:-

• 1단계 - 이전=0이고 이후=n-1

인 경우

• 2단계 - 또는 앞=뒤+1

deque 구문

으아아아

데이터 구조에서 deque는 스택 및 큐의 일부 속성을 상속합니다. C++에서 deque는 벡터의 벡터로 구현됩니다.

양단 큐를 이용한 다양한 메소드 처리

• 방법 1 - 일반적인 방식으로 deque 구현

• 방법 2 - deque에 요소 삽입

• 방법 3 - 데크에서 요소에 액세스

• 방법 4 - 데크의 요소 변경

양단 큐의 일반적인 구현

이 C++ 빌드 코드에서는 일반적인 방식으로 deque 작업을 구성합니다. 이 예에서는 대기열의 백엔드에 요소를 삽입하며 이것이 전체 시스템이 수행되는 방식입니다.

예 1

으아아아

출력

으아아아

deque에 요소 삽입

이 코드에서는 데크에 요소를 삽입하는 C++ 코드를 생성하려고 합니다. 이를 수행하는 방법에는 두 가지가 있습니다.

• push_back() - 배열 끝에 요소를 삽입합니다.

• push_front() - 배열의 시작 부분에 요소를 삽입합니다.

예 2

으아아아

출력

으아아아

deque의 요소에 액세스

두 가지 방법을 사용하여 데크의 요소에 액세스할 수 있습니다.

• front() - 앞에서 반환 값을 얻을 수 있습니다.

• back() - 다음 데이터를 반환합니다.

• at() - 지정된 인덱스에서 반환합니다.

으아아아

출력

으아아아

데크의 요소 변경

이 코드에서는 at() 메서드를 사용하여 특정 데크의 요소를 바꾸거나 변경할 수 있습니다.

예 4

으아아아

출력

으아아아

결론

이번 글을 통해 우리는 Double-ended Queue의 동작 방식, 응용, 장단점, C++를 이용한 알고리즘과 가능한 코드에 대해 알아보았습니다.

위 내용은 Deque의 응용, 장점 및 단점의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!