[자료구조] 큐(Queue)의 개념과 구현(2)

2022.07.11 - [자료구조&알고리즘] - [자료구조] 큐(Queue)의 개념과 구현(1)

[자료구조] 큐(Queue)의 개념과 구현(1)

지난 글에서는 단순한 형태의 큐에 대해서 알아보았다.

큐를 구현하는 방법은 크게 두 가지가 있는데

• 연결 리스트를 이용한 큐의 구현
• 배열을 이용한 큐의 구현

하나씩 알아보도록 하겠다.

---

연결 리스트를 이용한 큐의 구현

이중 연결 리스트를 이용하여, 새로 추가한 데이터를 리스트 맨 앞에 삽입하는 방식이다. 그림으로 보면 다음과 같은 구조를 가지고 있다.

이중 연결 리스트(Doubly linked list)를 이용한 큐의 구현

이러한 연결리스트를 이용한 큐의 구현에서는, enqueue와 dequeue를 연결 리스트의 node를 추가하고 삭제하는 방식으로 구현한다.

 

배열을 이용한 큐의 구현

미리 정해진 크기의 배열을 할당한 다음, 큐의 앞과 뒤를 나타내는 front와 rear변수를 사용하여 큐를 구현한다.

배열(array)를 이용한 큐의 구현

이 예시에서는 크기가 5인 배열을 할당하고, enqueue(30), enqueue(20), enqueue(10) 연산을 진행하였다.

데이터의 삽입이 일어날 경우, 배열에 차곡차곡 삽입한 다음, rear의 값을 1씩 증가시키는 방식으로 구현한다.

그렇다면 데이터의 삭제는 어떻게 구현할까?

배열을 이용한 큐의 구현에서의 데이터 삭제

데이터 자체를 삭제하는것이 아닌, 단순히 front값을 1 증가시켜서 dequeue를 구현한다. 

여기서 연결 리스트를 통한 구현과 차이점이 발생한다. 연결 리스트를 통한 구현에서는 데이터가 들어있는 노드를 삽입하고 삭제했다면, 배열을 통한 구현은 데이터를 삭제하지 않고 front와 rear값의 변화로 큐의 입출력을 구현한다.

 

그러나, 이러한 구조에는 한가지 문제점이 있는데, 데이터가 추가되고 삭제됨이 반복되면서 낭비되는 공간이 발생한다는 것이다.

그림과 함께 살펴보겠다.

 

배열을 이용한 큐의 문제점

위의 상황에서 enqueue(50)을 해보도록 하겠다.

 

rear값을 1 추가하고, 50을 삽입했다. 그러나, 앞서 dequeue된 30은 삭제되지 않고 그대로 남아있다. 이렇게 남아있는 데이터로 인해, 배열의 총 크기는 5이지만 최대 삽입할 수 있는 원소의 개수는 4개로 제한된다. 이는 dequeue를 추가적으로 진행하면 줄어들게 된다. 위의 상황에서 dequeue와 enqueue(60)을 진행해보겠다.

dequeue된 30과 20은 남아있기 때문에, 배열의 크기는 5이지만 현재 3개의 원소만 큐에 보관이 가능하다.

이처럼 배열을 이용하여 구현한 큐는, 데이터의 삽입과 삭제가 반복되면서 배열의 앞 부분에 무효화되는 공간이 발생한다는 문제점을 지니고 있다.

이러한 문제를 해결하기 위해 원형 큐(circular queue)라는 개념을 추가적으로 설명하겠다.

---

원형 큐(Circular queue)

원형 큐는 선형 큐와 마찬가지로 선입선출(FIFO)원칙을 따르고, 마지막 위치가 첫 번째 위치와 연결되는 자료구조이다.

다음의 예시를 보자.

원형 큐(Circular queue)

이해를 돕기 위해 원형의 구조로 예시를 만들어봤다.(실제로는 메모리가 원형은 아니다)

배열을 이용한 큐의 구현처럼, 데이터의 삽입은 rear값을 증가시키고 삭제는 front값을 증가시키는 방법으로 구현한다.

원형 큐가 어떻게 배열의 문제점을 보완해주는지 알아보기 위해 큐가 가득 찬 상태를 구현해보겠다.

다음의 상태는 위의 상태에서 dequeue 2번, 80까지의 데이터를 enqueue한 상태이다.

이 상태에서 enqueue(90)을 진행하면 어떻게 될까?

마지막 위치가 첫 번째 위치와 연결되어있기 때문에 첫 번째 위치로 rear가 이동됨과 동시에 데이터가 삽입됨을 볼 수 있다.

원형 큐의 이러한 특징은 앞서 말한 배열을 통한 큐의 구현의 단점을 보완해주는 역할을 한다.

그러나, 큐가 정말 다 찼는지 비어있는 공간이 있는지를 확인한 다음에 enqueue를 해야만 한다.

만약 이러한 상황에서 enqueue를 하게 된다면, 유효한 데이터를 삭제하는 것이 되어버리기 때문에, 현재 원소의 개수를 따로 저장하여 배열의 크기(capacity)와 비교한 다음, 큐가 가득 찼는지 아닌지를 확인한 후 연산을 진행해야 한다.

---

원형 큐의 구현

원형 큐의 구현은 다음과 같다.

 

#include <iostream>

#define MAXIMUM_QUEUE 8

template <class T>
class CircularQueue
{
private:
	T* arr;
	int front_index;
	int rear_index;
	int count; //현재 원소의 개수
	int capacity; // queue에 넣을 수 있는 원소의 개수
public:
	CircularQueue(int size = MAXIMUM_QUEUE) // 큐 초기화
	{
		arr = new T[size];
		front_index = 0;
		rear_index = -1; // 초기화 시 rear값은 -1 (원소가 추가되었을 때 front와 rear가 값은 값이기 위해)
		count = 0;
		capacity = size;
	}
	~CircularQueue()
	{
		delete [] arr; //동적 할당된 배열을 소멸자에서 해제
	}

	void enqueue(const T& element)
	{
		if(full()) // 큐가 가득 찬 상태에서 enqueue 진행 시 경고문구 출력과 종료
		{
			std::cout << "Overflow" << std::endl;
			return;
		}
		rear_index = (rear_index+1) % capacity; // rear가 원형 큐를 여러번 돌아도 첫 순환과 같은 위치를 가리키도록 함
		arr[rear_index] = element; // 원소 삽입
		count++; //원소 개수 추가
	}

	void dequeue()
	{
		if (empty()) // 큐가 비어있는 상태에서 dequeue 진행 시 경고문구 출력과 종료
		{
			std::cout << "Underflow" << std::endl;
			return;
		}

		front_index = (front_index + 1) % capacity; // front가 원형 큐를 여러번 돌아도 첫 순환과 같은 위치를 가리키도록 함
		count--;
	}

	const T& front() const 
	{
		return arr[front_index];
	}

	bool empty() const 
	{
		return count == 0;
	}

	int full() const 
	{
		return count == capacity;
	}

	int size() const
	{
		return count;
	}
};