Chap 06. 스택 (Stack) , 배열 기반 스택

스택은 Last In First Out (후입선출)의 자료구조.

---

스택의 추상 자료형 (ADT)

리스트의 ADT는 필요에 따라 정의 내용의 차이가 있을수 있지만 스택의 ADT는 거의 동일하게 표현된다. 

 

void StackInit(Stack *pstack);

- 스택의 초기화 

- 스택 생성 후 가장 먼저 호출되어야 하는 함수 

 

int SIsEmpty(Stack *pstack);

- 스택이 빈경우 true, else false 반환 

 

void SPush(Stack *pstack, Data data);

- 스택에 데이터 저장. 매개변수 data로 전달된 값을 저장함.

 

Data SPop(Stack *pstack);

- 마지막에 저장된 요소를 삭제

- 삭제된 데이터는 반환함 

- 이 함수의 호출을 위해서는 스택에 데이터가 최소 한개 있음이 보장되어야 한다 

 

Data SPeek(Stack *pstack); 

- 마지막에 스택에 푸쉬한 요소를 들여다본다 (반환하되 삭제하지 않음) 

- 이 함수의 호출을 위해서는 스택에 데이터가 최소 한개 있음이 보장되어야 한다 

 

---

스택은 배열 기반으로 구현할수도 있고, 연결 리스트를 기반으로 구현할수도 있다.

 

배열 기반 스택 

배열 기반 스택은 스택의 가장 마지막에 저장된 데이터의 위치를 가르키는 topIndex를 선언하고, 데이터를 넣는 push 연산이 수행될때는 topIndex를 증가시키고, 데이터를 빼는 pop 연산이 수행될때는 topIndex를 감소시키는 방식으로 간단히 구현된다.

 

ArrayBaseStack.h 

/*
 * 배열을 기반으로 구현한 스택
 */
#ifndef CHAP06_ARRAYBASESTACK_ARRAYBASESTACK_H
#define CHAP06_ARRAYBASESTACK_ARRAYBASESTACK_H

#define TRUE 1
#define FALSE 0
#define STACK_LEN 100

typedef int Data;

typedef struct _arrayStack
{
    Data stackArr[STACK_LEN]; // 배열 기반 스택
    int topIndex;
} ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack *pstack);
int SIsEmpty(Stack *pstack);

void SPush(Stack *pstack, Data data);
Data SPop(Stack *pstack);
Data SPeek(Stack *pstack);


#endif //CHAP06_ARRAYBASESTACK_ARRAYBASESTACK_H

ArrayBaseStack.c

#include "ArrayBaseStack.h"
#include <stdio.h>
#include <stdlib.h>

void StackInit(Stack *pstack)
{
    pstack->topIndex = -1;
}

int SIsEmpty(Stack *pstack)
{
    if(pstack->topIndex == -1) return TRUE;
    else return FALSE;
}

void SPush(Stack *pstack, Data data)
{
    pstack->topIndex += 1; // top 한칸 위로
    pstack->stackArr[pstack->topIndex] = data; // 데이터 추가
}

Data SPop(Stack *pstack)
{
    int rIdx;

    if(SIsEmpty(pstack))
    {
        printf("Stack Memory Error\n");
        exit(-1);
    }

    rIdx = pstack->topIndex;
    pstack->topIndex -= 1;

    return pstack->stackArr[rIdx];
}

Data SPeek(Stack *pstack)
{
    if(SIsEmpty(pstack))
    {
        printf("Stack Memory Error\n");
        exit(-1);
    }
    return pstack->stackArr[pstack->topIndex];
}

ArrayBaseStackMain.c

#include <stdio.h>
#include "ArrayBaseStack.h"

int main()
{
    Stack stack;
    StackInit(&stack);

    // data push
    SPush(&stack, 1);
    SPush(&stack, 2);
    SPush(&stack, 3);
    SPush(&stack, 4);

    // data pop
    while(!SIsEmpty(&stack))
        printf("%d ", SPop(&stack));
}

결과 

Last In First Out의 특성이 잘 나타난다.

 

---