큐 (Queue)

큐 (Queue)

FIFO 구조를 갖는 데이터 저장 방식

큐 ADT

객체: 0개 이상의 요소들로 구성된 선형리스트

(큐의 첫번째 요소를 가리키는 front와 마지막 요소를 가리키는 rear가 있음)

연산:

• create
• init
• is_empty
• is_full
• enqueue
• dequeue
• peek

배열을 이용한 선형 큐

초기 상태: front = rear= -1

데이터를 enqueue할 때마다 rear는 1씩 증가, 데이터를 dequeue할 때마다 front 1 증가

크기에 제한이 있고, 한번 dequeue한 공간을 재사용하기 어렵다.

=>메모리가 낭비된다.

연결리스트를 이용한 선형 큐

필요할 때마다 노드를 생성해서 연결 => 메모리 낭비 방지

dequeue 할 때 메모리 공간을 놓아주어야함

초기 front와 rear 포인터는 NULL을 가리키며, 큐가 비어있을 때도 NULL을 가리킴

 

-구현이 복잡해짐

배열을 이용한 원형큐

front는 첫번째 data 하나 앞의 index

rear는 마지막 요소의 index

초기 front=rear=1

공백 상태: front==rear

포화 상태: front % size == (rear+1) % size

(나머지 연산을 해야함! 아니면 front, rear 값이 index 보다 커져서 존재하지 않기 때문)

공백 상태와 포화 상태를 구별하기 위해서 front가 가리키는 공간은 항상 비워둔다! 데이터를 채우지 않음!

 

- size-1 개의 원소를 계속 넣을 수 있음

-낭비되는 공간이 배열을 이용한 선형큐에 비해 적음

-최대 크기에 제한이 있음