[자료구조] 1. Stack

1.1 스택이란?

LIFO(Last In, First Out)을 특성으로 하는 자료구조이다.

우리는 다양한 시스템 속에서 자연스럽게 스택 자료구조를 접하고 있다. 대표적인 예로 '뒤로 가기'는 방문 기록을 스택에 저장해두었다가 뒤로 가기 키를 누르게 되면 이전 페이지로 돌아간다. 또 한가지 예로는 function call stack이 있다. 코딩을 하다보면 무수히 많은 함수를 호출하게 된다. 이때 함수의 실행이 종료되면 함수를 호출한 부분으로 되돌아 가야한다. 그러므로 함수를 호출할 때마다 스택에 복귀할 주소를 저장해두게 되고 호출된 역순으로 복귀가 이루어지게 된다.

이 경우 main() 함수가 stack bottom에 저장된 후 a(), b()가 차례로 쌓인다. 5번 과정을 통해 b() 함수가 종료되면 스택에 저장해둔 복귀주소를 통해 a() 내부로 돌아가게되고 7번 과정이 차례대로 실행된다. 이러한 흐름으로 함수가 호출된다.

1.2 Pseudo code 구현

스택에서 가장 주목해야할 요소는 무엇일까? 스택이 LIFO의 특성을 가지고 있고, ADT를 통해 객체와 연산을 살펴본 결과 주요 연산은 모두 스택의 가장 상단에 있는 요소에 관한 연산임을 쉽게 알 수 있다. push, pop 등의 연산을 구현하기에 앞서 가장 상단의 요소를 가리키는 top변수를 정의해야 한다.

리스트의 첫 요소의 위치는 '0'이므로 초기 상태(공백 상태)에서는 top변수를 '-1'로 설정한다.
그리고 전역변수로써 SIZE를 설정한다. (동적 할당을 통해 필요한 만큼 메모리를 사용할 수도 있다. linked list를 통한 스택의 구현에서 소개.)

is_full(s):
	if(top >= SIZE-1)
    	then return TRUE;
    	else return FALSE;
        
is_empty(s):
	if(top == -1) 
    	then return TRUE;
    	else return FALSE;
        
push(s, x):
	if(is_full(s))
    	then error "OVERFLOW"
        else top <- top+1
        	 s[top] <- x

pop(s):
	if(is_empty(s))
    	then error "UNDERFLOW"
        else data <- s[top]
        	 top <- top-1
             return data

peek(s):
	if(is_empty(s))
    	then error "UNDERFLOW"
        else return s[top]

1.3 배열을 통한 스택 구현

#include <stdio.h>
#include <stdlib.h>
#define max_stack_size 10	// 스택 크기 전역 변수로 설정

typedef int element;	// 스택에 저장되는 데이터 타입 element로 정의 
						// 현재는 정수형으로 정의돼있지만 스택의 요소를 구조체로도 정의 가능
typedef struct{
    element stack[max_stack_size];
    int top;
} StackType;	// Stacktype을 가리키는 포인터를 각 함수의 매개변수로 전달

// 스택 초기화 함수
void init_stack(StackType *s){
    s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType *s){
    return (s->top == -1);   // TRUE면 1, FALSE면 0
}

// 포화 상태 검출 함수
int is_full(StackType *s){
    return (s->top == (max_stack_size-1));	// TRUE면 1, FALSE면 0
}

// 삽입 함수
void push(StackType *s, element x){
    if(is_full(s)){
        fprintf(stderr, "OVERFLOW");
        return;
    }
    else s->stack[++(s->top)] = x;    // top = top+1을 연산 후, s[top]에 x 대입
}

// 삭제 함수
element pop(StackType *s){
    if(is_empty(s)){
        fprintf(stderr, "UNDERFLOW");
        exit(1);
    }
    else return s->stack[(s->top)--];	// s[top] 값을 return 후, top = top-1 연산
}

int main()
{
    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;
    // 3 2 1 출력
}