아래 내용은 뇌를 자극하는 알고리즘을 참고하며 공부한 것을 정리한 내용입니다.
Stack?
스택(Stack)은 처음 들어간 것이 가장 마지막에 나오도록 되어있는 형태의 자료구조 입니다.
이러한 구조를 FILO(First In Last Out)라고도 부르데 마치 바구니를 채워넣는것과 비슷하며, 아래 그림처럼 나타낼 수 있습니다.
그림에서 제일 왼쪽에는 저장공간에 데이터를 하나 씩 쌓고있습니다. 데이터는 1번부터 들어가서 제일 밑에, 데이터 3번은 마지막으로 들어가서 제일 위에 위치해 있습니다.
제일 오른쪽에는 저장공간에서 데이터를 하나 씩 빼는 과정입니다. 데이터는 가장 위에있는 3번부터 순서대로 빠져나옵니다.
스택의 기능은 크게 삽입(Push)과 제거(Pop)이 있습니다. 위 그림에서 제일 왼쪽에는 데이터를 하나씩 넣는 삽입이며, 오른쪽의 데이터를 하나씩 제거하는 것은 제거 입니다.
주요 연산 구현
스택을 구현하는 방법 중 하나로 배열을 이용하는 방법이 있습니다. 배열을 이용하면 구현이 간단하지만 동적으로 스택의 용량을 조절하기 어려운 단점이 있습니다.
실제로 C를 활용해 작업할 때는 STL에 스택과 같은 형태의 Vector가 많이 사용됩니다.
배열을 활용한 구현
1. 노드
가장 간단한 형태의 노드를 생성하기 위해 int형 데이터 하나만 다루는 노드를 아래와 같이 구현할 수 있습니다.
만약 좀 더 복잡한 형태의 데이터를 활용해 스택구조를 만든다면 아래 노드안에 필요한 데이터 종류를 추가하여 구현할 수 있습니다.
typedef struct tagNode
{
int data;
} Node;2. 생성/소멸
앞에서 구현한 노드를 쌓는 스택을 구현하기 위해서 동일하게 구조체를 사용합니다.
스택을 만들 때 필요한 정보는 스택의 용량, 최상단 스택의 Index, 노드의 주소값 입니다.
typedef struct tagArrayStack
{
int Capacity; // 스택의 용량
int Top; // 스택의 최상위 노드 index
Node* Nodes; // 노드 배열
} ArrayStack;구현된 스택 구조체를 생성하기 위해서는 스택에 메모리를 할당하고 용량, 최상단 노드위치, 노드자체의 메모리 할당하는 세 가지 과정이 필요합니다.
// 스택 생성
void CreateStack(ArrayStack** Stack, int Capacity)
{
// 스택을 자유 저장소에 생성
*Stack = new ArrayStack;
// 입력된 Capacity만큼의 노드를 자유저장소에 생성
(*Stack)->Nodes = new Node[Capacity];
// Capacity 및 Top 초기화
(*Stack)->Capacity = Capacity; // 스택의 용량 설정
(*Stack)->Top = 0; // 최상단 노드의 index를 초기화
}활용이 끝난 스택은 메모리를 해제하여 소멸시켜야 합니다.
// 스택 삭제
void DestoryStack(ArrayStack* Stack)
{
// 스택 안의 노드들의 메모리 해제
delete Stack->Nodes;
// 스택 자체의 메모리 해제
delete Stack;
}3. 삽입(Push)
스택에 새로운 데이터를 삽입(Push)할 때는 최상단에 새로운 노드 값을 입력한 뒤, 스택의 최상단에 대한 위치(index)를 업데이트 해주어야 합니다.
// 스택 삽입
void Push(ArrayStack* Stack, int data)
{
int position = Stack->Top;
Stack->Nodes[position].data = data; // 최상단 노드에 데이터 추가
Stack->Top++; // 최 상단 노드위치 한칸 뒤로
}4. 제거(Pop)
스택에서 값을 빼내는 제거(Pop)에서는 땐 최상단 노드의 위치를 한칸 아래로 내리고, 최상단 노드의 값을 반환해 주어야 합니다.
int Pop(ArrayStack* Stack)
{
int position = --(Stack->Top); // 최상단 노드위 위치를 한칸 아래로
return Stack->Nodes[position].data; // 최상단 노드의 값을 반환
}