[자료구조] - 연결된 스택, 연결된 큐 (Linked Stack, Linked Queue)

---

---

연결 리스트로 구현한 스택 (Linked Stack)

지난 스택에 관한 포스팅(여기)에서는 스택을 구현할 때, "배열"을 이용해서 구현했습니다. 이번 포스팅에서는 연결 리스트로 구현하고자 합니다. 어찌 되었든 스택을 구현하는 것이기에 배열을 이용하나, 연결 리스트를 이용하나 외부적으로 볼 때는 큰 차이가 없습니다.

그러나, 스택의 내부를 살펴보면 차이점이 있습니다. 바로 배열과 달리, 연결 리스트로 구현한 스택은 "크기에 제한을 받지 않는다는 것"입니다. 동적 메모리 할당을 통해 스택에 새로운 요소를 삽입할 수 있습니다. 다만, 삽입과 삭제 시에 동적 메모리 할당을 하고 해제해야 하기 때문에 시간이 조금 더 걸립니다.

연결된 스택(Linked Stack) 구현

C언어로 구현한 연결된 스택은 다음과 같습니다.

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

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

typedef struct {
    StackNode *top;
} LinkedStackType;

// 초기화 함수
void init(LinkedStackType *s) {
    s->top = NULL;
}

// 공백 상태 검출 함수
int is_empty(LinkedStackType *s) {
    return (s->top == NULL);
}

// 포화 상태 검출 함수
int is_full(LinkedStackType *s) {
    return 0;
}

// 삽입 함수
void push(LinkedStackType *s, element item) {
    StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
    temp->data = item;
    temp->link = s->top;
    s->top = temp;
}

// 스택 출력 함수
void print_stack(LinkedStackType *s) {
    for (StackNode *p = s->top; p != NULL; p = p->link) {
        printf("%d->", p->data);
    }
    printf("NULL \n");
}

// 삭제 함수
element pop(LinkedStackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        StackNode *temp = s->top;
        int data = temp->data;
        s->top = s->top->link;
        free(temp);
        return data;
    }
}

// 피크 함수
element peek(LinkedStackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        return s->top->data;
    }
}

int main() {
    LinkedStackType s;
    init(&s);
    push(&s, 1); print_stack(&s);
    push(&s, 2); print_stack(&s);
    push(&s, 3); print_stack(&s);
    pop(&s); print_stack(&s);
    pop(&s); print_stack(&s);
    pop(&s); print_stack(&s);
    return 0;

---

연결 리스트로 구현한 큐 (Linked Queue)

연결된 스택을 구현한 것처럼 큐 또한 연결 리스트를 이용하여 구현할 수 있습니다. 지난 포스팅(여기)에서는 배열로 큐를 구현했었는데 이번에는 연결 리스트로 큐를 구현해보도록 하겠습니다. 배열로 구현한 큐와 달리 연결 리스트한 큐는 크기가 제한되지 않는다는 장점이 있습니다. 그러나 배열로 구현한 큐에 비해 코드가 좀 더 복잡해지고, 링크 필드로 인해 메모리를 더 많이 사용하게 됩니다.

연결된 큐 (Linked Queue) 구현

C언어로 구현한 연결된 큐는 다음과 같습니다.

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

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

typedef struct {
    QueueNode *front, *rear;
} LinkedQueueType;

// 큐 초기화 함수
void init(LinkedQueueType *q) {
    q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(LinkedQueueType *q) {
    return (q->front == NULL);
}

// 포화 상태 검출 함수
int is_full(LinkedQueueType *q) {
    return 0;
}

// 삽입 함수
void enqueue(LinkedQueueType *q, element data) {
    QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
    temp->data = data;
    temp->link = NULL;
    if (is_empty(q)) {
        q->front = temp;
        q->rear = temp;
    }
    else {
        q->rear->link = temp;
        q->rear = temp;
    }
}

// 삭제 함수
element dequeue(LinkedQueueType *q) {
    QueueNode *temp = q->front;
    element data;
    if (is_empty(q)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        data = temp->data;
        q->front = q->front->link;
        if (q->front == NULL) {
            q->rear = NULL;
        }
        free(temp);
        return data;
    }
}

// 큐 출력 함수
void print_queue(LinkedQueueType *q) {
    QueueNode *p;
    for (p = q->front; p != NULL; p = p->link) {
        printf("%d->", p->data);
    }
    printf("NULL\n");
}

int main() {
    LinkedQueueType queue;
    
    init(&queue);
    
    enqueue(&queue, 1); print_queue(&queue);
    enqueue(&queue, 2); print_queue(&queue);
    enqueue(&queue, 3); print_queue(&queue);
    dequeue(&queue); print_queue(&queue);
    dequeue(&queue); print_queue(&queue);
    dequeue(&queue); print_queue(&queue);
    return 0;
}

---

결론 (Conclusion)

이번에 구현한 연결된 스택과 연결된 큐를 제대로 이해하기 위해선 우선 "스택", "큐", "연결 리스트"에 대한 이해도가 필요합니다. 연결된 스택과 연결된 큐를 다루는 포스팅이지만 이 포스팅은 사실 상세하게 내용을 적진 않았습니다. 그 이유가 금방 말한대로 스택, 큐, 연결 리스트에 대한 이해가 있다면 연결된 스택, 연결된 큐를 전혀 어렵지 않게 이해할 수 있기 때문입니다.

혹시나 이해가 잘 되지 않는다면 스택(여기), 큐(여기), 연결 리스트(여기) 포스팅을 참고해주시거나, 따로 공부를 더 하고 읽어주세요 

---