[C언어와 함께 자료구조를] 스택의 개념, 배열로 스택구현

스택(stack)과 다음에 공부할 큐(queue)와 같은 자료구조는 특정한 접근방식이 있고, 이를 응용한 알고리즘이 매우 다양합니다. 특히 스택은 아주 중요한 자료구조로 시스템 내부의 기본동작에서 고급 알고리즘까지 다양하게 활용되고 있습니다.

스택의 개념

스택의 구조는 매우 간단합니다. 스택은 밑이 막혀있는 긴 통이라고 보면 됩니다. 즉, 입구와 출구가 같은 긴 통이므로 먼저 들어간 것은 밑에 있게 되고, 나중에 들어간 것은 제일 먼저 나오게 됩니다. 그래서 스택을 LIFO(Last In First Out)구조라 고 합니다.

 

스택을 조작하는 방법(연산이라고 합니다.) 은 두가지가 있습니다. 하나는 스택에 값을 집어 넣는 연산인 push이고 다른 하나는 스택에서 값을 빼내는 pop 동작입니다. 위 그림을 보면 쉽게 이해가 될 것입니다.

배열로 스택 구현하기

배열을 이용하여 스택을 구현하는 것은 위의 그림과 같은 모양이 됩니다. 우선 스택의 긴 통을 정의 하고 스택의 마지막 데이터의 위치인 상단을 top이라는 배열 인덱스를 이용하겠습니다.

배열의 성격상 스택 이라는 통의 크기는 정해 놓아야 합니다. 일단 10이라고 잡겠습니다. 스택에 들어갈 데이터는 정수형이라고 가정하면 다음과 같이 정의 할 수 있습니다.

#define MAXSIZE 10   // 스택의 크기 정의

int stack[MAXSIZE];  // 스택의 긴 통

int top;                      // 스택의 상단

여기서 top의 위치를 정확히 규정해 봅니다. 어떤 경우는 top이 스택의 가장 위 데이터가 아니라 그 위, 즉, 다음에 들어갈 데이터 저장 공간을 가리키기도 합니다. 여기서는 가장 위의 데이터를 가리키는 것으로 정하겠습니다. 스택을 정의 할 때 두가지 중 하나를 선택해서 사용하여야 하며, 혼용되어서는 안됩니다.

그리고, 스택연산을 정의 할 때, 극단적인 경우, 즉, 데이터가 하나도 없을 때와 꽉 차있을 때에 약간 주의를 해야 합니다.

먼저, 스택이 비어 있는 경우 top은 -1의 값을 가져야 합니다. C에서 배열의 인덱스는 0부터 시작하므로, top이 0이라면 스택에 데이터가 하나 있다는 의미입니다. 스택이 비어있는 경우는 초기 스택이 생성되었을 때도 마찬가지 이므로 스택을 초기화 하려면 top을 -1로 설정하면 됩니다.

void init_stack () { 
    top = -1;
} 

이제, 스택의 연산인 push와 pop을 정의해 보겠습니다. push를 위해서는 값이 있어야 하므로 push의 함수 인자로 val이라는 양의 정수형을 사용하겠습니다. 그 후 push는 top을 하나 증가시키고 배열의 인덱스 top에 val을 넣으면 됩니다. 그런데, 앞서 말씀드렸듯이 스택이 꽉차있는 경우에 push를 하게 되면 스택이 넘쳐나게 됩니다. 이를 스택 오버플로우(Stack Overflow)라고 합니다. 그러므로 배열의 인덱스인 top이 MAX-1이 되었을 때 스택이 꽉차있는 경우이므로 예외 처리를 해야 합니다.

 int push(unsigned int val) {
    if (top >= MAXSIZE-1) {
        printf("\nStack Overflow\n");
        return -1;
    }

    stack[++top] = val;
    return val;
}

반대로 pop연산에 대해서도 마찬가지 입니다. top의 위치의 데이터를 리턴하고 top을 하나 감소시키면 됩니다. 여기서는 스택이 비어있는 경우 pop연산을 하면 스택 언더플로우(Stack Underflow)가 발생합니다. 스택이 텅 비어있는 경우 top이 -1 이므로 이 경우 예외 처리를 하면 됩니다.

int pop(void) {
    if (top < 0) {
        printf("\nStack Underflow\n");
        return -1;
    }

    return stack[top--];
} 

음... 끝났습니다. 별거 아니죠? 다음은 전체 소스코드 입니다.

#include <stdio.h>

#define MAXSIZE 10   // 스택의 크기 정의
int stack[MAXSIZE];  // 스택의 긴 통
int top;                     // 스택의 상단

void init_stack () { 
    top = -1;
}

int push(unsigned int val) {
    if (top >= MAXSIZE-1) {
        printf("\n   Stack Overflow\n");
        return -1;
    }
    stack[++top] = val;
    return val;
}

int pop(void) {
    if (top < 0) {
        printf("\n   Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}


void print_stack() {
    int i;
    printf ("\n Stack From Top-----> To Bottom\n");
    for (i = top; i>=0; i--)
        printf ("%-6d", stack[i]);
}

void main(void)
{
    int i;
    init_stack();
    
    printf ("\nPush 5, 4, 7, 8, 2, 1");
    push(5);
    push(4);
    push(7);
    push(8);
    push(2);
    push(1);
    print_stack();
    
    printf("\nPop");
    i = pop();
    print_stack();
    printf("\n  popped value is %d\n", i);
    
    printf("\nPush 3, 2, 5, 7, 2");
    push(3);
    push(2);
    push(5);
    push(7);
    push(2);
    print_stack();
    
    printf("\nNow Stack is full, push 3");
    push(3);
    print_stack();
    
    printf("\nInitialize stack");
    init_stack();
    print_stack();
    
    printf("\nNow Stack is empty, pop");
    i = pop();
    print_stack();
    printf("\n  popped value is %d\n", i);
}

실행결과입니다.

PS C:\CS> .\stack

Push 5, 4, 7, 8, 2, 1
 Stack From Top-----> To Bottom
1     2     8     7     4     5     
Pop
 Stack From Top-----> To Bottom
2     8     7     4     5     
  popped value is 1

Push 3, 2, 5, 7, 2
 Stack From Top-----> To Bottom
2     7     5     2     3     2     8     7     4     5     
Now Stack is full, push 3
   Stack Overflow

 Stack From Top-----> To Bottom
2     7     5     2     3     2     8     7     4     5     
Initialize stack
 Stack From Top-----> To Bottom

Now Stack is empty, pop
   Stack Underflow

 Stack From Top-----> To Bottom

  popped value is -1

다음시간에는 큐에 대해서 공부해 보죠.