[자료구조]스택(Stack) - 연결리스트

연결리스트 자체가 동적인 할당을 통해서 구현되기 때문에 연결리스트를 이용해서 구현되는 스탹은 매우 유연하다. 

연결 리스트를 이용하여 스택을 구현할 때의 장점은 현재 스택에 저장되어 있는 자료 만큼만 메모리를 잡아먹기 때문에 메모리가 절약되고 스택의 크기가 메모리가 허용하는 한도에서 커질 수 있다는 것이다. 

#include <stdio.h>
#include <alloc.h>
 
// 리스트 노드 
typedef struct _node{
    int key;
    struct _node* next;
} node;
 
// 전역 변수 
node *head, *tail;
 
// 전역변수 초기화
void init_stack(void)
{
    head = (node*)malloc(sizeof(node));
    tail = (node*)malloc(sizeof(node));
 
    // 기본적인 연결리스트 구조
    // 머리는 꼬리를 바라보고 
    // 꼬리는 자기 자신을 바라본다.
    head->next = tail;
    tail->next = tail;
}
 
void clear_stack(void){
    node *t, *s;
    t = head->next;
 
    // head의 다음 노드가 tail일 때가지 돌아서 중간에 있는 node를 제거 한다. 
    while (t != tail){
        s = t;
        t = t->next;
        free(s);
    }
 
    head->next = tail;
}
 
 
// 추가
int push(int k){
 
    // 메모리 부족 확인
    node *t;
    t = (node*)malloc(sizeof(node));
 
    if (t == NULL){
        printf("\n Out of memory!!!");
        return -1;
    }
 
    t->key = k;
    t->next = head->next;
    head->next = t;
 
    return k;
}
 
// 삭제
int pop(void){
    node *t;
    int i;
 
    if (head->next == tail){
        printf("\n Stack underflow");
        return -1;
    }
 
    t = head->next;
    i = t->key;
    head->next = t->next;
    free(t);
    return 1;
}
 
void print_stack(void){
    node *t;
    t = head->next;
    printf("\n Stack contents : Top -----> Bottom");
 
    while (t != tail){
        t = t->next;
    }
 
}
 
 

위의 내용을 활용하여 메일을 작성하시면 됩니다. 

참구 하세요. 감사합니다.