C언어 : 스택(stack) , 배열을 사용해 스택 구현하기

스택 (Stack)

 

자료를 저장하는 구조중에는 스택(stack)이라고 하는 것이 있다.

스택은 입구가 하나인 통과 같은 구조로, 가장 나중에 삽입되어 저장된 자료가 가장 먼저 삭제되어 나온다.

스택에 자료를 삽입하는 동작을 push라고 하며, 스택에서 자료를 삭제하여 얻는 것을 pop 동작이라고한다.

스택은 배열을 사용하여 구현할 수 있다. 배열의 크기는 저장할 수 있는 자료의 최대 개수로 선언을 한다.

스택의 top은 가장 최근에 저장된자료의 배열 첨자를 나타낸다.

처음에는 저장된 원소가 없으므로 top은 -1로 초기화한다.

push 동작은 top을 증가시킨다음, top 위치의 배열 원소에 자료를 저장한다.

pop 동작은 top 위치의 자료를 반환한 다음, top을 감소시킨다.

 

아래는 문자를 저장하는 스택을 구현한 것이다.

#define MAXSIZE 500
#define STACKEMPTY  -1
 
char stack[MAXSIZE];
int top = -1;
 
void push(char item) {
    if (top >= MAXSIZE - 1) {
        printf("stack is full\n");
        return;
    }
    top++;
    stack[top] = item;
}
 
char pop(void) {
    char item;
    
    if (top < 0)
        return STACKEMPTY;
    item = stack[top];
    top--;
    return item;
}

 

다음과 같이 main함수를 작성하여 입력 문자들을 스택에 저장한 후에 스택에서 꺼내어 출력하면 문자가 입력된 역순으로 출력된다.

void push(char item);
char pop();
 
int main() {
    int ch;
 
    //EOF를 만날 때 까지 문자를 입력하여 스택에 삽입한다.
    while ((ch != getchar()) != EOF)
        push(ch);
    //스택에서 삭제하면서 입력된 문자를 꺼내어 출력한다.
    while ((ch = pop()) != STACKEMPTY)
        putchar(ch);
 
    return 0;
}