[자료구조/알고리즘]05. 큐

CH 05 큐(Queue)

목표

자료구조 큐에 대해 알아보고, C/C++ 프로그래밍 언어로 구현해봄으로써 큐의 대한 이해의 깊이를 늘려보세요!

목차

1. 큐란 무엇인가?
2. 큐 ADT
3. C로 구현하기
4. C++로 바꿔보기
5. 결론

1. 큐란 무엇인가?

큐란 마치, 순서가 있는 대기열 같습니다.

그림처럼 은행의 대기열이 있다고 합시다. 당연히 먼저 온 사람이 먼저 나가게 되겠죠? 이것이 바로 큐입니다. 유식한 말로는 FIFO(First In First Out) 구조라고 하지요. 이번 시간에 우리가 구현할 큐는 배열 기반의 원형 큐입니다. 본격적으로 코드를 구현하기 전에 원형 큐가 무엇인지 살펴보도록 하죠.

일반 배열로 큐를 구현했을 때, 우리가 가질 수 있는 문제점 중 하나는, 큐가 꽉차면, 재활용이 불가능하다는 점입니다. 왜냐하면, 배열 내 첫 인덱스를 가리키는 front, 끝을 가리키는 rear가 있을 때, 큐의 끝까지 데이터를 삽입하고 삭제하였을 때 front, rear를 앞으로 돌릴 방법이 없기 때문입니다. 다음 그림을 봐주세요.

이미 삽입가 삭제가 끝까지 이루어져 배열 마지막 인덱스에 first, rear가 위치하고 있습니다. 이 때, 추가나 삭제가 이루어질 수 있을까요? 결과는 당연히 아닙니다. 배열 범위를 초과하기 때문이지요. 큐의 이러한 문제점을 극복하기 위해서 원형 큐가 만들어졌습니다. 원형 큐는 인덱스가 배열의 길이 이상일 때, 다음의 연산으로 다시 0으로 돌아갑니다.

idx = (idx + 1) % arr.length

다음 그림은 왼쪽이 원형 큐가 비었을 때이고, 오른쪽이 원형 큐가 꽉 차 있을 때 입니다. 여기서 큐가 비어있고, 차있고를 판단하는 기준이 무엇인지 스스로 파악해보세요. 원형 큐의 가장 중요한 것은 한 공간을 비워둔다는 것입니다. 이것은 3절 코드 설명 때, 같이 설명하도록 하겠습니다.

2. 큐 ADT

큐의 ADT는 다음과 같습니다.

ADT Queue

• characters:
  1. arr: T[]
     • 데이터가 저장되는 배열
  2. front: Int
     • 현재 큐의 맨 앞 부분을 가리키는 인덱스
  3. rear: Int
     • 현재 큐의 맨 뒷 부분을 가리키는 인덱스
• operations:
  1. QInit(q: Queue *): void
     • 큐의 초기화를 담당
     • 큐 생성 후 가장 먼저 호출됨
  2. QIsEmpty(q: Queue *): bool
     • 큐가 비어있는지 여부를 반환
  3. QIsFull(q: Queue *): bool
     • 큐가 꽉 차 있는지 여부를 반환
     • 원형 큐로 만들면서 필요해진 연산
  4. QPeek(q: Queue *): T
     • 큐의 맨 앞의 원소를 반환
  5. QDequeue(q: Queue *): T
     • 큐의 맨 앞의 원소를 삭제한 후 반환
  6. QEnqueue(q: Queue *, data: T): void
     • 큐의 맨 뒤의 원소를 추가

3. C로 구현하기

먼저 Queue.h 를 만들고 다음을 복사해 주세요.

Queue.h

#pragma once

#include<stdbool.h>

#define MAX 5

typedef int T;

typedef struct _array_queue {
	T arr[MAX];
	int front;
	int rear;
}ArrayQueue;

typedef ArrayQueue Queue;

void QInit(Queue * q);
bool QIsEmpty(Queue * q);
bool QIsFull(Queue * q);
T QPeek(Queue * q);
T QDequeue(Queue * q);
void QEnqueue(Queue * q, T data);

코드를 하나 하나 살펴보도록 하죠.

#pragma once

이 부분은 앞 장들에서 설명했던 프로가드 부분입니다.

#include<stdbool.h>

#define MAX 5

typedef int T;

typedef struct _array_queue {
	T arr[MAX];
	int front;
	int rear;
}ArrayQueue;

typedef ArrayQueue Queue;

먼저 bool 타입을 위해 stdbool 헤더를 넣었고, int를 데이터 T로 재명명하였습니다. 그리고 원형 큐를 표현하기 위해서, MAX만큼 길이를 가진 배열 arr, 큐의 첫 번째를 가리키는 first 큐의 마지막을 가리키는 rear를 ArrayQueue의 필드로 선언하고, 더 쉽게 사용하기 위해 Queue로 재명명하였습니다.

void QInit(Queue * q);				//큐 초기화
bool QIsEmpty(Queue * q);			//큐 비어있는지 여부
bool QIsFull(Queue * q);			//큐 꽉 차 있는지 여부
T QPeek(Queue * q);					//큐의 맨 앞 데이터 반환
T QDequeue(Queue * q);				//큐의 맨 앞 데이터 삭제 후 반환
void QEnqueue(Queue * q, T data);   //큐 데이터 삽입

위의 코드는 앞서 2절에서 정의한 Queue의 ADT를 C코드로 옮긴 것입니다. 바로 구현을 해보도록 하죠. Queue.c 파일을 만들고 다음을 복사해 주세요.

Queue.c

#include"Queue.h"

#include<assert.h>

void QInit(Queue * q) {
	q->front = 0;
	q->rear = 0;
}

int next(int idx, int capacity) {
	return (idx + 1) % capacity;
}

bool QIsEmpty(Queue * q) {
	return q->front == q->rear;
}

bool QIsFull(Queue * q) {
	return next(q->rear, MAX) == q->front;
}

T QPeek(Queue * q) {
	assert(QIsEmpty(q) == false);
	return q->arr[q->front];
}

T QDequeue(Queue * q) {
	assert(QIsEmpty(q) == false);
	T ret = q->arr[q->front];
	q->front = next(q->front, MAX);
	return ret;
}

void QEnqueue(Queue * q, T data) {
	assert(QIsFull(q) == false);
	q->arr[q->rear] = data;
	q->rear = next(q->rear, MAX);
}

이제 하나, 하나 설명하도록 하겠습니다. 먼저 큐를 초기화하는 QInit입니다.

void QInit(Queue * q) {
	q->front = 0;
	q->rear = 0;
}

큐의 필드 arr은 정적 배열이기 때문에 선언 시 0으로 자동 초기화됩니다. 따라서 front와 rear에 배열의 첫 인덱스를 가리키는 0으로 초기화 해줍니다. 그림으로 보면 다음과 같습니다.

그 다음은 next 함수인데요. next 함수는 아까 설명 드렸던 연산, 인덱스에 대해서 1을 더한 후 배열의 길이만큼 나머지 연산을 수행하면 됩니다.

int next(int idx, int capacity) {
	return (idx + 1) % capacity;
}

여기서는 idx에는 삽입 시에는 rear, 삭제 시에는 front 그리고 capacity에는 MAX의 값이 들어갑니다. 다음은 rear가 next 함수로 인해 결국은 끝을 지나 첫 인덱스로 돌아가는 그림입니다.

이제 큐가 비었는지 여부를 반환하는 QIsEmpty 입니다. 큐가 비었을 때는 무조건 front와 rear가 가리키는 인덱스가 동일할 때입니다. 만약 큐의 데이터가 있다면, rear가 무조건 front의 위치와 다를 것이고 마지막 한 칸을 비워두기 때문에 큐가 비는 상황 외에는 이 둘의 인덱스가 같아질 경우가 없기 때문입니다.

bool QIsEmpty(Queue * q) {
	return q->front == q->rear;
}

다음 그림은 큐가 비었을 때 상황입니다. 이번에는 큐가 비었음을 알리기 위해서 0인덱스가 아닌 다른 곳을 가리키는 것을 확인할 수 있습니다.

다음은 큐의 꽉 차있는지 여부를 반환하는 QIsFull입니다. 앞서 말했듯, 큐의 한 칸을 비워두기 때문에, 큐가 꽉 찼다면 rear에 next 함수를 적용했을 때 그 값이 front와 같아야 합니다.

bool QIsFull(Queue * q) {
	return next(q->rear, MAX) == q->front;
}

다음은 위의 빈 상태의 큐가 4개의 데이터를 삽입하여 꽉 찬 상황을 표현한 그림입니다.

이제 큐의 맨 앞 front 자리의 데이터만 반환하는 QPeek 함수입니다. 이 함수의 예외 사항은 큐가 비었을 때 입니다. 비었다면 첫 데이터가 없기 때문이지요. 따라서 큐가 빈지 확인하고 비지 않았을 때, front의 값을 보내주어야 합니다. 코드는 다음과 같습니다.

T QPeek(Queue * q) {
	assert(QIsEmpty(q) == false);
	return q->arr[q->front];
}

다음은 큐의 맨 앞 데이터를 반환하는 상황을 표현한 그림입니다.

이제 큐의 맨 앞 데이터를 삭제하는 QDequeue 함수 입니다. QDequeue 도 QPeek 처럼 큐가 비어있으면 안됩니다. 그 예외 처리를 한 후, front의 데이터를 저장하고 front의 위치를 next(front, capacity) 로 옮깁니다. 그 후 그 데이터를 반환합니다.

T QDequeue(Queue * q) {
	assert(QIsEmpty(q) == false);
	T ret = q->arr[q->front];
	q->front = next(q->front, MAX);
	return ret;
}

다음은 큐가 front의 위치의 데이터를 삭제하고 위치를 옮긴 것을 표현한 그림입니다.

이제 큐의 데이터를 삽입하는 QEnqueue 함수 입니다. QEnqueue는 QDequeue와 반대로 먼저 큐가 꽉 차 있는지 확인하고, 현재 rear에 데이터를 넣습니다. 그 후 rear의 next(rear, MAX) 로 옮깁니다. 그러면 끝입니다.

void QEnqueue(Queue * q, T data) {
	assert(QIsFull(q) == false);
	q->arr[q->rear] = data;
	q->rear = next(q->rear, MAX);
}

다음은 큐에 데이터를 넣었을 때를 표시한 그림입니다.

4. C++로 바꿔보기

3절 C코드를 C++로 변경하면 다음과 같습니다.

Queue.hpp

#pragma once;

#include<cassert>

const int MAX = 5;

template<class T> class Queue {
private:
	T arr[MAX];
	int front;
	int rear;
	int capacity;

	int next(int idx) {
		return (idx + 1) % capacity;
	}

public:
	Queue() : front(0), rear(0), capacity(MAX) {}
	~Queue() {}

	bool isEmpty() {
		return this->front == this->rear;
	}

	bool isFull() {
		return next(this->rear) == this->front;
	}

	T peek() {
		assert(this->isEmpty() == false);
		return this->arr[this->front];
	}

	T dequeue() {
		assert(this->isEmpty() == false);
		T ret = this->arr[this->front];
		this->front = next(this->front);
		return ret;
	}

	void enqueue(T data) {
		assert(this->isFull() == false);
		this->arr[this->rear] = data;
		this->rear = next(this->rear);
	}
};

5. 결론

큐 정리

우리는 이번 시간에 큐의 모든 연산을 C로 구현해보고 동작 과정을 살펴 본 후 C++로 구현함으로써 큐를 이해하게 되었습니다. 어떤가요? ㅎㅎ 큐는 처음에 들어온 데이터가 가장 처음에 나가는 FIFO 구조라는 것을 잊지 말아주세요. 여기서는 동작 과정에 초첨을 두었기 때문에, 배열 리스트, 연결 리스트 기반으로 스택을 만들지는 않았습니다. 이를 직접 구현해보는 것도, 좋은 공부가 될 것입니다. 마지막으로 저는 제가 풀이한 큐 관련 문제들의 URL을 남기고 이만 물러갈까 합니다. 제 문제 풀이를 보기 전에 문제 URL로 접속하셔서 먼저 문제를 풀고 풀이를 봐주세요! 그럼 큐란 자료구조의 응용법도 손쉽게 터득할 수 있으실 겁니다.

• 알고스팟 JOSEPHUS 풀이
• 알고스팟 ITES 풀이