큐 자료구조 개념 설명 및 예시 코드 (C/C++)

1. 큐 자료구조 개념 설명

큐(Queue)는 가장 간단한 자료구조 중 하나로 FIFO(First In First Out)의 특성을 가지고 있습니다.

FIFO는 큐에 먼저 들어온 데이터가 먼저 나간다는 의미이고,

은행이나 맛집에서 방문한 순서대로 입장하는 평범한 대기열을 생각하면 쉽게 이해할 수 있습니다.

출처: https://waitwhile.com/blog/what-is-queue-management/

 

큐의 가장 끝 자리(rear)에 데이터를 넣는 것을 enqueue라고 하고,

가장 앞 자리(front)에서 데이터를 빼는 것을 dequeue라고 합니다.

 

dequeue 시 가장 먼저 들어온 데이터에 가장 높은 우선순위를 두고 뺀다면 일반적인 큐가 됩니다.

하지만 dequeue 시 큐에 들어온 순서가 아닌 최소값, 최대값 등 특별한 우선순위를 두고 빼는 방식을 쓴다면

이는 우선순위 큐(Priority Queue)라고 하고 통상 완전 이진 트리를 활용하는 힙(Heap)으로 구현합니다.

 

힙에 대한 내용은 아래 링크 참고하시길 바랍니다.

https://rightbellboy.tistory.com/342

힙 자료구조 개념 설명 및 예시 코드 (1 base) (C/C++)

 

 

2. 큐 자료구조 동작 원리

유연한 형태로 구현하려면 Linked List를 기반으로 Head와 Tail을 포인터로 두고 구현하는 것이 맞지만

일반적으로 Input의 최대량을 특정할 수 있는 알고리즘 시험에 맞추어 1차원 배열로 설계해보겠습니다.

 

우선 큐에 저장할 Data를 담을 1차원 배열을 선언하고, fr(front), re(rear)라는 두 integer 변수를 선언합니다.

이 두 변수들은 배열의 처음과 끝의 인덱스를 기억하게 하고 초기 값은 둘 다 0으로 설정합니다.

queue의 초기 상태

 

이 상태에서 큐에 3이라는 값이 들어오면, re(index 0)에 값을 넣고 re를 1 증가시킵니다.

(가장 뒤에 넣고, 가장 앞에서 빼는 형태라고 보시면 됩니다)

3이 enqueue된 상태

 

여기에 7이라는 값을 다시 넣는다고 하면, 마찬가지로 re(index 1)에 해당 값을 넣고 re를 1 증가시킵니다.

7이 추가로 enqueue된 상태

 

이번엔 dequeue를 해보고 어떻게 동작하는지 보겠습니다.

FIFO의 특성을 가지는 queue의 성질에 따라 먼저 들어간 3이 나와야 합니다.

따라서 fr(index 0)에 있는 값 3을 빼고 fr을 1 증가시킵니다.

먼저 들어온 3이 dequeue된 상태

 

위 이미지에서는 3이 지워진 것처럼 표기했지만

fr이 증가되어 index 0에는 어차피 접근할 수가 없으므로 굳이 삭제할 필요는 없습니다.

 

이어서 추가로 dequeue를 하면 아래와 같이 7이 나가게 됩니다.

나중에 들어온 7이 이어서 dequeue된 상태

 

위 이미지의 첫 장과 마지막 장을 보시면 아시겠지만, fr과 re가 같으면 queue가 비어있다고 볼 수 있습니다.

이를 활용하여 queue가 빌 때까지 반복하는 조건으로 사용하거나( while (fr < re) ),

queue가 빈 것을 확인하는 함수로 구현할 수도 있습니다.( return fr >= re; )

 

자세한 내용은 아래 코드를 보면서 학습해보시길 바랍니다.

 

 

3. 큐 자료구조 구현 예시 코드

#include <cstdio>

struct _que {
	int arr[7], fr, re;

	void init() {
		fr = re = 0;
	}

	void enqueue(int v) {
		arr[re++] = v;
	}

	int dequeue() {
		return arr[fr++];
	}

	bool isEmpty() {
		return fr >= re;
	}
} QUE;

int main() {
	QUE.init();
	QUE.enqueue(3);
	QUE.enqueue(7);
	printf("queue is empty ? %s\n", QUE.isEmpty() ? "true" : "false");
	printf("%d has been dequeued\n", QUE.dequeue());
	printf("%d has been dequeued\n", QUE.dequeue());
	printf("queue is empty ? %s\n", QUE.isEmpty() ? "true" : "false");
	return 0;
}