스택(stack)

스택(stack)이란?

---

스택은 후입선출(Last In First Out)로 동작한다.

가장 마지막에 들어간 데이터가 가장 먼저 빠져나간다는 뜻이다.

 

스택이 실생활에 사용되는 예

 

 

제일 마지막에 작성한 코드부터 차례대로 되돌아가기 위해 우리는 Ctrl + z 키를 사용한다.

 

 

물건을 밑에서부터 차근차근 쌓아 올리고 계산할때는 맨 위, 즉, 제일 마지막에 올려서 위에 놓인 물건부터 계산대로 옮긴다.

 

 

컴퓨터는 사람처럼 계산을 할 수 없기 때문에 후위 표기법과 같이 계산한다.

 

쨌든 맨 처음 넣었던 데이터를 확인하려면 그 위에 쌓여있는 다른 데이터들을 꺼내야 확인할 수 있다.

 

스택의 구성

---

 

스택 구현

---

typedef struct Stack {
    int arr[100];
    int top;
}stack;

 

스택의 구조체 부분에는 100칸짜리 int형 배열과 맨 위에 있는 데이터를 저장할 수 있는 변수가 구성 되어있다.

 

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

 

스택을 만들때마다 초기화 시켜주는 함수이다.

배열은 인덱스 0부터 시작하니, top 변수에 -1을 넣어 초기화시켜줘서 스택이 비어있음을 말한다.

 

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

 

스택이 비어있는지 확인하는 함수이다.

만약 top 변수에 -1이 들어가있으면 스택이 비었다는 뜻이므로 1('참')을 반환하고

비어있지 않으면 0('거짓')을 반환한다.

 

int is_full(stack* s)
{
    if (s->top == 99)
        return 1;
    return 0;
}

 

스택이 가득 차있는지 확인하는 함수이다.

배열의 맨 끝 인덱스가 99이므로 top변수의 값이 99이면 1을 반환하고

그렇지 않다면 아직 가득 차지 않았으므로 0을 반환한다.

 

void push(stack* s, int data)
{
    if (is_full(s)) {
        printf("\nStack is full.\n");
        exit(1);
    }
    printf("pushed: %d\n", data);;
    s->arr[++(s->top)] = data;
}

 

데이터를 넣는 함수이다.

만약 스택이 가득 찼을 시 is_full 함수에서 1을 반환하여 스택이 가득 찼다는 문구를 남긴 뒤 시스템을 종료한다.

스택이 가득 차지 않았으면 push된 데이터를 출력한뒤 arr배열 현재 인덱스의 다음 인덱스에 데이터를 넣는다.

data = 1 일때, 현재 스택이 비어있다면 top = -1 이고, pushed : 1을 출력한다음 '++' 연산자가 앞에 놓여있으므로 배열의 인덱스가 0일때 data(1)를 넣는다.

 

int pop(stack* s)
{
    if (is_empty(s)) {
        printf("\nStack is empty.\n");
        exit(1);
    }
    return s->arr[(s->top)--];
}

 

데이터를 빠져나오게 하는 함수이다.

만약 빼낼 데이터가 없는 스택이 비어있는 상태일 때 is_empty함수에서 1을 반환하여 스택이 비었다는 문구를 남긴뒤 시스템을 종료한다.

아직 빼낼 데이터가 있다면 top에 위치한 데이터를 반환시켜주고난 후  top이 있던 인덱스가 한칸 빠지기 때문에 '--'를 후에 해준다.

 

int peek(stack* s)
{
    if (is_empty(s)) {
        printf("Stack is empty.\n");
        exit(1);
    }
    return s->arr[(s->top)];
}

 

현재 top에 있는 데이터를 알려주는 함수이다.

스택이 비어있을시에는 pop함수와 마찬가지로 스택이 비어있음을 알린뒤 시스템을 종료한다.

비어있지 않다면 현재 스택의 맨 끝(위, top)에 위치한 데이터를 반환한다.

 

int main()
{
    stack s;
    init(&s);    // stack 
 
    push(&s, 3);
    push(&s, 2);
    push(&s, 1);
 
    printf("\ntop check : %d\n\n", peek(&s));
    printf("pop : %d\n", pop(&s));
    printf("pop : %d\n", pop(&s));
    printf("pop : %d\n", pop(&s));
 
    printf("\npop : %d\n", pop(&s));    // empty
 
    return 0;
}

 

스택에 데이터를 3, 2, 1 순으로 집어넣은 뒤 top에 있는 데이터가 무엇인지 확인한다. 그리고 pop함수를 이용해서 맨 나중에 들어간 데이터부터 빼내며 출력한다.

마지막에는 모든 데이터가 다 빠져나가서 스택이 비어있으니 스택이 비어있다고 알린 후 시스템을 종료한다.

 

 

결과♬