원형이 아닌 직선으로!
이번엔 순환 큐(Circular Queue)가 아닌, 링크드 큐(Linked Queue)입니다. 링크드가 하니 링크드 리스트가 떠오르지 않나요? 비슷합니다. 링크드 큐의 노드에도 그 노드의 다음을 가리키는 주소 값을 가지고 있으며, 노드가 전단(Front) -> 후단(Rear) 방향으로 이어져 있습니다. 그래도 전단에서 제거 연산이 이루어진다는 것과, 후단에서 삽입 연산이 이루어진다는 것은 바뀌지 않습니다. 링크드 큐의 구현은 상당히 간단합니다. 링크드 큐는 삽입 연산 때는 후단 노드의 다음 노드에 새로 추가되는 노드를 넣고, 제거 연산 때는 전단의 위치를 앞으로 옮기면 됩니다. 한번 그림으로 보도록 합시다.
위의 그림을 보시면, 전단에 있는 노드를 제거했을 때 단순히 전단의 위치를 다음 노드로 넘기면 됩니다. 그러곤 그게 끝입니다. 삽입도 이와 비슷합니다. 후단의 nextNode에 새로 추가되는 노드의 주소 값을 넣고 새로 추가되는 노드를 후단 노드로 지정하면 됩니다. 참고로, 순환 큐와는 다르게 리스트 큐는 크기에 제한을 받지 않습니다. (크기가 유연함) 링크드 큐의 노드를 구조체로 정의해보도록 합시다.
typedef struct Node {
int data; // 데이터 필드
struct Node* nextNode; // 다음 노드를 가리키는 주소값
} Node;
순환 큐의 노드 구조체에선 데이터 필드밖에 없었지만, 링크드 큐에 와서는 다음 노드를 가리키는 주소값이 포함됩니다. 이번에는 LinkedQueue 클래스의 멤버 변수와 생성자, 소멸자를 살펴보도록 합시다.
class LinkedQueue {
private:
int size; // 큐의 크기
Node* front; // 전단의 주소값
Node* rear; // 후단의 주소값
public:
LinkedQueue()
{
size = 0; // 크기를 0으로 초기화 한다
front = NULL; // 전단의 주소값을 NULL로 초기화 한다
rear = NULL; // 후단의 주소값을 NULL로 초기화 한다
}
~LinkedQueue()
{
while(!isEmpty()) // 큐가 비어있지 않을때까지
{
Node* deq = dequeue(); // 전단에 존재하는 노드를 제거한다
delete deq; // 메모리 공간에서 deq를 해제한다
}
}
..
순환 큐와 비교하여 다른부분만 설명을 드리도록 하겠습니다. 전단의 주소 값, 후단의 주소 값을 담을 수 있는 노드 구조체의 포인터가 멤버로 선언되었습니다. LinkedQueue의 생성자에선 size와 front, rear의 초기화가 이루어지며 소멸자에서는 큐를 비우기 위해, 큐 내에 있는 노드를 모두 제거하고 메모리 공간에서 해제합니다. 이번에는 삽입(Enqueue) 메서드를 살펴보도록 합시다.
..
void enqueue(int data)
{
Node* newNode = new Node(); // 새로 노드를 추가한다
newNode->data = data; // 새로 추가된 노드의 데이터에 매개변수로 받은 데이터의 값을 대입한다
newNode->nextNode = NULL; // 다음 노드를 NULL로 초기화 한다
if (front == NULL) // 전단의 주소값이 NULL 이라면, 즉 처음 추가하는 것이라면
{
front = newNode; rear = newNode; // 전단의 주소값과 후단의 주소값은 새로 추가된 노드의 주소값
} else {
rear->nextNode = newNode; // 후단의 다음 노드를 새로 추가된 노드로 지정한다
rear = newNode; // 새로 추가된 노드를 후단으로 지정한다
}
size++; // 크기를 1 증가시킨다
}
..
위의 삽입 메서드를 살펴보면, 노드를 새로 추가하고 데이터를 집어넣습니다. 그리고 전단의 주소 값이 NULL이라면, 큐가 비어있음을 의미하겠죠? 이럴 경우 전단과 후단을 새로 추가된 노드로 지정하시면 됩니다. 만약, 처음 추가하는 게 아니라 한 개 이상 존재한다면 후단의 다음 노드를 새로 추가된 노드로 지정하고 새로 추가된 노드는 가장 뒤에 있는 노더니 후단 노드로 지정합니다. 이번엔 제거(Dequeue) 메서드를 보도록 합시다.
..
Node* dequeue()
{
Node* temp = front; // 전단의 주소값을 temp에 대입한다
if (front->nextNode == NULL) // 전단의 다음 노드가 NULL 인것은 노드가 하나 이하이다
{
rear = NULL; front = NULL; // 전단과 후단의 주소값을 NULL로 초기화한다
} else // 전단의 다음 노드가 존재한다면, 즉 노드가 두개 이상이라면
front = front->nextNode; // 전단의 다음 노드를 전단으로 지정한다
size--; // 크기를 1 감소시킨다
return temp; // 큐에서 제거된 전단의 주소값을 반환한다
}
..
위의 제거 메서드를 살펴보면, 임시 포인터를 하나 만들어서 전단의 주소값을 대입합니다. 그런 다음에 전단의 다음 노드가 NULL이면 노드가 하나 이하인 경우이므로, 후단과 전단에 각각 NULL을 대입하여 아무것도 가리키지 않게 합니다. 만약에, 다음 노드가 NULL이 아니라면 그건 두 개 이상의 노드가 큐에 존재하고 있다는 것으로, 전단의 다음 노드를 전단으로 지정하시면 됩니다. 이번엔 getSize 함수와 isEmpty 함수를 보도록 합시다. (isFull 함수는 링크드 큐에선 ‘꽉 찬다’라는 개념이 없기 때문에 제외하겠습니다.)
..
// 큐가 비어있는지 확인을 한다
bool isEmpty() { return front == NULL; } // 전단의 주소값이 NULL이라면, 즉 큐가 비어있다면 true 아닐 경우 false
int getSize() { return size; } // 큐의 크기를 가져온다
..
위의 isEmpty 함수는 전단의 주소값이 NULL일 경우, 즉 큐 내에 노드가 하나라도 없을 경우에는 true가 되며 하나 이상이 존재할 경우에는 false가 됩니다. getSize 함수는 size 변수의 값을 반환합니다. (size 변수는 큐 내에 존재하는 노드의 수를 말합니다) LinkedQueue 클래스는 모두 살펴보았으니, 전체 예제를 한번 살펴보도록 합시다.
예제보기
#include <iostream>
using namespace std;
typedef struct Node {
int data; // 데이터 필드
struct Node* nextNode; // 다음 노드를 가리키는 주소값
} Node;
class LinkedQueue {
private:
int size; // 큐의 크기
Node* front; // 전단의 주소값
Node* rear; // 후단의 주소값
public:
LinkedQueue()
{
size = 0; // 크기를 0으로 초기화 한다
front = NULL; // 전단의 주소값을 NULL로 초기화 한다
rear = NULL; // 후단의 주소값을 NULL로 초기화 한다
}
~LinkedQueue()
{
while(!isEmpty()) // 큐가 비어있지 않을때까지
{
Node* deq = dequeue(); // 전단에 존재하는 노드를 제거한다
delete deq; // 메모리 공간에서 deq를 해제한다
}
}
void enqueue(int data)
{
Node* newNode = new Node(); // 새로 노드를 추가한다
newNode->data = data; // 새로 추가된 노드의 데이터에 매개변수로 받은 데이터의 값을 대입한다
newNode->nextNode = NULL; // 다음 노드를 NULL로 초기화 한다
if (front == NULL) // 전단의 주소값이 NULL 이라면, 즉 처음 추가하는 것이라면
{
front = newNode; rear = newNode; // 전단의 주소값과 후단의 주소값은 새로 추가된 노드의 주소값
} else {
rear->nextNode = newNode; // 후단의 다음 노드를 새로 추가된 노드로 지정한다
rear = newNode; // 새로 추가된 노드를 후단으로 지정한다
}
size++; // 크기를 1 증가시킨다
}
Node* dequeue()
{
Node* temp = front; // 전단의 주소값을 temp에 대입한다
if (front->nextNode == NULL) // 전단의 다음 노드가 NULL 인것은 노드가 하나뿐이다
{
rear = NULL; front = NULL; // 전단과 후단의 주소값을 NULL로 초기화한다
} else // 전단의 다음 노드가 존재한다면, 즉 노드가 두개 이상이라면
front = front->nextNode; // 전단의 다음 노드를 전단으로 지정한다
size--; // 크기를 1 감소시킨다
return temp; // 큐에서 제거된 전단의 주소값을 반환한다
}
// 큐가 비어있는지 확인을 한다
bool isEmpty() { return front == NULL; } // 전단의 주소값이 NULL이라면, 즉 큐가 비어있다면 true 아닐 경우 false
int getSize() { return size; } // 큐의 크기를 가져온다
};
int main()
{
LinkedQueue lq;
int size;
// 데이터의 삽입과 제거
lq.enqueue(50);
lq.enqueue(60);
lq.dequeue();
lq.enqueue(80);
lq.enqueue(90);
lq.dequeue();
lq.enqueue(89);
// 큐의 크기를 가져온다
size = lq.getSize();
for(int i = 0; i < size; i++)
cout << "빠져나간 데이터: " << lq.dequeue()->data << endl;
return 0;
}
결과보기
빠져나간 데이터: 80 빠져나간 데이터: 90 빠져나간 데이터: 89 계속하려면 아무 키나 누르십시오 . . .
위의 예제에서, 메인 함수부터 살펴보면 “데이터 삽입 2번-> 데이터 제거 1번-> 데이터 삽입 2번-> 데이터 제거 1번-> 데이터 삽입 1번” 순으로 이루어지고 있습니다. 먼저, 50과 60이 큐에 들어오고, 50이 빠져나갑니다. 그런 다음 80과 90이 큐에 들어왔으니 60, 80, 90 이죠? 그 뒤에는 60이 빠져나가고 89가 새로 들어왔으니 80, 90, 89가 되는 것입니다. (순서대로 빠져나감) 링크드 큐를 직접 구현해보니 환형 큐에 비해 구조가 간단하죠? 링크드 큐는 구현이 간단하다는 장점 등이 있으나, 노드를 제거하거나 삽입할 때 new, delete 연산을 수행합니다. 반면에 환형 큐는 고성능인 반면에, 구현이 링크드 큐보다 복잡하다는 단점 등이 있습니다.