[자료구조] 스택(Stack) in C

스택이란?

스택은 맨 위에서 삽입과 삭제가 일어나고 중간에서는 데이터를 삭제, 삽입이 불가능한 추상 자료형을 말한다.
이러한 입출력 형식을 후입선출(LIFO:Last-In First-Out) 이라고 한다.

특징 및 사용 예시

특징: 스택은 데이터를 저장할 수 있는 공간인 stack과 가장 위에 공간을 가리키는 top이라는 요소를 가진다.
예시: 스택은 데이터를 역순으로 만들고자 할 때 사용된다. 스택에 값을 순서대로 넣었다가 이를 꺼내어 순서대로 데이터를 저장하면 역순으로 변경된 데이터들을 얻을 수 있다. "ctrl + z" (되돌리기) 기능도 스택이 활용된 예시이다.

스택의 연산 및 구현

배열로 구현한 스택의 연산

init_stack(size)

최대 크기가 size인 배열을 생성한다.
스택의 최상단 인덱스를 가리키는 top은 -1이다.

void init(StackType *s)
{
	s->top = -1;
}

is_full

스택의 공간이 가득 찼을 때를 말한다.
top 과 size - 1 이 같을 경우 가득 찬다.

int is_full(StackType *s) // 스택이 가득차면 1 아니면 0
{
	return s->top == MAX_STACK_SIZE - 1;
}

is_empty

스택의 공간이 비어 있을 때를 말한다.
top 이 -1 과 같으면 스택은 비어있다.

int is_empty(StackType *s) // 스택이 비어있으면 1 아니면 0
{
	return s->top == -1;
}

push(item)

스택에 최상단에 항목을 삽입한다.
top 을 1 증가 시키고 해당 위치에 항목을 삽입한다.

void push(StackType *s, element item)
{
	if(is_full(s)) // 포화 상태인지 확인
    	return;
	s->data[++(s->top)] = item;
}

pop

스택에 최상단의 항목을 반환하고 삭제한다.
스택에 항목을 반환하고 top 을 1 감소시킨다.

element pop(StackType *s)
{
	if(is_empty(s)) // 공백 상태인지 확인
    	exit(1);
    return s->data[(s->top)--];

peek

스택의 최상단을 반환한다.
스택의 top 위치에 저장되어있는 값을 반환한다.

element peek(StackType *s)
{
	if(is_empty(s)) // 공백 상태인지 확인
    	exit(1);
	return s->data[s->top];
}

전체 코드

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

// == 스택 코드 ==
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct
{
    element data[MAX_STACK_SIZE];
    int top;
} StackType;

// 에러 출력 함수
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
}

// 스택 초기화 함수
void init_stack(StackType *s)
{
    s->top = -1;
}

// 포화 상태 확인 함수
int is_full(StackType *s)
{
    return s->top == MAX_STACK_SIZE - 1;
}

// 공백 상태 확인 함수
int is_empty(StackType *s)
{
    return s->top == -1;
}

// 삽입 함수
void push(StackType *s, element item)
{
    if (is_full(s))
    {
        error("스택 포화 에러\n");
        return;
    }
    s->data[++(s->top)] = item;
}

// 삭제 함수
element pop(StackType *s)
{
    if (is_empty(s))
    {
        error("스택 공백 에러\n");
        exit(1);
    }
    return s->data[(s->top)--];
}

// 피크 함수
element peek(StackType *s)
{
    if (is_empty(s))
    {
        error("스택 공백 에러\n");
        exit(1);
    }
    return s->data[s->top];
}

int main(void)
{
    StackType s;
    init_stack(&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));

    return 0;
}

마무리

여기서 알아야할 점은 StackType 구조체를 선언한 후 init_stack(&s)로 초기화를 해주어야 한다는 점이다.

typedef를 활용하여 element는 스택에 들어가는 값으로 설정하여 이를 변경하면 여러 자료형을 효과적으로 사용할 수 있다.
typedef char element; 이런식으로 선언하면 문자를 저장하는 스택을 만들 수 있다.

스택을 활용하면 괄호 검사, 후위 표기식 계산 등 우선순위나 이전의 데이터를 저장하고 있어야 할 때 사용하면 효율적이다.

오늘은 스택에 대해 알아보았다. 여러 문제를 풀면서 스택의 활용에 대해서 공부하면 좋겠다.

📕 참고 문헌

다음의 책을 참고했습니다.
C언어로 쉽게 풀어쓴 자료구조 [ 개정3판 ]
천인국, 공용해, 하상호 저 | 생능출판사 | 2021년 08월 20일