[스택] 스택의 개념과 구현

작성일 | In

이번 글에서는 스택의 개념을 설명하고, 간단히 구현하는 것 까지 다루겠습니다.

스택이란?

스택은 후입선출(Last In First Out, LIFO), 선입후출(First In Last Out, FILO)의 형태를 가진 자료구조입니다.
예를 들어, 물건을 위로 쌓아 올리고 다시 꺼낼 때에는 먼저 쌓은 것이 나중에 나오게 됩니다. 이러한 구조를 스택 이라고 부릅니다.

그림으로 간단히 나타내봅시다.
스택은 출입구가 1개입니다. 즉, 데이터의 삽입과 제거가 한 곳에서 모두 이뤄집니다.
스택의 맨 위에 데이터를 삽입하고, 맨 위에서 데이터를 제거합니다. 그러므로 먼저 들어간 데이터가 늦게 나오고, 나중에 들어간 데이터가 먼저 나오는 구조를 갖게 됩니다.

underflow와 overflow

주의해야 할 점이 있습니다.
만약 데이터의 개수가 스택의 크기를 초과하면 overflow 오류가 일어납니다.
또한, 스택에 아무것도 없는데 pop을 하거나 맨 위에 있는 데이터에 접근하려고 하면 underflow 오류가 일어납니다.
그러므로 구현을 할 때 overflow와 underflow 예외처리를 잘 해주어야 합니다.

구현 방법

이제 구현을 해봅시다.

먼저, 스택의 최대 크기를 정해줍시다.

1
#define size 100

그 후, 스택을 선언해고 top(가장 나중에 들어온 데이터의 인덱스)을 -1로 설정합니다.

1
2
int stack[size];
int top=-1;

push

이제 push기능을 구현해봅시다.
먼저 overflow 오류를 예외처리 해줘야 합니다.
overflow가 발행하면 stdlib.h에 있는 exit 함수를 써서 프로그램을 종료 시키는 방법을 쓰겠습니다.

1
2
3
4
if(top>=size-1){
    printf("\n\nStack is FULL\n");
    exit(1);
}

만약 overflow가 나오지 않으면 top이 가리키는 곳 보다 한 칸 위에 새로운 값을 저장합니다.

1
stack[++top]=item;

push함수의 전체 코드입니다.

1
2
3
4
5
6
7
8
void push(int item){
    if(top>=size-1){
        printf("\n\nStack is FULL\n");
        exit(1);

    }
    else stack[++top]=item;
}

pop

이제 맨 위에 있는 데이터를 제거하면서 그 값을 반환하는 pop기능을 구현해봅시다. pop은 underflow 오류를 처리해야 합니다.
top이 -1이면 데이터가 아무것도 없는 상태이기 때문에 top == -1 일 때 pop을 하게 되면 underflow가 발생합니다.

1
2
3
4
if(top==-1){
    printf("\n\nStack is Empty\n");
    exit(1);
}

underflow가 일어나지 않는다면 top을 한 칸 아래로 낮춰서 위에 있던 값들을 신경쓰지 않게 하면 됩니다.
그 값을 반환까지 하는 코드는 다음과 같습니다.

1
return stack[top--];

pop함수의 전체 코드입니다.

1
2
3
4
5
6
7
int pop(){
    if(top==-1){
        printf("\n\nStack is Empty\n");
        exit(1);
    }
    else return stack[top--];
}

peek(top)

다음으로는 peek함수를 구현해봅시다.
pop함수는 값을 제거한 뒤 그 값을 반환했지만, peek함수는 맨 위의 값을 반환하고, 제거는 하지 않습니다.
이 함수 또한 underflow 처리를 해줘야 하는데 위의 내용과 겹치므로 설명은 생략하겠습니다.

peek함수의 전체 코드입니다.

1
2
3
4
5
6
7
int peek(){
    if(top==-1){
        printf("\n\nStack is Empty\n");
        exit(1);
    }
    else return stack[top];
}

del

마지막으로 스택 맨 위에 있는 값을 제거하는 del함수를 만들겠습니다.
pop함수는 마지막에 값을 반환하지만 del함수는 반환하지 않습니다.

1
2
3
4
5
6
7
void del(){
    if(top==-1){
        printf("\n\nStack is Empty\n");
        exit(1);
    }
    else top--;
}

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <stdlib.h>

#define size 100

int stack[size];
int top=-1;

void push(int item){
    if(top>=size-1){
        printf("\n\nStack is FULL\n");
        exit(1);
    }
    else stack[++top]=item;
}

int pop(){
    if(top==-1){
        printf("\n\nStack is Empty\n");
        exit(1);
    }
    else return stack[top--];
}

void del(){
    if(top==-1){
        printf("\n\nStack is Empty\n");
        exit(1);
    }
    else top--;
}

int peek(){
    if(top==-1){
        printf("\n\nStack is Empty\n");
        exit(1);
    }
    else return stack[top];
}