Data Structure 6 - Stack(2)

배열로 스택을 구현할 수도 있다면, 연결리스트로도 스택을 구현할 수 있다. 

#include<stdio.h> // 연결리스트로 구현한 스택 ADT
#include<stdlib.h>
typedef int element;
typedef struct StackNode
{
    element data;
    struct StackNode* link;
}StackNode;

typedef struct
{
    StackNode* top; // 스택의 top을 나타내는 포인터
}LinkedStackType;

void init(LinkedStackType* s) // stack 초기화
{
    s->top == NULL; // top이 가르키는 것을 NULL(-1)로 초기화.
}

int is_empty(LinkedStackType* s)
{
    return (s->top == NULL);
}

void push(LinkedStackType* s, element item) //삽입 함수
{
    StackNode* temp = (StackNode*)malloc(sizeof(StackNode)); // 동적 메모리를 할당해 넣고자하는 노드 생성
    if (temp == NULL)
    {
        fprintf(stderr, "메모리할당에러\n");//만약 메모리 할당이 제대로 안되면 에러.
        return;
    }
    else
    {
        temp->data = item; // 원하는 데이터 삽입
        temp->link = s->top; // 그 밑의 다음 노드 가리킴
        s->top = temp; // 맨위에 집어넣었으니 top 옮겨줌
    }
}

element pop(LinkedStackType* s) // 삭제 함수
{
    if (is_empty(s))
    {
        fprintf(stderr, "스택이 비어 있음\n");
        exit(1);
    }
    else
    {
        StackNode* temp = s->top; // top이 가리키던 것을 잠깐 temp에게 옮겨놓고
        element item = temp->data; // 삭제되는 항목 전달
        s->top = s->top->link; // LinkedStackType s의 포인터 top이 가르키는 StackNode의 link를  s->top에 삽입. 즉, 삭제하는 노드의 link가 가르키던 것을 top이 가르키도록 하는 것.(왜냐하면 맨 위에꺼를 삭제하므로) 
        free(temp); // 삭제한 항목의 주소는 이제 더 필요 없으니까 해제.
        return item;// pop 한 항목 반환
    }
}

element peek(LinkedStackType* s) // 삭제 안하고 맨위의 항목만 뽑아보는 함수
{
    if (is_empty(s))
    {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else return s->top->data;// 맨위의 포인터 top이 가리키던 노드의 item을 반환.
}