[Data Structure] #2-3 연결된 스택 (Linked Stack)

연결 스택 (Linked Stack)

 저번 배열 스택에 이어서 연결리스트를 이용한 스택이다. 우리가 이미 배웠던 연결리스트의 개념을 잊지 않았다면 아주 쉽다. (정말 쉽다..)

기억해야할 점은 스택이 아래에서 쌓인다는 점이다. 그렇기에 삽입시 새로 들어오는 노드는 원래 최상위 노드를 가리켜야 한다는 점이다. 그리고 top 포인터를 다시 한단계 올려주면 된다. 삭제시에도 최상위 노드부터 없앤다. 그리고 top을 한단계 내려준다.

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

//linked list를 이용한 stack의 장점은
//stack의 크기가 동적이라는 점이다.
//반면 삽입이나 삭제에 시간이 좀 더 걸린다.

typedef int element;
typedef struct{
    element item;
    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; //always false
}

void push(LinkedStackType *s, element item){
    StackNode *new_node = (StackNode*) malloc(sizeof(StackNode));
    new_node->item = item;
    new_node->link = s->top;
    s->top = new_node;
}

element pop(LinkedStackType *s){
    if (is_empty(s))
        exit(1);
    StackNode *top = s->top;
    element item = top->item;
    s->top = s->top->link;
    free(top);
    return item;
}

element peek(LinkedStackType *s){
    if (is_empty(s))
        exit(1);
    element item = s->top->item;
    return item;
}

int main(){
    LinkedStackType s;
    init(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    
    printf("%d\n",pop(&s));
    printf("%d\n",pop(&s));
    printf("%d\n",pop(&s));
    printf("%d\n",is_empty(&s));
    return 0;
}

ㅁㅁㅁ