'자료구조 큐'에 해당되는 글 1건

연결형 큐


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


아래 그림처럼 말이죠.




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




구현

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

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


1
2
3
4
struct node {
    int data;
    struct node *next;
};

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

1
2
3
4
5
6
7
8
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만 반환하면 되니까요.

1
2
3
int size() {
    return len;
}


2. isEmpty

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


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

1
2
3
4
bool isEmpty() {
    //return front == NULL;
    return len == 0;
}




3. enqueue

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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
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를 다음 노드로 가리킵니다. 그리고 메모리를 해제하면 됩니다. 


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


1
2
3
4
5
6
7
8
9
10
11
12
13
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을 삽입합니다. 결과는 어떻게 될까요?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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;
     
}

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




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

반응형
블로그 이미지

REAKWON

와나진짜

,