[Data Structure] 연결 리스트를 통한 스택과 큐 구현

---

스택

 

기존 정적으로 구현한 스택은 스택의 크기가 유한하고, 한번 설정한 메모리 공간을 계속 사용한다는 단점이 있었다. 이를 연결 리스트로 구현하면 스택의 각 칸을 동적으로 할당하기 때문에 이러한 단점을 극복할 수 있다. 단 각 칸을 노드로 구현하기 때문에 칸 당 소비하는 메모리는 노드로 구현할 때 배열로 구현할 때보다 더 많다.

기존에 스택은 top 변수를 배열 인덱스로 이용하였는데, 연결 리스트로 구현하게 된다면 헤드 포인터를 top 변수로 사용하게 된다.

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct Node {
    element data;
    struct Node* link;
} Node;

typedef struct {
    Node* top;
} Stack;

void init(Stack* s) {
    s->top = NULL;
}

int is_empty(Stack* s) {
    return (s->top == NULL);
}

int is_full(Stack* s) {
    return 0;
}

void push(Stack* s, element item) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = item;
    node->link = s->top;
    s->top = node;
}

element pop(Stack* s) {
    if (is_empty(s)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        Node* removed = s->top;
        int data = removed->data;
        s->top = s->top->link;
        free(removed);
        return data;
    }
}

element top(Stack* s) {
    if (is_empty(s)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return s->top->data;
    }
}

int size(Stack* s) {
    if (is_empty(s)) {
        return 0;
    } else {
        int sum = 0;
        for (Node* p = s->top; p != NULL; p = p->link) {
            sum += 1;
        }
        return sum;
    }
}

void print_stack(Stack *s) {
    for (Node* p = s->top; p != NULL; p = p->link) {
        printf("%c -> ", p->data);
    }
    printf("NULL \n");
}

 

---

큐

 

정확히는 원형 큐를 구현 가능하다. 스택을 연결 리스트로 구현할 때와 마찬가지로 크기 제한에서 벗어날 수 있다는 장점이 있다.

front 는 처음 노드를 가리키는 포인터로, rear 는 마지막 노드를 가리키는 포인터 변수로 사용된다.

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct Node {
    element data;
    struct Node *link;
} Node;

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

void init(Queue* q) {
    q->front = q->rear = 0;
}

int is_empty(Queue* q) {
    return (q->front == NULL);
}

int is_full(Queue *q) {
    return 0;
}

void enqueue(Queue* q, element data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->link = NULL;
    if (is_empty(q)) {
        q->front = node;
        q->rear = node;
    } else {
        q->rear->link = node;
        q->rear = node;
    }
}

element dequeue(Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    Node* removed = q->front;
    element data = removed->data;
    q->front = q->front->link;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(removed);
    return data;
}

element front(Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        return q->front->data;
    }
}

element rear(Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        return q->rear->data;
    }
}

int size(Queue* q) {
    int sum = 0;
    for (Node* p = q->front; p != NULL; p = p->link) {
        sum += 1;
    }
    return sum;
}

void print_queue(Queue* q) {
    for (Node* p = q->front; p != NULL; p = p->link) {
        printf("%c -> ", p->data);
    }
    printf("NULL\n");
}