1. 큐는 삽입 작업이 한쪽 끝에서 수행될 수 있도록 하는 순서가 지정된 목록으로 정의할 수 있습니다. 뒤쪽 호출된 다른 끝에서 수행될 작업을 삭제합니다. 앞쪽 .
2. 대기열은 First In First Out 목록이라고 합니다.
3. 예를 들어, 기차표를 사기 위해 줄을 서서 기다리는 사람들이 줄을 서고 있습니다.
대기열의 응용
대기열이 선입선출 방식으로 작업을 수행한다는 사실 때문에 작업 순서가 매우 공평합니다. 아래와 같이 대기열의 다양한 응용이 논의됩니다.
- 대기열은 프린터, 디스크, CPU와 같은 단일 공유 리소스에 대한 대기 목록으로 널리 사용됩니다.
- 대기열은 예를 들어 데이터의 비동기 전송(데이터가 두 프로세스 간에 동일한 속도로 전송되지 않는 경우)에 사용됩니다. 파이프, 파일 IO, 소켓.
- 대기열은 MP3 미디어 플레이어, CD 플레이어 등과 같은 대부분의 응용 프로그램에서 버퍼로 사용됩니다.
- 대기열은 재생 목록에 노래를 추가하고 제거하기 위해 미디어 플레이어의 재생 목록을 유지하는 데 사용됩니다.
- 큐는 인터럽트를 처리하기 위해 운영 체제에서 사용됩니다.
복잡성
| 데이터 구조 | 시간 복잡도 | 우주 완성도 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 평균 | 최악의 | 최악의 | |||||||
| 입장 | 찾다 | 삽입 | 삭제 | 입장 | 찾다 | 삽입 | 삭제 | ||
| 대기줄 | 안에) | 안에) | 나(1) | 나(1) | 에) | 에) | 오(1) | 오(1) | 에) |