[자료구조] 큐(Queue) 개념, 원형 큐로 직접 구현해보기 C++

1. 큐(Queue) 란?

큐는 한쪽은 데이터가 나오기만 하고 한쪽은 들어가기만 하는 형태의 자료구조이다.

대표적인 예시로 놀이공원 줄 서기를 생각하면 된다. 내 앞의 사람들이 입장해야 내가 들어갈 수 있다.

이런 줄 서기 구조를 FIFO : First-In-First-Out (먼저 온 사람이 먼저 나감)이라고 한다.

이미지 출처 : https://medium.com/@1991dharapatel

 

2. 원형 큐

연결리스트로도 큐를 구현할 수 있지만 필자는 동적 배열을 사용하여 큐를 구현할 것이다.

배열로 큐를 구현하는 방법은 다양하지만 큐를 효율적으로 구현하기 위해 알아야 할 중요 로직이 존재한다.

몇 가지 방법을 소개하고 가장 효율적인 방법에 대해 설명하겠다.

 

방법 1. 

큐에 값이 빠져나가도 앞의 공간은 내버려 두고 새로운 값을 추가할 때마다 동적배열을 늘려준다.

이 방법은 앞에 안 쓰는 공간이 많은 데도 메모리를 증가시켜야 하는 비효율적인 문제가 발생한다. 따라서 좋은 방법이 아니다.

 

방법 2.

위 방법 1에서 앞에 비어있는 공간으로 A B를 앞당긴다.

그러나 채워진 데이터가 매우 많을 때 옮기는 과정이 매우 오래 걸리고 로직이 하나 더 추가되는 꼴이다. 따라서 이 또한 좋은 방법이 아니다.

 

🔑 방법 3 🔑

위와 같이 A, B, C, D로 찬 큐에서 A, B가 나가고 새로 E가 들어가는 시나리오이다.

이 방법은 새로운 E가 들어올 때 배열을 늘리지 않고 앞에 빈 공간으로 E를 넣어준다.

방법 3이 바로 배열을 원형처럼 잇는 것이다. 시작과 끝이 정해져 있는 것이 아닌 이어져 있다.

📌원형 배열 : 마지막 인덱스와 첫 인덱스가 이어진 구조📌

원형 큐 이미지, 출처:https://velog.io/@angel_eugnen/

 

이러면 컴퓨터가 어디가 앞이고 뒤인지 모르기 때문에 front, rear 변수로 큐의 앞, 뒤를 나타낸다.

front : 큐의 첫 요소 바로 앞의 인덱스를 저장

rear : 큐의 마지막 요소의 인덱스를 저장

 

원형 큐 사용에 따른 front, rear의 변화

- 큐가 비었을 때

front_ == rear_라면 큐는 비어있음을 의미한다.

 

 

- 큐에 값이 하나 들어갈 때

만약 새로운 값이 추가된다면 rear을 +1 시키고 해당 위치에 값을 저장한다.

 

 

- 큐에 값이 하나 빠질 때

front를 +1 한다

 

 

- rear가 배열의 마지막 인덱스인 경우 다음값 저장은?

rear = (rear + 1) % capacity

여기서 모듈러 연산(%)을 활용해 rear를 설정한다.

배열의 크기로 나누었을 때의 나머지를 인덱스로 계속 설정한다.

다음 rear가 4가 되어야 하는데 큐에 인덱스 4는 없기 때문에 4(rear + 1) 나누기 4(capacity)의 나머지 0의 위치에 값을 저장한다.

 

5. 만약 큐가 꽉 찼다면 capacity를 두배로 늘란다

 

 

3. c++ 동적배열로 원형 큐 구현

큐 클래스 메서드 설명

Queue class 구조

queue.h로 사용할 수 있게 만들었다.

아래 형식만 보고 직접 구현해 본다면 정말 좋은 경험이 될 것이다.

큐 클래스에서 사용하는 용어

먼저 큐에 값을 넣는 것 : enqueue    <- push라고도 함

큐에서 값을 빼는 것 : dequeue     <- pop이라고도 함

#pragma once

#include <cassert>
#include <iostream>

template<typename T>
class Queue
{
public:
	Queue(int capacity=2){}

	~Queue() {}

	bool IsEmpty() const {}

	bool IsFull() const {}

	T& Front() const {}

	T& Rear() const {}

	int Size() const {}
    
	void Resize() {}

	void Enqueue(const T& item) {}

	void Dequeue() {}

	void Print() {}

protected: // 뒤에서 상속해서 사용
	T* queue_; // array for queue elements
	int front_ = 0; // 시작 인덱스보다 하나 작은 값
	int rear_ = 0; // 마지막 인덱스 (첫 값은 1에 추가)
	int capacity_; // 빈 칸을 하나 둬야 하기 때문에 필요 메모리는 최대 저장량 + 1
};

 

생성자 / 소멸자

생성자 : 큐 생성 시 생기는 동적배열의 기본값은 2로 설정, 필요에 따라 capacity는 변경 가능하다.

소멸자 : 큐에 동적할당받은 배열을 모두 반납한다.

	Queue(int capacity=2)
	{
		assert(capacity > 0);

		capacity_ = capacity;
		queue_ = new T[capacity_];
		front_ = rear_ = 0;
	}

	~Queue()
	{
		if (queue_) delete[] queue_;
	}

 

Enqueue(), Dequeue()

Enqueue : 매개변수로 받은 item을 rear_를 +1 증가시키고 모듈러 연산을 한 인덱스에 값을 저장

만약 큐가 꽉 찬 상태에서 Enqueue를 한다면 동적 배열을 두배로 만드는 Resize()를 수행하고 Enqueue 한다.

Dequeue : front_를 하나 증가시키고 모듈러 연산을 한다. 제일 앞의 요소를 더 이상 가리키지 않게 함

위에서 설명했지만 모듈러 연산을 하는 이유는 배열의 끝이 지정되어 있지 않은 원형으로 생각하기 때문이다.
front, rear가 배열의 마지막 인덱스일 때 증가 시키면 접근 가능 인덱스 값을 초과한다.
그러나 모듈러 연산을 적용하면 0으로 돌아간다!! 이로써 원형으로 값을 저장하고 뺀다.

void Enqueue(const T& item) // 큐의 뒤에 추가, Push()
{
	if (IsFull())
		Resize();
	
	rear_ = (rear_+1) % capacity_;
	queue_[(rear_)] = item;

}

void Dequeue() // 큐의 첫 요소 삭제, Pop()
{
	assert(!IsEmpty());
	front_= (front_+1) % capacity_;
}

 

Front(), Rear()

큐의 제일 앞 요소와 제일 뒤 요소 return 하는 함수이다.

Front() : Front_는 제일 앞의 요소 한 칸 앞의 인덱스를 가리키는  Front_+1의 위치의 값을 return 한다.

Rear() : Rear_는 제일 뒤 요소의 인덱스를 가리키므로 Rear_를 return 한다.

	T& Front() const 
	{
		assert(!IsEmpty());
		return queue_[(front_ + 1) % capacity_];
	}

	T& Rear() const
	{
		assert(!IsEmpty());
		return queue_[rear_];
	}

 

IsFull(), IsEmpty

앞서 원형 큐의 구조를 설명했듯이

IsEmpty() : Front_와 Rear_가 같다면 빈 큐

IsFull() : Rear_가 하나 증가할 때 Front_와 같아진다면 꽉 찬 큐

	bool IsEmpty() const
	{
		return front_ == rear_;
	}

	bool IsFull() const
	{
		return (rear_ + 1) % capacity_ == front_;
	}

 

Size()

큐에 들어있는 원소의 개수를 반환해 주는 함수이다.

원형 큐 구조이기 때문에 rear_ - front_만을 구할 수 없다. rear_가 인덱스가 더 작은 경우도 존재하기 때문이다.

따라서 rear_가 front_ 보다 큰지 작은지에 따라 나누어 계산해야 한다.

만약 rear_ > front_인 경우는 rear_에 현재 동적배열의 크기를 더해준 다음 front_를 빼준다.

ex) 위 사진과 같은 경우 capacity =4

size는 0 + 4 - 1 = 3이다.

	int Size() const
	{
		if (front_> rear_)
			return rear_ + capacity_ - front_;
		else
			return rear_ - front_;
		return 0;
	}

 

Resize()

큐가 꽉 차서 함수가 호출되면 큐를 가리키는 동적배열의 크기를 두배로 늘려준다.

새로운 동적 배열에 기존 배열의 값을 복사하는 과정에서front_와 rear_가 인덱스 순이 아니기 때문에 0부터 그냥 채울 수 없다!! 

ex) rear_가 front_보다 더 작은 경우도 있음

따라서 front_의 모둘러 값이 rear_의 모둘러 값이 되기 전까지 front_를 +1 & 모듈러 연산 한 값만큼 증가시키며 반복하여 새로운 배열에 값을 채운다.

void Resize() // 2배씩 증가
{
	T* newQueue = new T[capacity_*2];
	int index = 1;
	for (int i = (front_ + 1) % capacity_; i != (rear_ + 1) % capacity_; i = (i + 1) % capacity_)
	{
		newQueue[index++] = queue_[i];
	}
	delete[] queue_; 
	
	front_ = 0;
	rear_ = capacity_ - 1;
	capacity_ *= 2;
	queue_ = newQueue;
}

채운 이후 기존 동적배열 제거,  front_, rear_, capacity, queue 재설정

 

 Print()

Resize()에서 원형 큐의 순회에 대해서 다루었다. print()는 Resize() 반복문에서 출력 기능만 해주면 된다.

 

4. 전체코드

아래 더보기에 전체코드 있습니다.

#pragma once

#include <cassert>
#include <iostream>
#include <iomanip>

template<typename T>
class Queue // Circular Queue
{
public:
	Queue(int capacity=2)
	{
		assert(capacity > 0);

		capacity_ = capacity;
		queue_ = new T[capacity_];
		front_ = rear_ = 0;
	}

	~Queue()
	{
		if (queue_) delete[] queue_;
	}

	bool IsEmpty() const
	{
		return front_ == rear_;
	}

	bool IsFull() const
	{
		return (rear_ + 1) % capacity_ == front_;
	}

	T& Front() const 
	{
		assert(!IsEmpty());

		return queue_[(front_ + 1) % capacity_];
	}

	T& Rear() const
	{
		assert(!IsEmpty());

		return queue_[rear_];
	}

	int Size() const
	{
		if (front_> rear_)
			return rear_ + capacity_ - front_;
		else
        	return rear_ - front_;
		return 0;
	}

	void Resize()
	{
		T* newQueue = new T[capacity_*2];
		int index = 1;
		for (int i = (front_ + 1) % capacity_; i != (rear_ + 1) % capacity_; i = (i + 1) % capacity_)
		{
			newQueue[index++] = queue_[i];
		}
		delete[] queue_; 
		
		front_ = 0;
		rear_ = capacity_ - 1;
		capacity_ *= 2;
		queue_ = newQueue;
	}

	void Enqueue(const T& item)
	{
		if (IsFull())
			Resize();
		
		rear_ = (rear_+1) % capacity_;
		queue_[(rear_)] = item;

	}

	void Dequeue()
	{
		assert(!IsEmpty());
		front_= (front_+1) % capacity_;
	}
    	void Print()
	{
		using namespace std;

		for (int i = (front_ + 1) % capacity_; i != (rear_ + 1) % capacity_; i = (i + 1) % capacity_)
			cout << queue_[i] << " ";
		cout << endl;
	}
}
protected: 
	T* queue_;
	int front_ = 0;
	int rear_ = 0; 
	int capacity_; 
	bool print_debug_ = false;
};