[자료구조] 배열 기반 스택 구현

배열 기반 스택

---

배열 기반 스택

• 데이터만 담는 구조체로 노드를 표현
• 스택 구조체의 경우 용량, 최상위 노드의 위치, 노드 배열 총 3가지 필드를 가지고 있어야 함

typedef struct tagArrayStack {
    int Capacity;
    int Top;
    Node* Nodes; // 자유 저장소에 할당된 배열을 가리키는 용도로 사용(첫 번째 요소)
} ArrayStack;

배열 기반 스택의 함수

• 생성

void AS_CreateStack(ArrayStack** Stack, int Capacity)
{
    //  스택을 자유저장소에 생성 
    (*Stack)           = (ArrayStack*)malloc(sizeof(ArrayStack));

    //  입력된 Capacity만큼의 노드를 자유저장소에 생성 
    (*Stack)->Nodes    = (Node*)malloc(sizeof(Node)*Capacity);

    //  Capacity 및 Top 초기화 
    (*Stack)->Capacity = Capacity;
    (*Stack)->Top = -1;
}

• 소멸

void AS_DestroyStack(ArrayStack* Stack)
{
    //  노드를 자유 저장소에서 해제 
    free(Stack->Nodes);

    //  스택을 자유 저장소에서 해제 
    free(Stack);
}

• 삽입

void AS_Push(ArrayStack* Stack, ElementType Data)
{
    Stack->Top++;
    Stack->Nodes[Stack->Top].Data = Data;
}

• 삭제

ElementType AS_Pop(ArrayStack* Stack)
{
    int Position = Stack->Top--;
    return Stack->Nodes[Position].Data;
}

예제 프로그램

#include "ArrayStack.h"

int main( void )
{
    int i= 0;
    ArrayStack* Stack = NULL;

    AS_CreateStack(&Stack, 10);

    AS_Push(Stack, 3);
    AS_Push(Stack, 37);
    AS_Push(Stack, 11);
    AS_Push(Stack, 12);

    printf( "Capacity: %d, Size: %d, Top: %d\n\n", 
        Stack->Capacity, AS_GetSize(Stack), AS_Top(Stack) );

    for ( i=0; i<4; i++ )
    {
        if ( AS_IsEmpty(Stack) )
            break;

        printf( "Popped: %d, ", AS_Pop(Stack) );

        if ( ! AS_IsEmpty(Stack) )
            printf( "Current Top: %d\n", AS_Top(Stack) );
        else
            printf( "Stack Is Empty.\n" );
    }

    AS_DestroyStack(Stack);

    return 0;
}

참조) 박상현, 『이것이 자료구조+알고리즘이다 with C언어』, 한빛미디어(2022)