큐(Queue)

큐란? 

큐(Queue)는 사전적인 정의로 '긴 열', '대기열'를 뜻한다. 길게 늘어져 있는 줄을 생각하면 편하다.

 

큐(Queue)는 일상생활에서도 자주 접하게 된다. 예를 들면 극장에서 표를 사려고 길게 늘어진 사람들의 줄, 또는 도로 위에서 신호를 기다리며 길게 늘어선 차들 등이 있다. 이러한 대기열에는 한 가지 중요한 특징을 가지고 있다. 그것은 바로 '선입선출(First-In First-Out : FIFO)'이다. 새치기라는 예외적인 상황을 제외하고 정상적인 경우라면 언제나 먼저 도착한 사람이 먼저 나가게된다.

일반적인 줄서기 상황

자료구조에 사용되는 큐는 이러한 줄 서기의 특징을 그대로 가지고 있다. 큐는 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터가 나오는 자료구조이다. 먼저 저장된 데이터가 나중에 저장된 데이터보다 항상 앞서 나오기 때문에 큐는 FIFO 특성을 지닌다고 말한다. 

 

큐는 또한 리스트와 스택처럼 선형 자료구조이다. 큐에 저장된 자료들 사이의 선후 관계가 모두 일대일(1:1)이다. 즉, 자료의 줄을 세우는데, 큐에 있는 모든 자료는 각각 자신의 앞에도 1개의 자료만 있고, 뒤에도 1개의 자료만 있다.

 

큐가 선입선출 특성을 가지는 이유는 다음과 같은 제약 사항 때문에 가능하다. 큐에서의 자료 변환은 큐의 제일 앞(front, 프런트)에서만 가능하고 자료 추가는 큐의 제일 끝(rear, 리어)에서만 가능하다. 이러한 제약 사항은 자연스럽게 큐를 선입선출의 특성을 갖게 한다. 큐를 이용하면 선입선출의 특성을 갖는 다양한 현실 세계를 효과적으로 표현할 수 있게 된다.

 

---

큐의 활용

큐의 특성 덕분에 먼저 온 요청의 서비스를 먼저 제공하는 방식으로 큐는 다양하게 활용되고 있다. 예를 들면 운영체제에서 CPU의 연산 처리시 여러 작업이 대기 하는 경우 대기중인 프로그램 먼저 대기중이거나 스케쥴러에 의해 우선순위가 높은 프로그램부터 처리한다.

 

프린터의 출력 요청 또한 큐를 사용한다. 먼저 출력 요청이 들어온 순서대로 출력 작업을 진행한다. 그리고 서버 요청시에도 마찬가지로 큐를 사용한다. 먼저 요청이 온 패킷 순서대로 서버에서 처리한다. 

 

---

큐의 구현

배열을 이용하는 방법과 연결리스트를 이용하는 방법이 있다. 두가지 모두 구현해보자.

 

구조

큐 구현에 앞서 우선 어떤 구조로 구현할 것인지부터 알아보겠다. 

Queue Abstract 클래스는 큐의 추상자료형을 순수 가상함수로 선언해놓은 부모 클래스이다. 어떻게 구현할 것인가에 따라 Array Queue 클래스와 Linked List Queue 클래스로 나뉘고 모두 Queue Abstract 클래스를 상속받는다. 그리고 UI에서 메뉴와 사용자 입력에 따른 큐의 기능처리 작업을 한다. 

 

데이터

기본적으로 큐에 들어갈 데이터의 내용은 다음과 같다.

// DataType.h

#pragma once

typedef struct _tagData
{
	int number;
public:
	_tagData() {}
	_tagData(int num)
	{
		number = num;
	}
}DATA;

간단하게 숫자만 저장하는 데이터 구조체이다.

 

매크로

동적 할당을 하기 때문에 할당 해제를 반드시 해줘야 한다. 동적 할당 해제를 편하고 안전하게 할 수 있도록 매크로 함수를 만들었다.

// Macro.h

#pragma once

template<typename T>
void SAFE_DELETE(T*& value)
{
	if (nullptr != value)
	{
		delete value;
		value = nullptr;
	}
}

template<typename T>
void SAFE_DELETE_ARRAY(T*& value)
{
	if (nullptr != value)
	{
		delete[] value;
		value = nullptr;
	}
}

미리 컴파일 된 헤더는 다음과 같다.

// pch.h

#ifndef PCH_H
#define PCH_H

// TODO: 여기에 미리 컴파일하려는 헤더 추가
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

#include "TypeData.h"
#include "Macro.h"

#endif //PCH_H

앞서 봤던 헤더들을 #include 시켜 모든 위치에서 쓸 수 있도록 하였다.

 

UserInterface 클래스

// UserInterface.h

#pragma once
#include "Queue_Abstract.h"
class UserInterface
{
public:
	UserInterface();
	~UserInterface();
public:
	void Logic();
private:
	void PrintMenu();
	int  InputProcess();
private:
	Queue_Abstract* m_Queue = nullptr;
};

UserInterface 클래스는 콘솔 창에 메뉴를 띄우고 큐를 구현 종류에 맞게 동적할당하여 사용자가 원하는 기능들을 메서드 호출 하는 작업을 한다. (큐의 기능과 사용을 캡슐화)

// UserInterface.cpp

#include "pch.h"
#include "UserInterface.h"
#include "Queue_Array.h"
#include "Queue_LinkedList.h"

UserInterface::UserInterface()
{
	m_Queue = new Queue_LinkedList;
			// 혹은 new Queue_Array;
}

UserInterface::~UserInterface()
{
	SAFE_DELETE<Queue_Abstract>(m_Queue);
}

void UserInterface::Logic()
{
	while (true)
	{
		PrintMenu();
		if (-1 == InputProcess())
			return;
	}
}

void UserInterface::PrintMenu()
{
	cout << "=====================================================================" << endl;
	cout << "1.Enqueue  2.Dequeue  3.PeekFront  4.PeekRear  5.PrintAll  6.Exit" << endl;
	cout << "Select Number? ";
}

int UserInterface::InputProcess()
{
	int input = 0;
	cin >> input;

	DATA data;
	switch (input)
	{
	case 1:
	{
		cout << "데이터를 입력하세요? ";
		cin >> data.number;
		m_Queue->Enqueue(data);
		cout << "Enqueue 완료!" << endl;
		break;
	}
	case 2:
	{
		cout << "꺼낸 데이터" << endl;
		if (true == m_Queue->Dequeue(&data))
			cout << "Number : " << data.number << endl;
		else
			cout << "Empty!" << endl;
		break;
	}
	case 3:
	{
		cout << "Front 데이터" << endl;
		if (true == m_Queue->PeekFront(&data))
			cout << "Number : " << data.number << endl;
		else
			cout << "Empty!" << endl;
		break;
	}
	case 4:
	{
		cout << "Rear 데이터" << endl;
		if (true == m_Queue->PeekRear(&data))
			cout << "Number : " << data.number << endl;
		else
			cout << "Empty!" << endl;
		break;
	}
	case 5:
	{
		m_Queue->PrintAll();
		break;
	}
	case 6:
		return -1;
	}

	return 0;
}

 

Queue_Abstract 클래스

// Queue_Abstract.h

#pragma once
class Queue_Abstract
{
public:
	Queue_Abstract();
	virtual ~Queue_Abstract();
public:
	virtual void Enqueue(const DATA& data) = 0;
	virtual bool Dequeue(DATA* OutData) = 0;
	virtual void ClearAll() = 0;
	virtual void PrintAll() = 0;
	virtual bool PeekFront(DATA* OutData) = 0;
	virtual bool PeekRear(DATA* OutData) = 0;
	virtual bool IsEmpty() = 0;
};

Queue의 필수 기능들을 순수 가상함수로 가지고 있다. 앞으로 구현될 Queue 클래스들은 부모로 이 클래스를 상속받아 필수 기능들을 오버라이딩한다. Peek를 이용하면 Front와 Rear의 데이터를 볼 수 있다.

 

 

1. 배열을 이용한 구현

배열을 사용하면 쉽게 접근이 가능하고 구현이 쉽다는 장점이 있지만 배열크기를 컴파일 시점에서 정해야 하는 단점이 존재한다. 그래서 배열 크기를 Enqueue, Dequeue시 조건을 만족한다면 확장하거나 축소하는 재할당 작업을 하도록 구현한다.

Enqueue시 재할당

Dequeue시 재할당

Queue_Array 클래스

// Queue_Array.h

#pragma once
#include "Queue_Abstract.h"

// 재할당 기준
const int UNIT = 2;

class Queue_Array
	: public Queue_Abstract
{
public:
	Queue_Array();
	virtual ~Queue_Array();

public:
	virtual void Enqueue(const DATA& data);
	virtual bool Dequeue(DATA* OutData);
	virtual void ClearAll();
	virtual void PrintAll();
	virtual bool PeekFront(DATA* OutData);
	virtual bool PeekRear(DATA* OutData);
	virtual bool IsEmpty();

private:
	// 재할당 함수
	void ChangeSize(int size);

private:
	// 큐를 사용할 배열
	DATA* m_Array = nullptr;
	// 재할당을 도와줄 배열
	DATA* m_ForSwap = nullptr;
    
	// m_Array의 사이즈
	int m_Size = 0;

	int m_Front = 0;
	int m_Rear = 0;
};

 

// Queue_Array.cpp

#include "pch.h"
#include "Queue_Array.h"

Queue_Array::Queue_Array()
{
	m_Size = UNIT;
	m_Array = new DATA[m_Size];
	memset(m_Array, 0, sizeof(DATA) * m_Size);
}

Queue_Array::~Queue_Array()
{
	ClearAll();
	SAFE_DELETE_ARRAY<DATA>(m_ForSwap);
}

void Queue_Array::Enqueue(const DATA & data)
{
	// 추가 후 사이즈가 배열 사이즈를 넘는다면
	if ((m_Rear + 1) - m_Front > m_Size)
	{
		// 배열 확장
		ChangeSize(+UNIT);
	}

	m_Array[m_Rear] = data;
	++m_Rear;
}

bool Queue_Array::Dequeue(DATA* OutData)
{	
	// 비어 있거나 데이터 return;
	if (true == IsEmpty())
		return false; 

	bool changeCheck = false;
	// 삭제 후 사이즈가 일정 크기만큼 작아진다면
	if (m_Rear - (m_Front + 1) <= m_Size - UNIT)
	{
		// 배열 축소
		changeCheck = true;
	}

	if(nullptr != OutData)
	{
		*OutData = m_Array[m_Front];
	}
	++m_Front;

	if(true == changeCheck &&
		false == IsEmpty())
		ChangeSize(-UNIT);
	
	return true;
}

void Queue_Array::ClearAll()
{
	m_Front = 0;
	m_Rear = 0;
	SAFE_DELETE_ARRAY<DATA>(m_Array);
}

void Queue_Array::PrintAll()
{
	if (true == IsEmpty())
	{
		cout << "Empty!" << endl;
		return;
	}

	int index = m_Front;
	int num = 0;

	while (m_Rear > index)
	{
		printf("[%d] - %d\n", num, m_Array[index].number);
		++index;
		++num;
	}
}

bool Queue_Array::PeekFront(DATA * OutData)
{
	if (true == IsEmpty())
		return false;
	if (nullptr != OutData)
		*OutData = m_Array[m_Front];
	return true;
}

bool Queue_Array::PeekRear(DATA * OutData)
{
	if (true == IsEmpty())
		return false;
	if (nullptr != OutData)
		*OutData = m_Array[m_Rear - 1];
	return true;
}

bool Queue_Array::IsEmpty()
{
	return (m_Front == m_Rear);
}

void Queue_Array::ChangeSize(int size)
{
	m_ForSwap = new DATA[m_Size];
	memset(m_ForSwap, 0, sizeof(DATA) * m_Size);
	memcpy(m_ForSwap, m_Array, sizeof(DATA) * m_Size);

	SAFE_DELETE_ARRAY(m_Array);
	m_Array = new DATA[m_Size + size];
	memset(m_Array, 0, sizeof(DATA) * (m_Size + size));

	// size를 축소하는 경우
	if (0 > size)
	{
		int index = 0;
		// ForSwap 정보를 배열로 옮길때 데이터를 땡긴다.
		// 재할당 받은 배열의 0번째 인덱스부터 데이터를 넣는다.
		for (int i = m_Front; i < m_Rear; ++i)
		{
			m_Array[index] = m_ForSwap[i];
			++index;
		}
		m_Rear -= m_Front;
		m_Front = 0;
	}
	// size를 확장하는 경우
	else
	{
		memcpy(m_Array, m_ForSwap, sizeof(DATA) * m_Size);
	}

	SAFE_DELETE_ARRAY(m_ForSwap);
	m_Size += size;

	cout << "Current Size : " << m_Size << endl;
}

 

2. 연결리스트를 이용한 구현

연결리스트를 사용하면 데이터 크기에 대한 제한이 없다는 장점이 있지만, 구현이 상대적으로 어렵다는 단점이 있다. 

Front와 Rear Node는 각자 알맞은 위치의 Node를 가리키고 있어야 한다. Enqueue시 Rear Node의 다음에 새로 추가하는 Node가 오고 Rear는 그 Node를 가리킨다. Dequeue시 Front의 Node가 삭제되고 Front는 그 Node의 다음 Node를 가리킨다. 만약 둘다 가리키는 링크가 없는 경우에는 Queue가 비어있는 것이다.

 

노드는 다음과 같다.

// DataType.h
#pragma once

typedef struct _tagNode
{
	DATA	   data;
	_tagNode*  link;
}NODE;

 

Queue_LinkedList 클래스

// Queue_LinkedList.h

#pragma once
#include "Queue_Abstract.h"

class Queue_LinkedList
	: public Queue_Abstract
{
public:
	Queue_LinkedList();
	virtual ~Queue_LinkedList();
public:
	virtual void Enqueue(const DATA& data);
	virtual bool Dequeue(DATA* OutData);
	virtual void ClearAll();
	virtual void PrintAll();
	virtual bool PeekFront(DATA* OutData);
	virtual bool PeekRear(DATA* OutData);
	virtual bool IsEmpty();
private:
	NODE m_Front;
	NODE m_Rear;
};

연결리스트에서 Enqueue와 Dequeue를 위해 Front, Rear Node를 멤버변수로 선언하였다.

// Queue_LinkedList.cpp

#include "pch.h"
#include "Queue_LinkedList.h"

Queue_LinkedList::Queue_LinkedList()
{
	// Node를 초기화
	memset(&m_Front, 0, sizeof(NODE));
	memset(&m_Rear, 0, sizeof(NODE));
}

Queue_LinkedList::~Queue_LinkedList()
{
	ClearAll();
}

void Queue_LinkedList::Enqueue(const DATA & data)
{
	NODE* newNode = new NODE;
	newNode->data = data;
	newNode->link = nullptr;

	// 만약 큐가 비어있는 경우
	if (nullptr == m_Rear.link ||
		nullptr == m_Front.link)
	{
		// Front와 Rear가 모두 newNode를 가리킨다.
		m_Front.link = newNode;
		m_Rear.link = newNode;
	}
	else
	{
		// newNode는 Rear가 가리키는 노드 다음에 오고
		// Rear는 newNode를 가리키게된다.
		m_Rear.link->link = newNode;
		m_Rear.link = newNode;
	}
}

bool Queue_LinkedList::Dequeue(DATA * OutData)
{
	if(true == IsEmpty())
		return false;

	NODE* delNode = nullptr;
	if (nullptr != OutData)
		*OutData = m_Front.link->data;

	// 삭제할 Node는 Front가 가리키고 있다.
	delNode = m_Front.link;
	// Front가 그 다음 Node를 가리키도록 한다.
	m_Front.link = m_Front.link->link;

	// Node를 삭제한다.
	SAFE_DELETE<NODE>(delNode);

	return true;
}

void Queue_LinkedList::ClearAll()
{
	if (true == IsEmpty())
		return;

	NODE* delNode = nullptr;

	while (false == IsEmpty())
	{
		delNode = m_Front.link;
		m_Front.link = m_Front.link->link;
		SAFE_DELETE<NODE>(delNode);
	}
}

void Queue_LinkedList::PrintAll()
{
	NODE* Node = m_Front.link;

	int num = 0;
	while (nullptr != Node)
	{
		printf("[%d] - %d\n", num, Node->data.number);
		Node = Node->link;
		++num;
	}
}

bool Queue_LinkedList::PeekFront(DATA * OutData)
{
	if (true == IsEmpty())
		return false;
	if (nullptr != OutData)
		*OutData = m_Front.link->data;
	return true;
}

bool Queue_LinkedList::PeekRear(DATA * OutData)
{
	if (true == IsEmpty())
		return false;
	if(nullptr != OutData)
		*OutData = m_Rear.link->data;
	return true;
}

bool Queue_LinkedList::IsEmpty()
{
	return (nullptr == m_Front.link ||
			nullptr == m_Rear.link);
}

 

Main()

#include "pch.h"
#include "UserInterface.h"

int main()
{
	UserInterface ui;
	ui.Logic();
}

UserInterface 클래스에 캡슐화 해둔 덕분에 인스턴스를 만들고 Logic() 메서드만 호출해주면 된다.

 

출력 값