후입선출(Last In First Out; LIFO)의 특성을 갖는 자료구조로, 데이터를 쌓아올리는(stack)의 형태를 갖는다.

  • push: 데이터를 넣는 작업
  • pop: 데이터를 꺼내는 작업

Implementation

스택은 배열(array)와 연결리스트(linked list)로 구현할 수 있는데, 여기서는 연결리스트를 이용해서 스택을 구현할 것이다.

structure

typedef struct node {
    void* data;
    struct node *next;
} node;

typedef struct stack {
    int size;
    node *head;
} stack;

동적으로 할당할 data와 다음 노드를 가리킬 next 포인터로 하나의 element 형태를 갖는다.

initialize

stack init_stack() {
    stack st;
    st.head = NULL;
    return st;
}

stack를 만들고, 아무것도 가리키는것이 없으니 head를 NULL로 초기화한다

push

void push(stack *st, void *in) {
    node* n = (node *)malloc(sizeof(node));
    n->data = in;
    n->next = st->head;
    st->head = n;
    ++st->size;
}

새로 추가할 노드를 할당한 뒤, 새로 추가된 노드의 next에 이전 노드가 가리키던 head포인터를 넘겨주고, 후입선출의 성질을 갖도록 스택의 head에는 방금 추가한 노드 포인터를 가리키게 해준다.

pop

void* pop(stack *st) {
    assert(st->size <= 0) {
        return NULL;
    }

    node *n = st->head;
    st->head = n->next;
    --st->size;

    void *out = n->data;
    free(n);

    return out;
}

가장 위에 있는node가 먼저 나가야하므로 현재 head가 가리키는 node의 data주소를 별도의 포인터 변수에 저장한 뒤, 이전 노드를 가리키도록 head에는 지울 노드가 가리키던 next 노드를 가리키도록 한다.