1.개요

Queue는 스택과는 다르게 양끝에서 삽입과 삭제가 각각 일어나는 자료구조다. 앞에 있는 것은 Front, 뒤에 있는 것은 Rear라고 한다. FIFO(First-In-First-Out)구조로, 스택과는 다르게 먼저온 것이 먼저 나간다. 밑의 이미지를 보면 이해가 더 잘 될 것이다.

하지만 이미지와 같은 선형큐(Linear Queue)에서, 삽입과 삭제를 반복하다보면, 문제가 하나 생긴다. 바로 front와 rear의 주소값이 큐의 최대 용량 보다 더 커진다는 점이다. 이건 밑의 이미지를 참조하자.

이에 대한 대책으로, 선형큐보다는 원형큐(Circular Queue)를 쓰면 된다. 원형큐란 마지막 원소가 첫번재 원소에 이어지는 구조다. 그래서 선형큐와는 다르게 재사용이 가능하다. 여기서 설명하는 큐는 원형큐에 대해 설명할것이다. 밑의 이미지 참조.

empty와 full 상태를 비교하기 위해서, 공간 한 개는 빈 상태로 나둬야 한다.

2. 기능

Queue Create(max_size)

max_size의 크기를 가진 Queue를 생성시키는 constructor. front와 rear의 초기값을 0으로 설정한다.

void Enqueue(item)

queue가 꽉차면 에러를, 아니면 item을 queue의 rear 위치에 넣는다. rear = (rear+1) % max_size

Element Dequeue()

queue가 비었으면 에러를, 아니면 front 위치의 item을 return하고 제거한다. front = (front+1) % max_size

Boolean Isfull()

(rear+1) % max_size == front queue가 꽉차면 true를, 아니면 false를 return

Boolean Isempty()

front == rear 가 true면 비어있는 상태

3. 코드

개인적으로 정리한 자료구조입니다. 수정되거나 건의 할 사항이 있으면, 21600055@handong.edu로 메일 바랍니다.