[자료구조] 배열(Array)을 기반으로 스택(Stack) 구현하기

배열을 기반으로 스택 구현하기

배열을 이용한 스택은 용량을 동적으로 변경하는 비용이 크다는 단점이 있지만, 구현이 간단하다는 장점도 있습니다.

배열 기반의 스택은 각 노드를 동적으로 생성하고 제거하는 대신, 스택 생성 초기에 프로그래머가 부여한 용량만큼의 노드를 한꺼번에 생성합니다. 그 후 최상위 노드의 위치를 나타내는 변수를 두고 삽입과 제거 연산을 수행합니다.

 

-각 층을 구성할 노드와 스택의 구조체

typedef struct tagNode{
    ElementType Data;
} Node;

 

노드의 위치는 배열의 인덱스로 알 수 있기 때문에 데이터만 담고 있으면 됩니다.

 

typedef struct tagArrayStack{
    int Capacity;   //용량
    int Top;    //최상위 노드
    Node* Nodes;    //노드 배열
} ArrayStack;

 

몇개의 노드를 가질 수 있는지 알 수 있는 스택의 용량, 최상위 노드에 접근할 수 있는 위치, 쌓이는 노드를 보관할 노드 배열을 가집니다.

 

-스택의 생성과 소멸

void AS_CreateStack(ArrayStack** Stack, int Capacity){  //스택 생성
    (*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack)); //스택을 Heap에 생성

    (*Stack)->Nodes = (Node*)malloc(sizeof(Node)*Capacity); //입력된 Capacity만큼의 노드를 Heap안의 Stack에 생성
    (*Stack)->Capacity = Capacity;
    (*Stack)->Top = -1;
}

 

첫번째 malloc()함수로 Heap공간에 ArrayStack공간을 할당해주고

두번째 malloc()함수로 Heap 안에 있는 ArrayStack에 노드배열의 공간도 할당해줍니다.

이렇게되면 Heap공간에 ArrayStack안에 있는 노드만큼의 스택이 생성됩니다.

 

void AS_DestroyStack(ArrayStack* Stack){
    free(Stack->Nodes);
    free(Stack);
}

 

Heap에 공간을 할당한 경우 후에 프로그램 종료 전에 free를 잊으면 안되겠죠! 소멸 함수를 만들어 메모리 누수를 막아줍시다.

 

-노드 삽입 연산(Push)

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

 

최상위 노드의 인덱스(Top) 위에 값을 저장하고 그 노드가 새로운 Top이 됩니다.

 

-노드 제거 연산(Pop)

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

 

최상위 노드의 인덱스(Top)를 줄여주면 전의 노드가 Top이 됩니다.

주의할 점은 제거 연산에서는 최상위 노드에 있던(제거 되는) 노드의 데이터를 호출자에게 반환합니다.

 

-그 외 연산

• 최상위 인덱스(Top) 반환

ElementType AS_Top(ArrayStack* Stack){
    return Stack->Nodes[Stack->Top].Data;
}

 

• 스택 크기(Size) 반환

ElementType AS_GetSize(ArrayStack* Stack){
    return Stack->Top + 1;
}

 

• 스택이 비어있는지 bool값 반환

bool AS_isEmpty(ArrayStack* Stack){
    if(Stack->Top == -1) return true;
    else return false;
}