스택 자료구조의 개념과 배열을 이용해서 C로 구현하는 방법

 

1. 스택(Stack)의 개념

 

스택은 한쪽으로 들어가서, 동일한쪽으로 나오는 자료구조다. 스택에 한쪽 방향으로 데이터를 넣는 Push와 스택에서 한 쪽 방향으로 데이터를 빼내는 Pop으로 이루어져 있다. 일반적으로 스택은 리스트처럼 생겼기 때문에 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방법으로 나뉜다.

 

Push(7) -> Push(8) -> Push(4) -> Pop() -> Push(2) -> Pop()

 

위 함수를 차례로 실행하면 다음 그림과 같다.

 

스택

 

 

2. 배열을 이용한 스택 구현

 

#include <stdio.h>
#define SIZE 10000
#define INF 99999999

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

 

먼저 전체 스택의 크기 SIZE를 10000으로 정해주고, INF에 무한대의 값을 넣어준다. top이라는 변수는 스택의 최상단을 의미하는데, 스택의 최상단은 다음 그림에서와 같다.

 

 

// 스택 삽입 함수
void push(int data) {
    if (top == SIZE - 1)
    {
        printf("스택오버플로우가 발생했습니다. \n");
        return;
    }
    stack[++top] = data;
}

// 데이터 추출 함수
int pop() {
    if (top == -1)
    {
        printf("스택언더플로우가 발생했습니다. \n");
        return -INF;
    }
    return stack[top--];
}

 

스택 삽입 함수인 push()는 top 인덱스에 1 더한 인덱스(다음 인덱스를 의미함)부터 차곡차곡 데이터를 넣어주는 것이다. 만약 top 인덱스가 9999를 넘는다면, 기존에 설정해 준 10000 인덱스는 존재하지 않으므로 더 이상 데이터가 들어갈 수 없다는 에러 메시지를 출력한다.

 

스택 데이터 추출 함수인 pop()은 현재 top이 가리키고 있는 원소의 값을 반환함과 동시에 top을 1 감소시켜 원소가 줄었음을 알리는 것이다. 만약 top이 -1이면 인덱스가 -1이면 원소가 하나도 없다는 의미이므로 마이너스 무한대 값을 리턴해서 오류가 발생했음을 출력한다.

 

// 스택 전체 원소 출력 함수
void show() {
    printf("스택의 최상단\n");
    for (int i = top; i >= 0; i--)
    {
        printf("%d\n", stack[i]);
    }
    printf("스택의 최하단\n");
}

 

최상단에서부터 원소가 빠져나와야 하기 때문에, for문에서 i는 top부터 시작해서 인덱스가 1씩 감소하며 그 인덱스에 해당하는 스택의 값을 차례로 출력하는 것이다. 

 

int main(void) 
{
    push(7);
    push(8);
    push(4);
    pop();
    push(2);
    pop();
    show();
}

스택의 최상단
8
7
스택의 최하단

 

앞서 그림으로 살펴 보았던 과정 그대로 출력이 된다. 

 

이렇게 배열을 이용하여 스택을 구현하면, 메모리 공간이 비효율적으로 활용된다. 스택의 크기만큼 배열을 미리 만들어줘야 하기 때문이다. 따라서 배열보다는 연결 리스트를 이용하는 것이 메모리를 효율적으로 할당하여 구현을 할 수 있다.