자료구조 큐를 C언어 연결 리스트로 구현하기

 

1. 연결 리스트, 큐 구조체 만들기

 

#include <stdio.h>
#include <stdlib.h>
#define INF 99999999

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct Queue {
    Node *front;
    Node *rear;
    int count;
} Queue;

 

Queue에는 front, rear, 그리고 큐에 들어가 있는 원소들의 개수를 count로 정했다. 

 

2. push 함수 구현하기

 

큐 삽입 과정

 

큐는 rear가 가리키는 노드 뒤쪽에 들어가기 때문에, 먼저 노드를 뒤에 만들어 놓고 rear의 next가 그 노드를 가리키게 만든 다음에, rear가 그 노드를 가리키도록 하면 된다. 

 

void push(Queue *queue, int data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node -> data = data; 
    node -> next = NULL;
    if (queue -> count == 0) { // 큐가 비어 있을 때는 count값이 0이고
        queue -> front = node; // front에 node를 넣어 준다. 첫번째 원소이기 때문이다. 초기세팅이다. 
    } else { // 첫번째가 아닌 경우에는 다 rear 뒤쪽에 넣는다.
        queue -> rear -> next = node; // rear의 다음 노드가 node가 되고
    }
    queue -> rear = node; // rear가 node가 된다.
    queue -> count++;
}

 

push 함수는 queue와 data를 매개변수로 갖는다. 앞서 그림으로 본 것처럼 먼저 node를 만들어서 메모리 할당을 해 준다. node의 구조인 data, next가 가리키는 것을 각각 정한다. 만약 큐의 count가 0일 때는 큐가 비어 있다는 의미이므로 front를 node로 설정해 주고, count가 0이 아닐 때는 rear의 next가 node를 가리키게 한다. 그러고 나서 rear를 node로 재설정해 주고, 큐의 count를 1 올리면 push가 끝난다.

 

3. pop 함수 구현하기

 

큐 pop함수 구현하기

 

pop함수는 front가 그다음 노드를 가리키게 한 후, 기존 front를 메모리 해제해 주면 된다.

 

int pop(Queue *queue) {
    if (queue -> count == 0)
    {
        printf("큐 언더플로우");
        return -INF;
    }
    
    Node *node = queue -> front;
    int data = node -> data;
    queue -> front = node -> next;
    free(node);
    queue -> count--;
    return data;
}

 

일단 삭제할 노드를 Node *node 라고 해 준다. 그리고 그건 현재 큐의 front에 해당하는 것이다. 또 정수형 data를 선언해서 현재 front의 data를 담아둔다. 그리고 앞서 그림으로 살펴본 pop 과정처럼, 큐의 front를 node의 next로 바꿔 가리키게 한 후, 기존 front였던 node를 메모리 해제해 준다. 그리고 계속 잊게 되는데 queue의 count를 1 빼줘야 한다. 담아 두었던 기존 front의 data를 리턴하면 pop함수 끝이다. 

 

4. 큐 전체 구현하기

 

void show(Queue *queue) {
    Node *cur = queue -> front; 
    while (cur != NULL)
    {
        printf("%d \n", cur -> data);
        cur = cur -> next;
    }
}

int main(void) 
{
    Queue queue;
    queue.front = queue.rear = NULL;
    queue.count = 0;

    push(&queue, 7);
    push(&queue, 5);
    push(&queue, 4);
    pop(&queue);
    push(&queue, 6);
    pop(&queue);

    show(&queue);
}

4 
6

 

show 함수에서 큐의 cur을 next로 하나씩 옮겨주면서 프린트한다. main 함수에서 push, pop 함수를 구현하면 올바른 결과가 나온다.