[자료구조] 연결형 큐(Linked List + Queue) 개념과 구현(C++소스)

연결형 큐

큐를 링크드리스트 형태로 구현할 수 있습니다. 스택에서처럼 말이죠. 스택과는 다르게 큐는 front와 rear가 있기 때문에 큐는 두개의 노드를 갖고 있어야합니다.

아래 그림처럼 말이죠.

큐의 특징은 알아보았으니(또는 이미 알고있거나) 어떻게 구현을 할 지 생각해보도록 합시다.

구현

이제 Node라는 구조체 변수를 갖는 LinkedQueue를 구현해보겠습니다. 하나하나 차근차근히요.

Node구조체는 아래와 같습니다. data와 다음 노드를 가리키기 위한 next변수를 가지고 있지요.

struct node {
	int data;
	struct node *next;
};

이제 LinkedQueue를 간단하게 정의해보지요.

struct LinkedQueue {
	Node *front, *rear;
	int len;
	LinkedQueue() {
		front = rear = NULL;
                len=0;
	}
};

구조체의 초기값을 정합니다. front와 rear를 갖고 있고 이 둘은 처음에는 가리키는 노드가 없으니까 NULL이 됩니다. 그리고 길이 역시 0입니다.

우리는 이제 size, isEmpty, enqueue, dequeue 4개의 연산을 구현해보도록 할겁니다. 링크드리스트로 구현하는 형태이기 때문에 그 크기가 가변적입니다. 그렇기 때문에 isFull연산은 없습니다.

1. size

뭐 간단하죠? 그냥 len만 반환하면 되니까요.

int size() {
	return len;
}

2. isEmpty

간단합니다. len이 0이면 그냥 비어있는 겁니다. 바로 이해할겁니다. 허나, front로도 구할 수 있습니다. front는 이제 꺼내야될 노드를 가리키는 녀석입니다. front가 NULL이라면 꺼낼 노드가 없게 되니까 큐가 비어있는 상태로 보면 되겠죠. 

코드는 아래와 같습니다. 주석을 해제하고 같은 결과가 나오는지 확인해보세요.

bool isEmpty() {
	//return front == NULL;
	return len == 0;
}

3. enqueue

큐에 노드를 집어 넣습니다. 일단 큐가 비어있다면 front와 rear는 처음 들어오는 노드를 가리킵니다.

하지만 큐가 비어있지 않는다면 rear을 이용해야합니다. rear의 다음 노드(rear->next)가 새로 들어온 노드가 됩니다. 이후 rear을 새로 들어온 노드로 가리키면 되는 것이죠.

큐에 데이터가 추가되었으니 길이는 하나 증가합니다.

void enqueue(int data) {
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = NULL;
	if (isEmpty()) {
		front = rear = node;
	}
	else {
		rear->next = node;
		rear = rear->next;
	}
	len++;
}

4. dequeue

큐에서 하나 꺼내는 연산인데요. 어디서 꺼내느냐. front가 가리키는 노드를 꺼내면 됩니다. 아참, 그전에 큐가 비어있는지 확인하는게 먼저겠죠. 큐에 내용이 있다면 front노드의 데이터를 하나 꺼내고, 임의로 node라는 포인터를 써 front가 가리키는 노드를 같이 가리키게 합니다. 그 이후 front->next로 front를 다음 노드로 가리킵니다. 그리고 메모리를 해제하면 됩니다. 

큐에서 데이터가 삭제됐으니 길이는 줄겠죠?

int dequeue() {

	if (isEmpty()) {
		cout << "Q is empty" << endl;
		return INF;
	}
	Node *delNode = front;
	int ret = delNode->data;
	front = delNode->next;
	free(delNode);
	len--;
	return ret;
}

전체코드

이제 전체코드를 보도록 해요. 메인에서는 큐에 1부터 5까지 삽입하고 다시 10을 삽입합니다. 결과는 어떻게 될까요?

#include <iostream>
#define INF 987654321
using namespace std;
struct Node {
	int data;
	Node *next;
};

struct LinkedQueue {
	Node *front, *rear;
	int len = 0;
	LinkedQueue() {
		front = rear = NULL;
	}
	int size() {
		return len;
	}

	bool isEmpty() {
		return len ==0;
	}

	void enqueue(int data) {
		Node *node = (Node*)malloc(sizeof(Node));
		node->data = data;
		node->next = NULL;
		if (isEmpty()) {
			front = rear = node;
		}
		else {
			rear->next = node;
			rear = rear->next;
		}
		len++;
	}

	int dequeue() {
		
		if (isEmpty()) {
			cout << "Q is empty" << endl;
			return INF;
		}

		Node *delNode = front;
		int ret = delNode->data;
		front = delNode->next;
		free(delNode);
		len--;
		return ret;
	}
};

int main() {
	
	LinkedQueue q;
	for (int i = 1; i <= 5; i++)
		q.enqueue(i);

	q.enqueue(10);

	while (!q.isEmpty()) 
		cout << q.dequeue() << endl;
	
}

원하는 대로 결과가 나왔나요?

여기까지 큐를 링크드리스트로 구현하는 방법을 알아보았습니다. 링크드리스트로 구현한 큐이든, 선형큐이든 항상 무슨 프로그램을 구현할 것인지 고려하여 쓰기 바랍니다.