요약

하나를 쌓을 때마다 노드를 새로 만들어 줄의 맨 앞에 끼우고, 꺼낼 때는 맨 앞 노드를 떼어 낸다. 맨 앞에서만 넣고 빼니 둘 다 한 번에 끝나고, 칸 수를 미리 정하지 않아도 메모리가 남아 있는 한 계속 쌓인다. 대신 원소마다 다음 노드의 주소를 적을 칸이 하나씩 더 들고, 넣고 뺄 때마다 메모리를 얻고 돌려주는 일을 한다.

예시로 보기

배열로 만든 스택은 정해 둔 칸 수까지만 담는다. 얼마나 쌓일지 모르면 칸 수를 넉넉히 잡거나 가득 찰 때마다 배열을 옮겨야 한다. 연결 리스트로 만들면 처음에 크기를 정할 필요가 없다.

3, 7, 9를 차례로 쌓은 스택을 두 방법으로 그리면 이렇다.

배열 스택                    연결 스택

칸 4 |   |                  top
칸 3 |   |                   |
칸 2 | 9 | <- top            v
칸 1 | 7 |                  [9] -> [7] -> [3] -> NULL
칸 0 | 3 |

연결 스택에서는 top이 맨 위 원소의 노드를 가리키고, 노드마다 링크가 바로 아래 원소의 노드를 가리킨다. 맨 아래 노드의 링크는 NULL이다. 새 원소는 늘 top이 가리키는 자리에 끼우고, 꺼낼 때는 top이 가리키는 노드를 뗀 뒤 top을 그 아래 노드로 옮긴다.

한 일 돌려준 값 체인 (맨 왼쪽이 top)
push 3, push 7, push 9   9 → 7 → 3
pop 9 7 → 3
push 5   5 → 7 → 3
pop, pop 5, 7 3
pop 3 (비었음. top은 NULL)
검증: 컴파일해 실행(ASan·UBSan). 위 그림과 추적 표, 카드 C1·C2, 무작위 연산 5,000번에서 배열 스택(두 배 늘리기 판)과 꺼낸 값·맨 위·빔 판정이 같고 살아 있는 노드 수가 늘 원소 수와 같음, malloc 횟수와 free 횟수가 같음 — 18_linked-stack_impl.c

정의

하는 일은 배열로 만든 스택과 같다. 넣기(push), 꺼내기(pop), 비었는지 보기다. 달라진 것은 담는 방법이다. 원소마다 노드 하나를 두고, 맨 위 노드의 주소를 top에 적는다.

typedef int element;

typedef struct StackNode {
    element item;
    struct StackNode *link;       /* 바로 아래 원소의 노드. 맨 아래면 NULL */
} StackNode;

typedef struct {
    StackNode *top;               /* 맨 위 원소의 노드. 비었으면 NULL */
} LinkedStackType;

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

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

void push(LinkedStackType *s, element item)
{
    StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
    if (temp == NULL) {
        fprintf(stderr, "error\n");
        exit(1);
    }
    temp->item = item;
    temp->link = s->top;          /* 새 노드가 지금의 맨 위를 가리킨다 */
    s->top = temp;                /* 새 노드가 맨 위가 된다 */
}

element pop(LinkedStackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "error\n");
        exit(1);
    }
    StackNode *temp = s->top;     /* 떼어 낼 노드를 적어 둔다 */
    element item = temp->item;
    s->top = s->top->link;        /* 바로 아래 노드가 맨 위가 된다 */
    free(temp);
    return item;
}

push는 단순 연결 리스트의 맨 앞에 끼우기이고, pop은 맨 앞 지우기다. 두 줄의 차례도 그대로다. push에서는 새 노드의 링크를 먼저 채우고 나서 top을 바꾼다. pop에서는 떼어 낼 노드의 주소와 값을 먼저 적어 두고 나서 top을 옮기고 free한다.

늘 지켜야 할 규칙(표현 불변식)은 이렇다. top에서 링크를 따라가면 맨 위 원소부터 맨 아래 원소까지 차례로 만나고 NULL에서 끝난다. 노드 수는 스택에 든 원소 수와 같다1.

배열 스택과 견주기

두 구현을 견주면 이렇다1.

  배열 스택 연결 스택
담는 개수 정해 둔 칸 수까지. 넘으면 끝내거나 배열을 늘린다 정하지 않는다. malloc이 메모리를 주는 동안
push, pop \(O(1)\). 배열을 늘리는 순간만 \(O(\text{칸 수})\) 늘 \(O(1)\)
원소마다 덤으로 쓰는 것 없음. 대신 안 쓴 빈칸이 있다 링크 한 칸
넣고 뺄 때 하는 일 정수 하나를 올리고 내린다 malloc과 free를 한 번씩 부른다

활용

  • 구현: 18_linked-stack_impl.c. 맨 위를 보기만 하는 peek과 남은 노드를 모두 돌려주는 destroy도 이 파일에 있다. 연습: 연결 리스트 연습
  • 다 쓴 스택은 destroy로 비운다. 노드가 남은 채 LinkedStackType 변수만 버리면 그 노드들을 돌려줄 길이 없어진다(동적 메모리 할당의 누수).
  • push가 malloc에 실패했을 때 “error”만 찍고 돌아오면, 부른 쪽은 원소가 들어간 줄 알고 계속 간다. 그래서 pop처럼 프로그램을 끝낸다1.
  • 흔한 실수: pop에서 free(temp)를 먼저 부르고 temp->item을 읽는 것, 빈 스택인지 보지 않고 s->top->link를 읽는 것.

연결

확인 문제

C1 빈 연결 스택에 push 1, push 2, pop, push 3, push 4, pop을 차례로 했다. 꺼낸 값 둘과, 남은 체인을 top부터 써라. 살아 있는 노드는 몇 개인가?

답: 꺼낸 값은 2와 4다. 남은 체인은 top → 3 → 1 → NULL이고 노드는 2개다.
이유: push마다 노드 하나를 얻고 pop마다 하나를 돌려준다. 네 번 얻고 두 번 돌려줬다.

C2 스택의 맨 위를 체인의 맨 앞 노드로 잡는다. 거꾸로 체인의 맨 끝 노드를 맨 위로 잡으면 pop이 왜 느려지는가?

답: 맨 끝 노드를 떼려면 그 앞 노드의 링크를 NULL로 고쳐야 한다. 링크가 한 방향뿐이라 앞 노드는 처음부터 따라가야 찾는다. 노드가 \(n\)개면 링크를 \(n - 2\)번 따라가므로 pop이 \(O(n)\)이 된다.
이유: 체인에서 한 번에 끝나는 일은 맨 앞에 끼우기와 맨 앞 지우기다. 스택은 넣는 곳과 빼는 곳이 같으니, 둘 다 맨 앞에서 하면 된다.

C3 배열 스택과 연결 스택 가운데 무엇이 알맞은가? (가) 작은 기기에서 메모리를 처음에 한 번만 잡고, 도는 동안에는 malloc을 부르지 않으려 한다. 깊이는 많아야 64다. (나) 깊이가 수십일 때도 있고 수십만일 때도 있는데, 넣는 일 한 번이 오래 걸리는 순간이 있으면 안 된다.

답: (가)는 배열 스택이다. 칸 64개를 처음에 잡으면 그 뒤로 메모리를 얻을 일이 없다. (나)는 연결 스택이다. 배열을 두 배로 늘리는 판은 가득 차는 순간의 push가 원소를 모두 옮기느라 오래 걸리지만, 연결 스택의 push는 늘 노드 하나를 얻는 일뿐이다.

  1. 구현 코드로 확인했다. ↩ ↩2 ↩3