Queue(큐)

개념

먼저 들어온 데이터가 먼저 나가는 구조를 갖고 있고 이러한 특성을 FIFO(First In First Out)라고 한다. 따라서 큐는 삽입, 삭제가 다른 쪽에서 일어난다. 삽입하는 곳(큐의 뒤쪽)을 rear, 삭제하는 곳을(큐의 맨 앞쪽) front라고 한다. 그래서 변수를 사용할 때도 이와 동일한 이름으로 사용된다.

연산

1. enqueue

큐의 맨 끝에 새로운 데이터를 삽입하는 연산이다.

2. dequeue

큐의 맨 앞에 있는 데이터를 꺼내서 리턴한다. 삭제 연산이다.

3. isFull

큐가 가득 찼는지 확인하는 연산이다.
큐가 가득 찼으면 true, 그렇지 않으면 false를 반환한다.

4. isEmpty

큐가 비어있는지 확인하는 연산이다.
비어있으면 true, 그렇지 않으면 false를 반환한다.

5. peek

큐의 맨 앞에 있는 데이터를 읽어서 리턴해준다. (맨 앞에 어떤 데이터가 있는지 알기 위함)

선형큐(Linear Queue)

큐를 구현할 때 가장 간단하게 1차원 배열을 사용하여 구현하는 방법이다. 삽입, 삭제를 위한 변수인 front, rear를 만들고 초기값을 -1로 한다. 그 후, 데이터가 추가되면 rear를 하나 증가시키고 그 위치에 데이터를 저장한다. 삭제할 때도 front를 하나 증가시키고 그 자리에 있는 데이터를 삭제한다.

선형큐는 작업 스케줄링에 사용된다.

원형큐(Circular Queue)

선형큐의 문제점을 개선하여 고안된 방법이다. 선형큐에서 삽입, 삭제를 계속해서 하다보면 front, rear값이 계속 증가되므로 언젠가는 배열의 끝에 도달하게 된다. 이렇게 되면 배열의 앞부분이 비어 있어도 배열을 사용하지 못한다는 문제점이 있다.

구현 자체는 배열로 하지만 개념적으로는 원형이라고 상상하면 된다. 원형큐는 front와 rear의 값이 배열의 끝인(Max_Queue_Size-1)에 다다르면 다음 값은 0이 되도록 한다. 선형큐와는 달리 원형큐는 front와 rear의 초기값이 0이다. 따라서 front == rear이면 공백 상태이다. 원형큐에서는 한 자리는 꼭 비워두는데 포화 상태와 공백 상태를 구분하기 위해서이다.

원형큐의 삽입, 삭제 연산은 나머지 연산자(%)를 사용한다. 예를 들어,
front = (front + 1) % MAX_QUEUE_SIZE;
요렇게 하기 때문이다. 삭제 연산 또한 이렇게 한다!

덱(Deque)

Deque: Double-ended Queue의 줄임말.
큐의 front와 rear 둘다 삽입, 삭제가 가능한 큐이다.
따라서 스택과 큐의 연산이 모두 가능하다!

그 외

큐의 응용은??
버퍼 문제에서 사용된다!

버퍼란? 어떤 장치에서 다른 장치로 데이터를 송신할 때 일어나는 시간의 차이나 데이터 흐름의 속도 차이를 조정하기 위해 일시적으로 데이터를 기억시키는 장치

간단한 예시로는 프린팅 버퍼, 시뮬레이션, cpu 스케줄링 등이 있다.