1. 큐, 대기열 (Queue)
ㅇ [일반]
- 대기 열을 지어 기다리고 있다는 수학적인 용어
ㅇ [자료구조]
- 컴퓨터 알고리즘의 저장구조로써 활용되는, 자료구조 종류 중 하나
ㅇ [스케줄링]
- 대기 큐 중에서 우선 처리 규칙
2. [자료구조] 큐 (Queue)
ㅇ 한쪽 끝에서 삽입되고, 다른 한쪽 끝으로 삭제되는 리스트 구조의 일종임
ㅇ 큐의 특징
- 스택 처럼, 한 번에 데이터 1개씩 만 처리
- 데이터의 입력,출력이 정해진 위치에서 만 가능
. 자료 추가(삽입,입력)는, 끝(rear)에서 만 가능
. 자료 반환(삭제,출력)은, 처음(front)에서 만 가능
. 한편, 스택에서는, 자료의 삭제/추가가 모두 한쪽 끝(top)에서 만 가능
- 전후/선후 관계가 1:1
. 즉, 선형자료구조 임
- 시간복잡도 : O(1) (상수시간)
ㅇ 큐의 구분 : 입출력 순서/처리 방법에 따라 달라짐 ☞ 큐잉 정책 참조
- 일반적인 큐 (Genaral Queue)
. 삽입된 순서에 따라 삭제됨
.. 가장 일반적인 경우 : FIFO (선입선출 : 먼저 들어간 것이, 먼저 처리됨)
- 우선순위 큐 (Priority Queue)
. 임의 순서로 삽입되나(입력/추가), 일정 순서로 삭제됨/출력됨/제거됨
.. 입력은 임의 순서이나,
.. 출력은 반드시 일정한/정해준 순서를 갖음
ㅇ 큐의 용어
- 큐에 자료 추가 : 인큐 (Enqueue)
- 큐에서 자료 제거 및 반환 : 디큐 (Dequeue)
- 큐 자료 접근(자료 제거가 아닌 반환 만) : 피크 (Peek)
- 처음/전단 자료 : 프런트 (Front) 또는 헤드 (Head)
- 마지막/후단 자료 : 리어 (Rear) 또는 테일 (Tail)
ㅇ 큐의 연산(동작)
- 큐 생성 : createQueue()
- 큐 삭제(메모리 해제) : deleteQueue()
- 큐 포화 여부 : isFull()
- 공백 큐 여부 : isEmpty(q)
. 큐 q가 비었으면 true
- 인큐 : enqueue(q,i)
. 큐 q의 끝(테일)에 항목 i를 추가
- 디규 : dequeue(q)
. 큐 q의 처음(헤드)에서 항목 제거 후 다음 항목을 헤드로 만듬
. 큐가 비었으면 오류 발생시킴
- 피크 : peek()
ㅇ 큐의 구현 방법
- 배열을 이용하는 방법
- 연결 리스트를 이용하는 방법
ㅇ 구현 例)
- Python 例) (by 파이썬 모듈 collections의 deque)
. from collections import deque; queue = deque(); queue.append(1); queue.append(2);
queue.append(3); queue.popleft(); print(queue) => deque([2, 3])
- Javascript 例) (by 자바스크립트 배열 메서드 중 push(),shift())
. let queue = []; queue.push(1); queue.push(2); queue.push(3);
console.log(queue); // => [1, 2, 3]
queue.shift(); console.log(queue); // => [2, 3]
. 또는, (by 자바스크립트 배열 메서드 중 unshift(),pop())로도 가능
ㅇ 주요 용도 : 작업들 간에 처리 순서를 관리하는 등
- 프린터 작업 대기열, 운영 체제의 작업 스케줄링, 네트워크 패킷 처리 등
3. [스케줄링] 큐 처리 방식
※ ☞ 큐잉 정책 (Queuing) 참조
- 입출력(삽입,삭제) 순서에 대한 정책에 따라 여러 큐잉 형태 있음
. 선입선출 (FIFO), 선입후출 (FILO) 등