큐는 어떤 데이터 구조인가요?
- 藏色散人원래의
- 2020-12-25 10:45:159862검색
큐는 선형 데이터 구조입니다. 큐는 테이블의 프런트 엔드에서만 삭제 작업을 허용하는 반면, 삽입 작업은 테이블의 백 엔드에서 수행됩니다. 큐는 삽입 작업이 수행되는 끝에서 제한된 작업을 수행하는 선형 테이블입니다. 대기열의 꼬리라고 하며 삭제 작업이 수행됩니다. 끝을 팀장이라고 합니다.
이 기사의 운영 환경: windows10 시스템, thinkpad t480 컴퓨터.
큐는 선형 데이터 구조입니다.
큐는 특별한 선형 테이블입니다. 특별한 점은 테이블의 프런트 엔드(전면)에서만 삭제 작업과 테이블의 백 엔드(후면)에서만 삽입 작업을 허용한다는 것입니다. 제한된 선형 테이블에 대한 작업입니다. 삽입 작업을 수행하는 끝을 큐의 꼬리라고 하고 삭제 작업을 수행하는 끝을 큐의 헤드라고 합니다. 큐에 요소가 없으면 빈 큐라고 합니다.
큐의 데이터 요소를 큐 요소라고도 합니다. 큐에 큐 요소를 삽입하는 것을 큐에 넣기(enqueuing)라고 하며, 큐에서 큐 요소를 삭제하는 것을 큐에서 빼기(dequeuing)라고 합니다. 큐는 한쪽 끝에서는 삽입하고 다른 쪽 끝에서는 삭제만 허용하기 때문에 가장 먼저 큐에 들어간 요소만 큐에서 먼저 삭제될 수 있으므로 이 큐를 FIFO(선입선출)라고도 합니다. 첫 번째 아웃) 선형 목록.
순차 큐
순차 큐 구조를 구축하려면 연속적인 저장 공간을 정적으로 할당하거나 동적으로 적용해야 하며, 관리를 위한 두 개의 포인터를 설정해야 합니다. 하나는 헤드 요소를 가리키는 전면 헤드 포인터이고, 다른 하나는 그림에 표시된 것처럼 팀에 추가되는 다음 요소의 저장 위치를 가리키는 후면 포인터입니다. 팀의 끝에 요소가 삽입될 때마다 Rear는 1씩 증가하고 대기열의 선두에서 요소가 삭제될 때마다 Front는 1씩 증가합니다. 삽입 및 삭제 작업이 진행됨에 따라 큐 요소의 개수는 계속해서 변경되며, 큐가 차지하는 저장 공간도 큐 구조에 할당된 연속 공간에서 이동합니다. front=rear인 경우 큐에 요소가 없으며 이를 빈 큐라고 합니다. 할당을 가리키는 연속된 공간을 넘어 후면이 증가하면 큐는 더 이상 새로운 요소를 삽입할 수 없지만 이때 점유되지 않은 사용 가능한 공간이 많은 경우가 많습니다. 이러한 공간은 가 차지한 저장 단위입니다. 대기열에서 제거된 대기열 요소입니다.
순차 큐에서의 오버플로우 현상: 
원형 큐
실제로 큐를 사용할 때 큐 공간을 재사용 가능하게 만들기 위해 큐 사용 방법이 약간 개선되는 경우가 많습니다. 삽입이나 삭제에 관계없이 후면 포인터가 1씩 증가하거나 전면 포인터가 증가하면 1만큼 초과하면 할당된 큐 공간은 이 연속 공간의 시작 위치로 향합니다. 실제로 MaxSize-1을 1씩 0으로 변경하는 경우 나머지 작업인 Rear%MaxSize 및 front%MaxSize를 사용하여 이를 달성할 수 있습니다. 이는 실제로 큐 공간을 원형 공간으로 상상하며, 원형 공간의 저장 단위가 순환적으로 사용되는 방식으로 관리되는 큐를 순환 큐라고도 합니다. 몇 가지 간단한 애플리케이션 외에도 실제로 실용적인 대기열은 순환 대기열입니다.순환 대기열에서는 대기열이 비어 있으면 앞=뒤가 있고 대기열 공간이 모두 가득 차면 앞=뒤도 있습니다. 두 가지 상황을 구별하기 위해 순환 대기열은 최대 MaxSize-1 대기열 요소만 가질 수 있다고 규정됩니다. 순환 대기열에 빈 저장 단위가 하나만 남아 있으면 대기열이 가득 찼습니다. 따라서 큐가 비어지는 조건은 front=rear이고, 큐가 가득 차는 조건은 front=(rear+1)%MaxSize입니다. 비어 있거나 꽉 찬 대기열의 상황은 아래와 같습니다.
추천: "
Programming Video"
위 내용은 큐는 어떤 데이터 구조인가요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!