큐는 어떤 데이터 구조인가요?

큐는 선형 데이터 구조입니다. 큐는 테이블의 프런트 엔드에서만 삭제 작업을 허용하는 반면, 삽입 작업은 테이블의 백 엔드에서 수행됩니다. 큐는 삽입 작업이 수행되는 끝에서 제한된 작업을 수행하는 선형 테이블입니다. 대기열의 꼬리라고 하며 삭제 작업이 수행됩니다. 끝을 팀장이라고 합니다.

이 기사의 운영 환경: windows10 시스템, thinkpad t480 컴퓨터.

큐는 선형 데이터 구조입니다.

큐는 특별한 선형 테이블입니다. 특별한 점은 테이블의 프런트 엔드(전면)에서만 삭제 작업과 테이블의 백 엔드(후면)에서만 삽입 작업을 허용한다는 것입니다. 제한된 선형 테이블에 대한 작업입니다. 삽입 작업을 수행하는 끝을 큐의 꼬리라고 하고 삭제 작업을 수행하는 끝을 큐의 헤드라고 합니다. 큐에 요소가 없으면 빈 큐라고 합니다.

큐의 데이터 요소를 큐 요소라고도 합니다. 큐에 큐 요소를 삽입하는 것을 큐에 넣기(enqueuing)라고 하며, 큐에서 큐 요소를 삭제하는 것을 큐에서 빼기(dequeuing)라고 합니다. 큐는 한쪽 끝에서는 삽입하고 다른 쪽 끝에서는 삭제만 허용하기 때문에 가장 먼저 큐에 들어간 요소만 큐에서 먼저 삭제될 수 있으므로 이 큐를 FIFO(선입선출)라고도 합니다. 첫 번째 아웃) 선형 목록.

순차 큐

순차 큐 구조를 구축하려면 연속적인 저장 공간을 정적으로 할당하거나 동적으로 적용해야 하며, 관리를 위한 두 개의 포인터를 설정해야 합니다. 하나는 헤드 요소를 가리키는 전면 헤드 포인터이고, 다른 하나는 그림에 표시된 것처럼 팀에 추가되는 다음 요소의 저장 위치를 ​​가리키는 후면 포인터입니다. 팀의 끝에 요소가 삽입될 때마다 Rear는 1씩 증가하고 대기열의 선두에서 요소가 삭제될 때마다 Front는 1씩 증가합니다. 삽입 및 삭제 작업이 진행됨에 따라 큐 요소의 개수는 계속해서 변경되며, 큐가 차지하는 저장 공간도 큐 구조에 할당된 연속 공간에서 이동합니다. front=rear인 경우 큐에 요소가 없으며 이를 빈 큐라고 합니다. 할당을 가리키는 연속된 공간을 넘어 후면이 증가하면 큐는 더 이상 새로운 요소를 삽입할 수 없지만 이때 점유되지 않은 사용 가능한 공간이 많은 경우가 많습니다. 이러한 공간은 가 차지한 저장 단위입니다. 대기열에서 제거된 대기열 요소입니다.

순차 큐에서의 오버플로우 현상:

(1) "언더플로우" 현상: 큐가 비어 있을 때 큐 연산으로 인해 발생하는 오버플로우 현상. "언더플로우"는 정상적인 현상이며 프로그램 제어 전송을 위한 조건으로 자주 사용됩니다.

(2) "진정한 오버플로" 현상: 대기열이 가득 찼을 때 스택에 대한 푸시 작업으로 인해 공간 오버플로가 발생합니다. "True Overflow"는 오류 조건이므로 피해야 합니다.

(3) "False Overflow" 현상: Enqueue 및 Dequeue 작업 중에 Head 및 Tail 포인터가 증가만 하고 감소하지 않으므로 삭제된 요소의 공간은 절대 재사용할 수 없습니다. 큐의 실제 요소 수가 벡터 공간의 크기보다 훨씬 작은 경우 테일 포인터가 벡터 공간의 상한을 초과하여 큐 작업이 불가능할 수 있습니다. 이 현상을 "거짓 오버플로"라고 합니다.

원형 큐

실제로 큐를 사용할 때 큐 공간을 재사용 가능하게 만들기 위해 큐 사용 방법이 약간 개선되는 경우가 많습니다. 삽입이나 삭제에 관계없이 후면 포인터가 1씩 증가하거나 전면 포인터가 증가하면 1만큼 초과하면 할당된 큐 공간은 이 연속 공간의 시작 위치로 향합니다. 실제로 MaxSize-1을 1씩 0으로 변경하는 경우 나머지 작업인 Rear%MaxSize 및 front%MaxSize를 사용하여 이를 달성할 수 있습니다. 이는 실제로 큐 공간을 원형 공간으로 상상하며, 원형 공간의 저장 단위가 순환적으로 사용되는 방식으로 관리되는 큐를 순환 큐라고도 합니다. 몇 가지 간단한 애플리케이션 외에도 실제로 실용적인 대기열은 순환 대기열입니다.

순환 대기열에서는 대기열이 비어 있으면 앞=뒤가 있고 대기열 공간이 모두 가득 차면 앞=뒤도 있습니다. 두 가지 상황을 구별하기 위해 순환 대기열은 최대 MaxSize-1 대기열 요소만 가질 수 있다고 규정됩니다. 순환 대기열에 빈 저장 단위가 하나만 남아 있으면 대기열이 가득 찼습니다. 따라서 큐가 비어지는 조건은 front=rear이고, 큐가 가득 차는 조건은 front=(rear+1)%MaxSize입니다. 비어 있거나 꽉 찬 대기열의 상황은 아래와 같습니다.

추천: "

Programming Video

"

위 내용은 큐는 어떤 데이터 구조인가요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!