구현한 배열 스택(Array Stack)은 자유 저장소에 동적으로 생성되지만, 한 번에 용량을 전달 받아서 생성하게 됩니다.
전달 받은 용량만큼 스택을 사용할 수 있고, 배열인만큼 크기를 변경할 수 없다는 단점을 가지고 있습니다.
링크드 리스트는 배열의 크기 고정에 대한 단점을 보안합니다.
배열 스택의 단점을 보안하기 위해 연결 리스트를 사용한 링크드 리스트 스택을 구현합니다.
연결 리스트 스택 구조체
배열 스택과 다르게 연결 리스트 스택은 인덱스로 접근하지 않고 노드안의 포인터를 사용합니다.
연결 리스트처럼 스택의 노드 구조체 안에 다음 노드를 가리킬 Next 포인터를 만들어줍니다.
|
1
2
3
4
5
6
|
// 스택의 노드 구조체
typedef struct Node
{
ElementType Data;
struct Node* Next;
} Node;
|
배열 스택은 스택을 생성하기 전에 용량이 필요했지만, 링크드 리스트 스택은 스택에 담을 리스트와 위치를 알려줄 탑의 위치만 알고 있으면 됩니다.
|
1
2
3
4
5
6
|
// LinkedListStack 구조체
typedef struct tagLinkedListStack
{
Node* List;
Node* Top;
} LinkedListStack;
|
스택은 마지막에 넣은 데이터가 먼저 나오는 구조이기 때문에, Top의 위치를 연결 리스트의 Tail이라고 생각합니다.
Tail 위치에서 새로운 데이터를 넣어주거나 삭제를 해준다고 생각합니다.
물론 List를 통해서 순차적으로 탐색하면 Tail의 위치를 접근할 수 있지만, 노드의 개수만큼 전부 탐색하는 O(n) 만큼의 시간이 걸립니다.
하지만 Top의 위치를 언제나 가지고 있다면 O(1)을 만족합니다.
연결 리스트 스택 - 구현
연결 리스트 스택의 주요 연산은 초기화, 데이터 추가, 제거, 맨 위 데이터의 확인 등이 있습니다.
- 스택 생성(Create)
- 스택 제거(Destroy)
- 스택 데이터 추가 (Push)
- 스택 데이터 제거(Pop)
- 스택 맨 위 데이터 반환(Top)
- 스택 크기(GetSize)
- 스택 비어 있는지 확인(IsEmpty)
1. 연결 리스트 스택 - 생성
연결 리스트 스택을 생성하고 초기화를 하는 연산입니다.
이전에 구현했던 배열 스택과는 다르게 용량이 필요없습니다.
|
1
2
3
4
5
6
7
8
9
10
|
// LLS 생성
void LLS_CreateStack(LinkedListStack** Stack)
{
/// 스택을 자유 저장소에 할당
(*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack));
// 스택 초기화
(*Stack)->List = NULL;
(*Stack)->Top = NULL;
}
|
자유 저장소에 연결 리스트 스택을 생성합니다.
2. 연결 리스트 스택 - 제거
자유저장소에 동적으로 생성했던 연결 리스트 스택과 노드를 소멸시키는 연산입니다.
free() 함수를 사용해서 할당한 메모리를 해제합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// LLS 소멸
void LLS_DestroyStack(LinkedListStack* Stack)
{
// 스택에 쌓여있는 노드를 모두 제거
while (!LLS_IsEmpty(Stack))
{
Node* Popped = LLS_Pop(Stack);
LLS_DestroyNode(Popped);
}
// 스택을 자유 저장소에서 해제
free(Stack);
}
|
스택을 자유 저장소에 해제하기 전에 스택에 쌓여있는 모든 노드들을 해제합니다.
3. 연결 리스트 스택 - 노드 추가
연결 리스트 스택의 노드를 생성하는 함수입니다.
노드를 자유 저장소에 할당하고 초기화한 다음에 생성한 노드의 주소값을 반환합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// LLS 노드 생성
Node* LLS_CreateNode(ElementType Data)
{
// 노드를 자유 저장소에 할당
Node* NewNode = (Node*)malloc(sizeof(Node));
// 노드 초기화
NewNode->Data = Data;
NewNode->Next = NULL;
// 생성한 노드의 주소값 반환
return NewNode;
}
|
4. 연결 리스트 스택 - 노드 소멸
생성된 연결 리스트 스택의 노드를 자유 저장소에서 해제하는 함수입니다.
|
1
2
3
4
5
|
// LLS 노드 소멸
void LLS_DestroyNode(Node* Node)
{
free(Node);
}
|
5. 연결 리스트 스택 - 데이터 삽입(Push)
연결 리스트 스택에 데이터를 넣는 Push 연산입니다.
우리가 구현했던 링크드 리스트에서 Tail 뒤에 노드를 추가하는 연산과 같습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
// LLS 데이터 삽입
void LLS_Push(LinkedListStack* Stack, Node* NewNode)
{
if (Stack->List == NULL)
{
Stack->List = NewNode;
}
else
{
Node* OldTop = Stack->List;
while (OldTop->Next != NULL)
{
OldTop = OldTop->Next;
}
OldTop->Next = NewNode;
}
Stack->Top = NewNode;
}
|
노드가 하나도 없는 빈 스택인 경우에 새 노드를 넣어주고, 아닌 경우 while문을 통해서 Top을 찾고 다음 노드에 새 노드를 넣어줍니다.
6. 연결 리스트 스택 - 데이터 제거(Pop)
연결 리스트 스택에서 데이터를 제거하는 연산입니다.
다른 연산과는 다르게 스택의 마지막 요소를 제거하는 연산입니다.
스택의 Top은 마지막 노드의 주소를 가지고 있으므로 제거할 노드를 먼저 제거해서 반환을 하게 되면 Top의 위치를 잃어버리게 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
// LLS 데이터 제거
Node* LLS_Pop(LinkedListStack* Stack)
{
Node* TopNode = Stack->Top;
if (Stack->List == Stack->Top)
{
Stack->List = NULL;
Stack->Top = NULL;
}
else
{
Node* CurrTop = Stack->List;
while (CurrTop != NULL && CurrTop->Next != Stack->Top)
{
CurrTop = CurrTop->Next;
}
Stack->Top = CurrTop;
CurrTop->Next = NULL;
}
return TopNode;
}
|
Top 노드를 만들어 마지막 노드를 반환한다는 조건을 만족시킵니다.
마지막 노드의 주소를 저장할 포인터 변수를 만들어 놓고, 마지막 노드의 이전 노드를 찾습니다.
Top의 위치를 이전 Top의 위치로 변경해주고 현재 Top의 Next를 NULL로 만들어서 연결을 끊고, TopNode를 반환해서 Pop의 기능을 만족합니다.
7. 연결 리스트 스택 - 맨 위 노드 반환(Top)
연결 리스트 스택의 Top의 위치를 구하는 연산입니다.
|
1
2
3
4
5
|
// LLS 맨 위 노드 반환
Node* LLS_Top(LinkedListStack* Stack)
{
return Stack->Top;
}
|
8. 연결 리스트 스택 - 크기
연결 리스트 스택의 크기를 구하는 연산입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// LLS 크기 반환
int LLS_GetSize(LinkedListStack* Stack)
{
int Count = 0;
Node* Current = Stack->List;
while(Current != NULL)
{
Current = Current->Next;
Count++;
}
return Count;
}
|
9. 연결 리스트 스택 - 비여있는지 여부
연결 리스트 스택이 비여있는지 확인하는 연산입니다.
|
1
2
3
4
5
|
// LLS 비어있는지 여부
int LLS_IsEmpty(LinkedListStack* Stack)
{
return (Stack->List == NULL);
}
|
댓글