스택 자료구조 연결 리스트를 이용하는 방법 C로 구현하기

 

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

 

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

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

typedef struct Stack{
    Node *top; 
} Stack;

 

먼저 INF를 무한대의 값으로 설정하고, Node 구조체를 만든다. 기본적으로 연결 리스트는 다음 노드를 가리켜야 하므로, 노드의 data와 다음 노드를 가리키는 포인터 변수 next를 만들어준다. 또 Stack이라는 구조체를 만들어서, 모든 스택이 top이라는 노드를 가지고 있고 포인터를 가지고 있는 구조체이기 때문에 일종의 배열 형태로 만들 수 있다.

 

연결 리스트를 활용한 스택 push 구현 원리

 

Top은 스택의 최상단이다. 스택은 데이터를 넣을 때 반드시 top의 자리에 들어가야 하므로, 삽입할 노드의 next가 top을 가리키도록 하면 된다. 그렇게 하면 삽입된 노드는 스택의 최상단 노드인 top이 되고, 이전에 top이었던 노드는 일반 노드의 위치가 된다. 간단하게 스택에 데이터를 넣을 수 있다.

 

연결 리스트를 활용한 스택 pop의 원리

 

항상 추출은 최상단 노드에서 이루어지기 때문에, stack의 top이 가리키는 노드가 삭제할 노드다. 삭제할 노드의 데이터를 기록해 두었다가 top이 두 번째 노드를 가리키게 한 다음, top은 할당 해제를 해 준다. 그리고 기록해 둔 삭제한 노드의 데이터를 리턴하면 된다.

 

2. push(), pop() 함수 구현하기

 

// 스택 추가 과정
void push(Stack *stack, int data) {
    Node *node = (Node*) malloc(sizeof(Node));

    node -> data = data;
    node -> next = stack -> top;
    stack -> top = node;
}

// 스택 추출 과정
int pop(Stack *stack) {
    if (stack -> top == NULL)
    {
        printf("스택언더플로우\n");
        return -INF;
    }
    Node *node = stack -> top;
    int data = node -> data;
    stack -> top = node -> next;
    free(node);
    return data;
}

 

push() 함수를 구현하기 위해서는 먼저 매개변수로 삽입하고자 하는 스택과 데이터를 받도록 한다. 그리고 한 개의 노드가 들어갈 메모리를 할당해 준 다음에, 그 node의 data로는 인자로 받은 데이터를 넣어준다. 그리고 node의 next는 스택의 최상단 top을 가리키도록 해 준다. 이렇게 만들어 준 node를 stack의 top이 가리키도록 바꿔치기하면 된다. 

 

pop() 함수를 구현하기 위해서는 매개변수로 스택을 받도록 한다. pop()은 최상단 노드를 빼내는 것이기 때문에, 현재의 최상단 노드 자체와 data를 잠깐 담아 두었다가, 두 번째 노드가 최상단 노드가 될 수 있도록 바꿔치기해준다. 그러고 나서 아까 담아 둔 node의 메모리를 해제해 주고, 그 node의 데이터를 리턴해주면 pop() 함수 완성이다. 만약 현재 스택이 비어 있으면 에러 메시지와 -INF 값을 출력하고 실행을 중단한다. 

 

// 스택 전체 출력하는 함수
void show(Stack *stack) {
    Node *cur = stack -> top;
    printf("스택의 최상단\n");
    while (cur != NULL)
    {
        printf("%d\n", cur -> data);
        cur = cur -> next;
    }
    printf("스택의 최하단\n");
}

 

스택 전체를 출력하는 show() 함수에서는 top에서부터 시작해서 NULL을 만나기 직전까지 다음 노드를 출력하도록 한다.

 

3. 완성된 스택 사용하기

 

int main(void) 
{
    Stack s;
    s -> top = NULL;
    show(&s);

    push(&s, 7);
    push(&s, 8);
    push(&s, 4); 
    pop(&s);
    push(&s, 2); 
    pop(&s);
    show(&s);
}

main.c:52:7: error: member reference type 'Stack' (aka 'struct Stack') is not a pointer; did you mean to use
      '.'?
    s -> top = NULL;
    ~ ^~
      .
main.c:52:14: error: expression is not assignable
    s -> top = NULL;
    ~~~~~~~~ ^
2 errors generated.

 

처음에 스택을 만들어 줄 때, top에 NULL 값을 넣어주어야 한다. 그래야 반복문을 돌리거나 다른 연산을 할 때 NULL 값을 만날 때까지 실행하도록 할 수 있기 때문이다. 스택에 처음 값을 넣어주는 순간부터 data를 가지면 된다. &s라고 쓰는 이유는 스택 변수의 메모리 주소를 보내줘야 하기 때문이다. 

 

오류 메시지가 나오길래 무슨 일인고 했더니 Stack은 포인터 변수가 아니라는 것을 잊고 -> 기호를 써서 그런 거였다. 고쳐서 다시 실행했다.

 

int main(void) 
{
    Stack s;
    s.top = NULL;
    show(&s);

    push(&s, 7);
    push(&s, 8);
    push(&s, 4); 
    pop(&s);
    push(&s, 2); 
    pop(&s);
    show(&s);
}

스택의 최상단
스택의 최하단
스택의 최상단
8
7
스택의 최하단

 

프로그램을 실행해 보면 잘 나온다. 메모리의 낭비 없이 스택을 구현할 수 있는 연결 리스트를 이용해 보았다.