Stack(feat.Linked List)

박재현·2024년 5월 8일

Algorithm

목록 보기

9/22

바로 직전에는 배열로 스택을 구현해봤는데, 이번에는 연결리스트를 이용해서 스택을 구현해보려고 한다.

사담인데, 나는 프로그래밍을 C언어로 처음 시작을했다.
그래서 다양한 data type들과 각각 data type들이 몇byte의 memory size인지도 알아야했다.
또 배열이라는걸 사용했었고 배열의 한계를 느끼고 Linked List를 접하고 와!!! 개쩐다 신세계다!!! 하고 온몸에 소름돋았던 기억이 있는데, 요즘 JS / Python으로 코딩을 입문하는 분들은 이런게 없는거 같아 좀 아쉽다.
unsigned int라는걸 들어봤을까?ㅋㅋ 여튼...꼰대냄새 나니 그만!!! 멈춰!!

일단 연결리스트 자체가 동적할당을 통해서 구현되기 때문에, 연결리스트를 이용해서 구현하는 스택은 굉장히 유연하다!

연결리스트를 이용해서 스택을 구현하게되면, 배열하고 다르게 사이즈를 미리 선언해주지 않기때문에 불필요한 메모리 낭비를 방지할 수 있음과 동시에 메모리가 허용하는 한도내에서 계속해서 데이터를 저장할 수 있다는점이다.

또, 스택은 데이터가 드나드는 입구와 출구가 하나이기 때문에 단순 연결 리스트로 아주~ 쉽게 구현이 가능하다!

위 그림을 통해서 알 수 있지만, 새로운 값이 추가되는 위치와, 스택에서 가장 최근에 들어온 값을 빼내는 위치가 모두 동일한걸 알 수 있다.

따라서 Head->next만 우리는 조작하면 되는 간단한 구조라서 previous node를 굳이 조작할 필요가 없기 때문에, simple linked list로 구현해도 충분하다.

리스트 초기화

typedef struct _node {
    int value;
    struct _node *next;
} node;

node *head;
node *tail;

void init_list(void) {
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    head->next = tail;
    tail->next = tail;
}

이전에 포스팅한 Simple Linked List글을 읽고 이해했다라면, 추가적으로 설명할 필요는 없을것 같긴하다.

List의 구조를 유지하고 처음과 끝을 명확히 하기위해서 head / tail 노드를 만들고 리스트의 모양을 잡아주기만 하면 끝난다.

Push!

기능을 구현하기 이전에 한가지 명확하게 해야할 부분이 있는데, linked list로 stack을 구현하게되면 Stack Overflow라는 개념 자체가 없다는 점이다.

왜?? 라고 생각이 들었다면, 배열과 리스트의 차이와 배열의 한계점 등을 다치 확인해볼 필요가 있을듯하다 😭

여튼, Linked List로 구현한 스택은 "미리 정해진 스택의 크기가 없고" 메모리가 허용하는 내에서 계속 커질 수 있다.

따라서 StackOverflow라는 예외상황 대신에 메모리가 부족해서 새로운 노드를 생성하지 못하는 경우인 OOM(Out Of Memory) 에러를 반환해주면 된다.

void push(int value) {
    node *new;
    if( (new = (node *)malloc(sizeof(node))) == NULL ) {
        printf("Occurred OOM !\n");
        return;
    }
    
    new->value = value;
    new->next = head->next;
    head->next = new;
}

여기서 잘 확인해야 하는건, 배열로 스택을 구현할때 가장 최상단(즉 가장 마지막에 들어온 값)의 값을 TOP이라는 변수로 인덱싱을 했지만, List로 구현할경우 무조건 Head->next에 삽입해주면 된다.

즉, Head 노드가 Top인덱스를 대체한다고 이해하면 된다.

POP!

Pop 동작은 스택의 가장 상단이 head이기 때문에, head->next 노드의 값을 반환하고 해당 노드를 삭제해주면 끝난다.

다만 여기서 조심해야할 부분은 바로 스택에 아무것도 없을때이다.

스택이 빈 상태에서 head->next인 tail을 삭제하고 반환한다면 말 그대로 대참사가 일어난다!

int pop(void) {
    if(head->next == tail) {
        printf("Stack underflow !!!\n");
        return -1;
    }
    int value;
    node *temp;
    
    temp = head->next;
    value = temp->value;
    head->next = temp->next;
    free(temp);
    
    return value;
}

Clear Stack

스택을 초기화할때에도 신경을 써줘야한다.

단순하게 head->next = tail; 이 한줄로 스택이 초기화 될 수 있다.

다만, 이렇게 되면 기존에 스택에 있던 모든 노드들이 memory를 반환하지 않게되고 말 그대로 memory leak이 발생한다.

따라서 처음부터 마지막까지 모든 노드를 메모리에서 삭제해야만 한다.

많은 사람들이 메모리를 신경쓰지 않는데, 신경써줘야 한다...

void clear_stack(void) {
    node *temp;
    node *delete;
    
    temp = head->next;
    while(temp != tail) {
        delete = temp;
        temp = temp->next;
        free(delete);
    }
    head->next = tail;
}

전체코드

//
//  main.c
//  Stack_LinkedList
//
//  Created by 박재현 on 2024/05/08.
//

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

typedef struct _node {
    int value;
    struct _node *next;
} node;

node *head;
node *tail;

void init_list(void) {
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    head->next = tail;
    tail->next = tail;
}

void push(int value) {
    node *new;
    if( (new = (node *)malloc(sizeof(node))) == NULL ) {
        printf("Occurred OOM !\n");
        return;
    }
    
    new->value = value;
    new->next = head->next;
    head->next = new;
}

int pop(void) {
    if(head->next == tail) {
        printf("Stack underflow !!!\n");
        return -1;
    }
    int value;
    node *temp;
    
    temp = head->next;
    value = temp->value;
    head->next = temp->next;
    free(temp);
    
    return value;
}

void clear_stack(void) {
    node *temp;
    node *delete;
    
    temp = head->next;
    while(temp != tail) {
        delete = temp;
        temp = temp->next;
        free(delete);
    }
    head->next = tail;
}

void print_stack(void) {
    node *t;
    t = head->next;
    
    printf("\nStack as below\n");
    while(t != tail) {
        printf("%-6d", t->value);
        t = t->next;
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    int num;
    init_list();
    
    printf("\nPush 5, 4, 7, 8, 2, 1");
    push(5);
    push(4);
    push(7);
    push(8);
    push(2);
    push(1);
    print_stack();
    
    printf("POP !\n");
    num = pop();
    print_stack();
    printf("POP value is %d\n", num);
    
    printf("\nPush 3, 2, 5, 7, 2");
    push(3);
    push(2);
    push(5);
    push(7);
    push(2);
    print_stack();
    
    printf("Push 3\n");
    push(3);
    print_stack();
    
    printf("Initialize stack!\n");
    clear_stack();
    print_stack();
    
    printf("Currently Stack is Empty !!\nLet's try POP!\n");
    num = pop();
    print_stack();
    printf("POP value is %d\n", num);
    
    
    return 0;
}