스택 (Stack)

 

후입 선출(LIFO : Last-In First-out),

가장 최근에 들어온 데이터가 가장 먼저 나가고 가장 나중에 들어온 데이터가 가장 나중에 나가는 자료 구조

 

연산

push : 데이터를 넣는다.

pop : 데이터를 꺼낸다.

peek : 가장 위에 있는 데이터를 반환한다.

isEmpty : 스택이 비어있는지 확인한다.

 

추가 삭제 연산은 상수시간에 가능하나, (연결 리스트로 구현하면 메모리 할당 및 해제 시간이 배열보다 조금 더 걸린다.)

특정 항목에 대한 접근은 상수 시간안에 불가능 하다.

 

/*
	연결 리스트로 구현한 스택
	코드 출처 : C언어로 쉽게 풀어쓴 자료구조 / 생능출판 / 천인국, 공용해, 하상호 지음 
*/
#include <stdio.h>
#include <malloc.h>

typedef int element;
typedef struct StackNode {
    element item;
    struct StackNode *link;
} StackNode;

typedef struct {
    StackNode *top;
} LinkedStackType;

void init(LinkedStackType *s)
{
    s->top = NULL;
}

int isEmpty(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->item = item;
        temp->link = s->top;
        s->top = temp; //스택 맨 위 포인터에 새로 넣은 노드의 주소를 넣는다.
    }
}

element pop(LinkedStackType *s)
{
    if(isEmpty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        StackNode *temp = s->top;
        element item = temp->item;
        s->top = s->top->link; //top은 맨 위 아래 데이터를 가리킨다.
        
        free(temp);
        return item;
    }
}

element peek(LinkedStackType *s)
{
    if(isEmpty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        return s->top->item;
    }
}

void main() {
    LinkedStackType s;
    init(&s);
    push(&s, 1);
    push(&s, 2);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", isEmpty(&s));
}