[자료구조] 5강 3장 스택과 큐 - 2절 큐

5강 3장 스택과 큐 - 2절 큐

 

*큐의 정의

리스트의 한쪽 끝에서 원소를 삽입, 다른 한쪽 끝에서는 원소의 삭제가 일어나는 구조

가장 먼저 삽입된 원소가 가장 먼저 삭제된다고 해서 선입선출(FIFO : First In First Out) 구조

 

*데크

리스트의 양쪽에서 삽입/삭제

스택과 큐를 혼합한 구조

데크의 종류에는 입력 제한 데크(스크롤), 출력 제한 데크(셀프)가 있다.

 

*요점정리

큐는 FIFO 선입선출

큐의 삽입 및 삭제 과정 – Front pointer, Rear pointer

선형 큐의 문제점을 보완하기 위한 원형큐

큐의 적용 분야들 – 작업 스케줄링

리스트의 양쪽에서 입출력이 가능한 데크 (입력제한, 출력제한 데크)

 

순서 있는 리스트

- 삽입 연산은 한쪽 끝에서

일어난다(rear라고 부른다)

-삭제 연산은 삽입의 반대쪽에서

일어난다.(front라고 부른다.)

-

FIFO

(First In First Out)

 

큐의 예

•예 - 고객 작업 처리

은행, 미용실 등 고객은 큐를 구성한다.

각 고객은 점원에게 한 개의 처리 작업이 된다.(job)

점원은 작업을 한 개씩 처리한다.

 

원형 큐 구현 - 정리

- full 큐와 empty 큐의 구별 방법(1가지를 선택하여 실천한다.)

방법 1

: 최대 MAX_QUEUE_SIZE

–

1 만 저장한다(front==rear+1 이면 full)

(MAX_QUEUE_SIZE가 아님)

방법 2

: 변수를 추가하여 두 상태를 구별한다,(데이터 개수 n을 항상 계산한다.)

- 큐를 유지하기위해 데이터 이동이 불 필요해진다.

 

* 데크

Double-Ended QUEue의 약자로서 양쪽에서 입출력이 가능한 자료 구조

스택과 큐의 동작을 복합한 방식

선형 리스트 중에서 가장 일반적인 형태

한쪽 끝에서 과잉 상태가 되는 것을 최소로 하기 위하여 노드들을 리스트의 가운데 부분에 보관

 

입력 제한 데크(input restricted deque)

출력(삭제)은 양쪽에서 다 가능하지만 입력(삽입)은

어느 한쪽 끝으로만 하도록 제한한 데크

 

출력 제한 데크(output restricted deque)

입력은 양쪽에서 다 가능하지만 출력은

어느 한쪽 끝으로만 하도록 제한한 데크