CAPS 위키 : 큐

#queue [ 수정 내역 ] [ 수정 ]

최근 수정:

목차

1. 개요

2. enqueue

3. dequeue

4. front

5. empty

6. size

7. 에필로그

1. 개요

https://www.5balloons.info/wp-content/uploads/2017/06/queue.png

queue. 먼저 들어간 데이터가 먼저 나오는 자료구조. 흔히들 FIFO (First In First Out)라 부른다. 연산으로는 크게 enqueue, dequeue, front, empty, size 등이 있는데 큐에 데이터를 넣고 빼는 작업을 한다. 여기서 front는 큐에 제일 먼저 넣은 데이터를 말한다.

사용하는 변수는 front, back (혹은 rear)로 어디가 맨 앞인지, 맨 뒤인지 알 수 있다. 특히, 큐는 스택과 다르게 넣고 빼고를 하다보면 front가 배열 맨 뒤로 넘어가서 꽉 차게 되는 현상이 발생하는데, 이를 해결하기 위해 약간의 연산을 추가하여 원형 큐라는 것을 사용한다. 아래 코드는 모두 원형 큐를 사용하여 구현되었다. 그리고 배열의 크기를 나타내는 상수 SIZE를 사용하였다.

2. enqueue

큐에 데이터를 추가하는 연산. 배열이라면 제일 뒤에 데이터를 추가한다.

// C 언어

void enqueue(int data)

{

queue[back++ % SIZE] = data;

}

3. dequeue

큐에서 데이터를 제거하는 연산. 배열이라면 제일 앞에 있는 데이터를 제거한다.

// C 언어

void dequeue()

{

++front;

}

4. front

큐에서 제일 먼저 넣은 데이터를 리턴해준다.

// C 언어

int front()

{

return queue[front % SIZE];

}

5. empty

큐가 비어있는지 확인한다. 여기서는 원형 큐를 사용하였기 때문에 front와 back이 같은지 확인하면 된다.

// C 언어

int empty()

{

return front== back;

}

6. size

큐의 크기를 반환한다.

// C 언어

int size()

{

return back - front;

}

7. 에필로그