Queue -> 언제 사용?
buffer, 마구 입력된 것을 처리하지 못하고 있는 상황, ex) BFS
2.1 선형 큐 (Linear Queue)
큐(Queue)는 한쪽 방향으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제되는 구조입니다.
예를 들자면, 가장 먼저 줄을 선 사람이 먼저 줄을 빠져나가게 됩니다.
이러한 구조를 선입 선출(FIFO : First-In First-Out) 구조라고 합니다.
더 쉬운 이해를 위해 큐의 삽입과 삭제 연산을 보겠습니다.
선형 큐의 동작은 그다지 어렵지 않습니다.
front와 rear를 인덱스 -1에 위치 -> enqueue 동작 시 rear 값 증가를
dequeue 동작 시 front 값 증가를 시켜 해당 데이터를 관리합니다.
이해를 돕기 위해 간단한 코드를 보며 큐에 대해 접근하겠습니다.
위의 예시를 구현시킨 코드입니다.
아래의 코드를 보겠습니다.
if(i <= q->front) , front가 가리키는 값이 i의 값 보다 크거나 같을 때 데이터가 없다고 표시합니다.
위의 코드에서는 front 값이 증가할 경우는 삭제 연산이 일어난 경우입니다.
if(i > q->rear) , rear가 가리키는 값보다 i의 값이 클 때 데이터가 없다고 표시합니다.
위의 코드에서는 rear가 가리키는 인덱스가 마지막 데이터의 위치이기 때문입니다.
하지만 선형 큐에는 문제점이 존재합니다.
선형적으로 데이터를 관리하기 때문에 효율적이지 못합니다.
선형큐 문제점
Front와 rear 값이 계속 증가
배열의 앞부분이 비어 있더라도 사용을 하지 못 함
매번 이동을 시키면 되지만, 그러면 시간 복잡도가 증가합니다.
2.2 원형 큐 (Circular Queue)
그래서 위의 선형 큐(Linear Queue)를 보완해 나온 것이 원형 큐(Circular Queue)입니다.
공백상태 : front == rear
포화상태 : front == (rear+1) % M
공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둔다.
아래의 원형 큐 출력 함수를 위의 선형 큐 출력 함수와 비교한다면 이해가 됩니다.
원형 큐 출력 함수 동작
로직
-
q-> front, q->rear 가 가리키는 값 출력
-
if(! is_empty(q)) // 원형 큐가 공백 상태가 아니라면,
-
i에 q->front가 가리키는 값을 대입하시오.
-
do while 문 // 무조건 한 번은 돌리고 조건과 일치하면 계속 반복하시오.
-
(front가 가리키는 인덱스 값 +1)을 MAX_QUEUE_SIZE 값과 나누었을 때 나머지 값을 i에 대입하시오.
// 예를 들어 front가 가리키는 인덱스는 삭제 연산이 진행된 것이니,
다음 인덱스부터 출력을 해야겠죠? 그 말입니다.
-
if( i == q-> rear) // front가 가리키는 값과 rear 값이 가리키는 값이 같으면 break;
-
while( i!= q-> front); // i에 대입된 값과 front 가 가리키는 값이 같지 않으면 참. -> 반복
2.3 덱 (Deque)
우리가 앞에서 선형 큐와 원형 큐를 살펴보았습니다.
맨 처음 큐는 선입 선출(FIFO : First-In First-Out) 구조라고 말했습니다.
그렇다면 뒤에서 삭제가 가능하고, 앞에서 추가가 가능하고,
원하는 rear가 가리키는 값을 바로 얻을 수는 없을까?
이러한 요구를 만족시키는 개념이 덱입니다.
덱(deque) (스택 + 큐)
덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐
새롭게 추가된 연산
delete_rear, add_front, get_rear 이 3가지만 추가가 된 것이고 나머지 연산은 동일합니다.
사실 앞에서 큐와 스택의 개념을 정확히 숙지하셨다면, 덱은 어려울 게 없습니다.
기능 3가지가 추가됐다고 생각하시면 됩니다.
스택의 장점과 큐의 장점을 합친 것입니다.
TIP : 아래의 3가지 예제 코드들을 직접 구현하는 해보는 것을 추천합니다.
