Data Structure #06 큐

화승이·2024년 6월 30일

CS공부

목록 보기

6/14

큐(Queue)

이번에 학습한 큐(Queue)는 앞서 했던 '스택'의 자료구조랑 굉장히 유사하면서 정반대인 자료구조이다. 스택은 접시를 여러개 쌓으면 나중에 쌓은 접시를 제일 먼저 뽑을 수 있는 후입선출의 구조라면, 큐는 먼저 들어간 데이터가 먼저 나오는 선입선출의 구조이다.

큐란?
먼저 들어간 데이터가 먼저 나오는 자료구조
FIFO(First-In, First-Out) 선입선출

대표적인 예시로는 줄을 서있는 우리의 모습을 예를 들면 된다. 우리가 줄을 서는 이유는 그 줄이 빨리 끝나서 우리가 볼 일을 보는 것이 목적인데, 큐도 다음과 같다. 먼저 나가는 데이터는 제일 먼저 줄을 서 있는 사람이라고 보면 쉽게 구조를 이해할 수 있다.

큐의 기본 연산자

큐의 기본 연산자는 크게 두가지로 나타낼 수 있다. 이도 마찬가지로 프로그래머가 구조를 어떻게 사용하냐에 나눠질 수 있겠지만 대표적으로는 데이터를 넣는 연산, 빼는 연산 크게 2가지이다.

Enqueue 연산자
큐에 데이터를 넣는 연산자이다.
Dequeue 연산자
반대로, 큐에서 데이터를 꺼내는 연산자이다. 제일 앞서 넣었던 데이터를 참조해서 빼면 된다.

큐의 ADT

다음은 큐의 ADT를 살펴보도록 하겠다.

큐의 초기화하는데 사용한다. 큐의 자료구조를 사용하기 위해서 제일 먼저 호출되어야하는 함수이다.
```
	void QueueInit(Queue * pq);
```
큐가 비어있는지 여부를 확인한다. 비워있으면 1(TRUE), 데이터가 있으면 0(FALSE)를 반환한다.
```
	int QIsEmpty(Queue * pq);
```
큐에 데이터를 저장하는 연산, 매개변수인 data로 전달된 값을 큐에 저장한다.
```
	void Enqueue(Queue * pq, Data data);
```
저장순서가 가장 앞선 데이터를 삭제 후에 반환한다.
```
	Data Dequeue(Queue * pq);
```
저장순서가 앞선 데이터를 반환한다. Dequeue의 연산에서 삭제 말고 참조된 값을 반환만 한다.
```
	Data QPeek(Queue * pq);
```

큐의 구현

이번 큐의 구현도 마찬가지로 배열과 연결리스트 기반의 구현으로 설명을 할 것이다.

큐의 배열기반 구현

큐의 머리를 F(Front), 큐의 꼬리를 R(Rear)로 가정할 때, 밑 그림으로 큐를 구현할 수 있다. 큐는 데이터를 넣을 때 데이터의 뒷부분에 삽입이 되고, 우리가 큐에서 데이터를 가져올 때는 앞부분에서 가져오기 때문에 F,R 두 개의 참조자가 다 필요하다는 것을 가정할 수 있다.

사실 위 그림에서는 문제가 있다. 만약 Dequeue연산을 2번 더 하고, Enqueue 연산을 더 했을 때 일차원적인 배열으로 볼 때 배열의 끝부분까지 계산을 하면 앞부분 배열은 비워있지만 뒤에 더 데이터를 삽입할 공간이 사라지는 것을 확인할 수 있다. 즉, R이 배열의 끝에 도달하게 되면, 회전을 해서 다시 앞부분부터 채워야하는 복잡한 일이 존재한다. 이거에 대한 해결책은 아래와 같다.

위 사진은 원형큐이다. 원형 큐는 R이 배열의 끝에 도달할 때 회전해야하는 문제를 해결해주는 구조이다. 단, 이 상태에서도 문제가 존재하는데 그 문제는 다음과 같다. 배열의 모든 공간을 다 F와 R이 사용한다면 빈 상태의 원형큐와 다 찼을 때의 원형큐에서 항상 F는 R보다 앞에 있기 때문에 두 개의 위치로만 구분이 힘들다. 그렇기에 한 공간을 비워두고 계산하면 편하다.

F와 R이 동일한 위치 => 원형 큐가 빈 상태

R이 가리키는 위치의 앞을 F가 가리킴 => 원형 큐가 꽉 찬 상태

큐의 연결리스트기반 구현

큐의 연결리스트 기반 구현은 배열 기반보다는 훨씬 구현하기 쉽다. 그 이유는 스택의 구현에서 데이터를 그냥 앞에서 꺼낸다고 생각하면 되기 때문이다.

큐 초기화
리스트 2개 (Front, Rear) 를 저장할 공간 만들기
Enqueue
처음 데이터 추가에는 Front 외에 Rear 둘 다 새 노드를 가리키게 한다. 그 이후부터는 Rear의 위치만 변경해가면서 추가하면 된다.
Dequeue
F가 가리키는 대상만 반환하고 변경시키면 된다. 얘도 마찬가지로 한 개만 남을 때는 R을 같이 해줘야하는지 걱정할 수 있지만 데이터를 추가하는 연산을 할 때 큐가 비워있는지의 여부를 확인해주는 연산은 F만 확인하기 때문에 상관이 없다.