[C] 스택(Stack) LinkedList[C] 스택(Stack) LinkedList

Posted at 2015. 2. 14. 23:22 | Posted in C



facebook에 글올리기



[C] 스택(Stack) LinkedList


스택은 리스트로 표현할 수도 있다.

배열에서는 크기가 정해져 있기 때문에 크기 이상의 데이터가 push 되면 스택오버플로우가 발생하지만, 리스트를 사용할 경우 동적으로 할당할 수 있기 때문에 메모리가 고갈될 때까지 push를 할 수 있다.



 Colored By Color Scripter

#include <stdio.h>
#include <malloc.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;
}

int push(int k){
    node *t;
    if ((t = (node*)malloc(sizeof(node))) == 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 i;
}

void clear_stack(void){
    node *t, *s;
    t = head->next;
    while (t != tail){
        s = t;
        t = t->next;
        free(s);
    }
    head->next = tail;
}

void print_stack(void){
    
    node *t;
    t = head->next;
    printf("\n Stack contents : TOP ------> Bottom \n");
    while (t != tail){
        printf("%-6d", t->key);
        t = t->next;
    }
}

int main(void){

    int i;
    init_stack();

    printf("\nPush 5,4,7,8,2,1");
    push(5);
    push(4);
    push(7);
    push(8);
    push(2);
    push(1);
    print_stack();

    printf("\nPop");
    i = pop();
    print_stack();
    printf("\n   popping value is %d", i);

    printf("\nPush 3, 2, 5, 7, 2");
    push(3);
    push(2);
    push(5);
    push(7);
    push(2);
    print_stack();

    printf("\nNow stack is full, push 3");
    push(3);        // 스택 오버플로우
    print_stack();

    printf("\nInitialize stack");
    init_stack();
    print_stack();

    printf("\nNow stack is empty, pop");
    i = pop();
    print_stack();
    printf("\n    popping value is %d", i);

    return 0;
}



이웃추가
facebook에 글올리기

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기