연결형 큐
큐를 링크드리스트 형태로 구현할 수 있습니다. 스택에서처럼 말이죠. 스택과는 다르게 큐는 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;
}
원하는 대로 결과가 나왔나요?
여기까지 큐를 링크드리스트로 구현하는 방법을 알아보았습니다. 링크드리스트로 구현한 큐이든, 선형큐이든 항상 무슨 프로그램을 구현할 것인지 고려하여 쓰기 바랍니다.
'자료구조' 카테고리의 다른 글
| [자료구조] 그림으로 쉽게 보는 힙(Heap) 개념과 코드 (3) | 2018.12.01 |
|---|---|
| [자료구조] 트리 개념 및 순회 방법, 전위순회, 중위순회, 후위순회 (0) | 2018.11.04 |
| [자료구조] 큐(Queue)와 원형큐(Circular Queue) 개념과 구현 (1) | 2018.10.10 |
| [자료구조] 그림으로 쉽게 보는 연결형 스택 원리, 구현, 코드 (0) | 2018.10.09 |
| [자료구조] 그림으로 쉽게 보는 연결 리스트 (Linked List) 개념과 구현 (3) | 2018.10.04 |
REAKWON
와나진짜
