[C] 스택

스택은 말 그대로 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다. 상자 속에 책을 차례차례 쌓게되면 맨 밑의 책부터 빼내는 것이 불가능한 것 처럼 스택 역시 맨 위에서부터 접근하고 처리하는 자료구조이다. 이러한 자료구조는 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되기 때문에 후입선출구조라고 부른다. 스택은 같은 구조, 크기의 데이터를 한 방향으로 접근하여 쌓거나 반환하는 자료구조이며 아래쪽부터 위쪽으로 데이터를 쌓는다. 일반적으로 top 이라는 인덱스를 사용하며 데이터를 집어넣는 과정을 push, 데이터를 꺼내는 과정을 pop 이라고 한다.

#include <stdio.h>
#define s_size 100

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

int empty_check(){
    if (top == -1 ) return 1;
    else return 0;
}

int full_check(){
    if (top== s_size - 1) return 1;
    else return 0;
}

void push(int x){
    if (full_check()) return;
    else stack[ ++top ]= x;
    return;
}

int pop(){
    if (empty_check()) return -1;
    else return stack[top--];       
}

int main(){
    push(1);
    printf("%d\n", stack[top]);

    push(2); 
    push(3);
    pop();
    printf("%d", stack[top]);

    return 0;
}

1
2

스택을 구현하는 가장 간단한 방법은 일정 크기의 배열을통해 구현하는 방법으로 일정 크기의 stack 배열을 선언하여 사용한다. 첫 번째 요소가 저장될 위치의 인덱스가 0이기 때문에 연산의 편의를 위하여 top 은 -1로 초기화 된다. 미리 배열의 크기를 선언한다는 점에서 배열의 크기를 초과하지않는지, 그리고 배열이 비어있지 않은지에 대한 조건을 선행적으로 확인해야한다. 배열에서의 데이터 삽입은 top 인덱스를 증가시킨 위치에 값을 대입하며, 삭제는 현재 위치한 원소를 삭제 후 top을 1만큼 감소시키는(이동하는) 후치연산이 수행된다.

간단한 형태로 구현하는 stack 코드는 아래와 같다.

#include <stdio.h>

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

int main(){

    stack[++top]=1;
    printf("%d\n", stack[top]);

    stack[++top]=2; 
    stack[++top]=3;

    printf("%d", stack[--top]);

    return 0;
}

1
2