7. 큐(Queue) -a. 연결 리스트 기반

큐

  # 큐는 영어로 줄이나 대기 행렬을 의미하는 단어로, 먼저 들어온 데이터가 먼저 빠져나가는 구조의 리스트이다.

  # 영어로는 'FIFO(First In First Out)' 혹은 'LILO(Last In Last Out)' 구조의 자료구조로 불린다.

  # 입구와 출구가 각각 있는 구조라고 생각하면 이해하기 편하다. (이때 입구로 나가거나, 출구로 들어오는건 불가능하다고 가정한다.)

  # 일반적으로 줄의 출구 즉 큐의 맨 앞을 Front, 줄의 입구 즉 큐의 맨 끝을 Rear라고 한다.

  # 일반적으로 큐에 데이터를 넣는 행위를 Enqueue 혹은 Add, 큐에서 데이터를 빼는 행위를 Dequeue 혹은 Remove라고 한다.

  # 큐도 배열이나 연결 리스트를 이용해서 구현할 수 있다. 

  # 하지만 큐를 배열로 구현할 시 거의 원형큐로 만드므로 이번에는 연결 리스트를 이용한 큐를 먼저 소개한다.

  

연결 리스트 기반 큐

  # 큐를 연결 리스트를 기반으로 만들 때는 Front 포인터와 Rear 포인터 두 개를 이용하는 것을 먼저 생각해 볼 수 있다.

  # 이렇게 하면 Add는 항상 Rear포인터를, Remove는 항상 Front 포인터를 이용하면 된다.

  # 포인터를 하나만 사용하고 싶다면 이때는 원형 연결 리스트를 이용해서 원형 큐를 만드는 것이 좋다.

  # 원형큐는 배열을 이용할 것이므로 여기서는 포인터 두개를 이용하여 만드는 큐를 소개한다.

  # 연결 리스트 기반 큐도 딱히 Overflow를 걱정할 필요는 없고, Underflow만 조심하면 된다.

연결 리스트 기반 큐의 ADT

  1. 큐에 데이터를 넣는다. (Add)

  2. 큐에서 데이터를 뺀다. (Remove)

  3. 큐 맨 앞의 데이터를 확인한다. (Peek)

  (데이터가 없을때 값을 확인하거나 제거하려 하면 컴파일 에러가 발생한다.)

  4. 큐에 들어있는 데이터의 개수를 확인한다. (Count)

C++로 구현한 연결 리스트 기반 큐

#pragma once

template <typename T>
class QueueList
{
	template <typename T>
	struct node {
		T data;
		node<T>* next;
	};

	node<T>* pFront;
	node<T>* pRear;

	int iCount;

public:
	int Add(T data);
	int Remove();
	T  Peek();
	int Count();

public:
	QueueList();
	virtual ~QueueList();
};

template <typename T>
QueueList<T>::QueueList()
{
	pFront = nullptr;
	pRear = nullptr;
	iCount = 0;
}


template <typename T>
int QueueList<T>::Add(T data)
{
	node<T>* newnode = new node<T>;
	newnode->data = data;
	newnode->next = nullptr;

	if (pRear != nullptr) {
		pRear->next = newnode;
	}
	else {
		pFront = newnode;
	}

	pRear = newnode;

	return ++iCount;
}

template <typename T>
int QueueList<T>::Remove()
{
	node<T>* pDel = pFront;
	pFront = pFront->next;
	delete pDel;

	return 	--iCount;
}

template <typename T>
T QueueList<T>::Peek()
{
	return pFront->data;
}

template <typename T>
int QueueList<T>::Count()
{
	return iCount;
}

template <typename T>
QueueList<T>::~QueueList()
{
	while (true) {
		if (!a.Remove()) {
			break;
		}
	}
}