C언어로 스택(Stack) 구현하기

스택

일단 stack의 구조는 이렇다.

데이터를 넣을땐 위에서 넣고, 데이터를 빼낼때 또한 위에서 뺀다.

아래에서 데이터를 넣고, 뺄 수 없다. 항상 위에서만!

후입선출(last in, first out)을 구조를 가진다.

---

스택의 예시

1)함수의 호출

2)웹 브라우저에서 뒤로가기

등등..

 

예를들어, 재귀함수를 호출한다고 가정해보자.

함수는 실행이 끝나면 자신을 호출한 함수로 되돌아가야한다.

만약 factorial(3)이라는 함수를 호출한다면 factorial(2)가 실행되고, factorial(2)함수가 끝나면

factorial(3)함수로 돌아간다는 뜻이다. 스택은 복귀할 주소를 기억하는데 사용된다.

스택 예시

스택에서 입출력이 이루어 지는 가장 윗부분을 stack top이라고 한다.

가장 밑 스택은 bottom stack이라고 한다.

만약, 새로운 데이터를 넣을땐, top을 위로 한칸 옮겨서 그곳에 데이터를 집어넣는다.

---

스택구현하기

스택을 구현하기 위해서 몇가지 함수를 정의할 필요가 있다.

 

 

 

1. 스택이 비었는지 확인하는 함수 

2.스택이 꽉 찼는지 확인하는 함수

3.스택의 top에 data를 집어넣는 함수

4.스택의 top에서 data를 제거하고 반환하는 함수

5.스택의 top에서 data를 제거하지 않고 반환하는 함수

 

 

 

일단 스택을 여러개 만들 수 있게 하려고 스택을 구조체로 만들어야한다.

만약 전역변수로 스택을 만들면 스택1개를 모두가 공유해야하기 때문이다.

#include <stdio.h>
#define MAX_STACK 100

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

 

 

 

그리고 스택을 생성한 후 초기화 해야할 함수도 필요할 것이다.

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

초기화는 stack top을 -1로 초기화 한다.

나중에 데이터를 넣을때, top을 0으로 옮긴후 데이터 삽입, top을 1로 옮긴 후 데이터 삽입

이런 방식으로 해야하기 때문이다.

 

 

 

1.스택이 비었는지 확인하는 함수

int is_empty(StackType *s)
{
    if(s->top == -1)
        return 1;
    else
        return 0;
}

스택의 top이 -1이면 데이터 삽입이 이뤄지지 않았다는 뜻으로

스택이 비었다고 볼 수 있다. 즉, 공백상태

공백 상태

공백상태는 이런 상태를 나타낸다.

 

 

 

2.스택이 꽉 찼는지 확인하는 함수

int is_full(StackType *s)
{
    if(s->top == MAX_STACK - 1)
        return 1;
    else
        return 0;
}

만약 스택이 가득 찼다면, stack top은 MAX_STACK - 1의 위치에 위치한다. (스택은 [0]부터 시작하기 때문에)

스택이 꽉 찼을 때

 

 

 

3.스택의 top에 data를 집어넣는 함수

void push(StackType *s, element item)
{
    if(is_full(s) == 1) //꽉 찼을때
        printf("full"); //full이라고 알려줌
    else
        s->data[++(s->top)] = item; //++로 top을 한칸 증가시킨후 그 인덱스에 data넣음
}

예를 들어, 비어있는 스택에 1을 넣어보면

1을 넣는다

top이 -1이었다가 ++top으로 0이된다.

즉, data[0]에 1을 넣는 것과 같다.

 

 

 

4.스택의 top에서 data를 제거하고 반환하는 함수

element pop(StackType *s)
{
    if(is_empty(s) == 1) //일단 스택이 비었는지 확인
        printf("empty");
    else
        return s->data[(s->top)--];
}

data배열에서 top을 뽑아낸 다음, top을 한칸 감소시킨다.(후위연산자 사용)

일단 data를 뽑아낸 후, top의 위치를 옮긴다. 라는게 핵심

 

 

 

5.스택의 top에서 data를 제거하지 않고 반환하는 함수

element peek(StackType *s)
{
    if(is_empty(s) == 1)
        printf("empty");
    else
        return s->data[s->top];
}

이번엔 데이터를 제거하지 않고, 현재 top에 있는 data만 반환하면 되기 때문에.

top의 위치를 변경할 필요가 없다. (후위 연산자를 사용할 필요가 없다.)

s->data[s->top]

---

스택에 데이터를 삽입·삭제 후, 스택을 출력해보자

int main(void)
{
    StackType s; //구조체 변수 선언
    init_stack(&s); //스택 초기화

    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d ", pop(&s));
    printf("%d ", pop(&s));
    printf("%d ", pop(&s));

    return 0;
}

스택에, 1넣고, 2넣고, 3넣는다.

상태

 

 

 

여기서 pop을 하면 top부터 한칸씩 추출한다.

---

전체코드)

#include <stdio.h>
#define MAX_STACK 100

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

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

int is_empty(StackType *s)
{
    if(s->top == -1)
        return 1;
    else
        return 0;
}

int is_full(StackType *s)
{
    if(s->top == MAX_STACK - 1)
        return 1;
    else
        return 0;
}

void push(StackType *s, element item)
{
    if(is_full(s) == 1)
        printf("full");
    else
        s->data[++(s->top)] = item;
}

element pop(StackType *s)
{
    if(is_empty(s) == 1)
        printf("empty");
    else
        return s->data[(s->top)--];
}

element peek(StackType *s)
{
    if(is_empty(s) == 1)
        printf("empty");
    else
        return s->data[s->top];
}

int main(void)
{
    StackType s;
    init_stack(&s); //스택 초기화

    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d ", pop(&s));
    printf("%d ", pop(&s));
    printf("%d ", pop(&s));

    return 0;
}