이번 주제는 스택(Stack)입니다.
스택은 선입후출(First In Last Out)의 구조로 먼저 들어간 데이터보다 나중에 들어간 데이터가 먼저 나오는 자료구조입니다.
뒤로 가기와 앞으로 가기의 기능 구현 등을 포함한 우리가 사용하고 있는 여러 프로그램에서 볼 수 있습니다.
스택은 배열과 링크드 리스트로 구현 가능 합니다.
그 중에서 배열은 구현이 쉽다는 장점과 용량을 동적으로 할당할 수 없다는 단점을 가지고 있습니다.
배열 스택 구조체
이전에 구현했던 자료들처럼 스택을 구성하는 노드들을 만듭니다.
|
1
2
3
4
5
|
// AS 노드
typedef struct Node
{
ElementType Data;
} Node;
|
배열 스택을 구성하는 노드 구조체입니다.
연결 리스트처럼 다음 노드의 위치를 저장할 필요가 없기 때문에, 다음 노드를 저장할 포인터가 필요 없이 데이터를 담을 멤버로 구성합니다.
|
1
2
3
4
5
6
7
|
// AS 구조체
typedef struct tagArrayStack
{
int Capacity;
int Top;
Node* Nodes;
} ArrayStack;
|
생성한 배열 스택의 용량 Capacity, 현재 높이를 저장하고 있는 Top, 스택에 넣을 노드 배열로 구성되어 있습니다.
배열 스택 - 구현
배열 스택의 주요 연산은 초기화, 데이터 추가, 제거, 맨 위 데이터의 확인 등이 있습니다.
- 스택 생성(Create)
- 스택 제거(Destroy)
- 스택 데이터 추가 (Push)
- 스택 데이터 제거(Pop)
- 스택 맨 위 데이터 반환(Top)
- 스택 크기(GetSize)
- 스택 비어 있는지 확인(IsEmpty)
1. 배열 스택 - 생성
배열 스택을 생성하고 초기화를 하는 연산입니다.
스택 구조체와 용량을 받아서 크기만큼 할당합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// AS 생성
void AS_CreateStack(ArrayStack** Stack, int Capacity)
{
// 스택을 자유 저장소에 할당
(*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack));
// 스택 용량만큼 노드를 자유 저장소에 할당
(*Stack)->Nodes = (Node*)malloc(sizeof(Node) *Capacity);
// 스택 용량과 Top 초기화
(*Stack)->Capacity = Capacity;
(*Stack)->Top = 0;
}
|
malloc () 함수를 사용해서 배열 스택과 노드를 동적으로 할당합니다.
생성한 배열 스택은 현재 비어 있으므로 Top를 0으로 초기화 합니다.
2. 배열 스택 - 소멸
자유저장소에 동적으로 생성했던 배열 스택과 노드를 소멸시키는 연산입니다.
free() 함수를 사용해서 할당한 메모리를 해제합니다.
|
1
2
3
4
5
6
7
8
9
|
// AS 소멸
void AS_DestroyStack(ArrayStack* Stack)
{
// 배열 스택 노드를 자유 저장소에서 해제
free(Stack->Nodes);
// 배열 스택을 자유 저장소에서 해제
free(Stack);
}
|
메모리가 누수되지 않도록, 먼저 할당된 노드들을 free() 함수로 해제하고 배열 스택을 해제합니다.
3. 배열 스택 - 데이터 삽입(Push)
생성된 배열 스택에 데이터를 추가하는 Push 연산입니다.
해당 연산은 Data를 받아서 Top 위치에 넣어주는 연산입니다.
C언어에서 인덱스는 0부터 시작하기 때문에 스택을 초기화할 때 Top의 위치를 0으로 했습니다.
현재 인덱스에 Data를 넣어준 다음에 스택의 위치를 나타내주는 Top의 위치를 증가시킵니다.
|
1
2
3
4
5
6
7
8
|
// AS 데이터 삽입
void AS_Push(ArrayStack* Stack, ElementType Data)
{
int Position = Stack->Top;
Stack->Nodes[Position].Data = Data;
Stack->Top++;
}
|
코드 구현에 따라서 -1로 초기화하고 스택의 위치를 증가시킨 다음에 Data를 넣주는 방식도 있습니다.
|
1
2
3
4
5
6
7
8
9
10
|
// AS Top을 -1로 초기화
void AS_CreateStack(ArrayStack** Stack, int Capacity)
{
(*Stack)->Top = -1;
}
// AS 데이터 삽입
void AS_Push(ArrayStack* Stack, ElementType Data)
{
Stack->Nodes[++Stack->Top].Data = Data;
}
|
4. 배열 스택 - 데이터 제거(Pop)
스택에서 넣었던 마지막 요소를 빼주는 연산입니다.
마지막 요소를 꺼내주는 연산으로 Top의 이전 요소에 접근합니다.
|
1
2
3
4
5
6
7
|
// AS 데이터 제거
ElementType AS_Pop(ArrayStack* Stack)
{
int Position = --(Stack->Top);
return Stack->Nodes[Position].Data;
}
|
배열 스택의 Top 위치를 1만큼 감소시키고, 해당 위치의 노드의 데이터에 접근합니다.
5. 배열 스택 - 맨 위 데이터 반환(Top)
배열 스택의 Top의 위치를 구하는 연산입니다.
Top으로 접근하면 간단하게 구할 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// AS 맨 위 데이터 반환
ElementType AS_Top(ArrayStack* Stack)
{
int Position = Stack->Top - 1;
if (AS_IsEmpty(Stack))
{
printf("Stack is Empty\n");
exit(-1);
}
return Stack->Nodes[Position].Data;
}
|
6. 배열 스택 - 크기
배열 스택의 크기를 구하는 연산입니다.
우리가 스택의 구조체에 만들어줬던 Top와 스택의 크기는 동일하기 때문에 Top를 반환해줍니다.
|
1
2
3
4
5
|
// AS 크기 반환
int AS_GetSize(ArrayStack* Stack)
{
return Stack->Top;
}
|
7. 배열 스택 - 비여있는지 여부
배열 스택이 비여있는지 확인하는 연산입니다.
현재 Top의 위치가 0일 경우 해당 배열 스택은 비여있기 때문에 확인해서 반환합니다.
|
1
2
3
4
5
|
// AS 비여있는지 여부
int AS_IsEmpty(ArrayStack* Stack)
{
return (Stack->Top == 0);
}
|
댓글