스택과 스택의 노드
링크드 리스트는 배열과 달리 인덱스로 노드에 접근할 수 없습니다.
리스트를 쓰면 배열과는 달리 용량에 제한을 두지 않아도 된다는 장점이 있습니다.
그러나 '인덱스'가 없기 때문에 자신의 위에 위치하는 노드를 가리키는 포인터가 필요합니다.
( 자신의 위에 위치한다: 스택 구조에서 자기 노드를 기준으로 최상위 노드 방향을 '위'라고 한 것입니다. )
typedef struct Node {
char* data;
struct Node* nextNode;
}Node;
스택의 구조체입니다.
배열과는 다르게 최대길이, 최상위 노드의 인덱스가 필요 없습니다.
그 대신 리스트의 헤드와 테일을 가리키는 포인터가 필요합니다.
스택의 구조체에서
헤드는 리스트의 '시작점'을 뜻하고, 테일은 '최상위 노드'를 가리킵니다.
typedef struct LLStack {
Node* list;
Node* top;
}LLStack;
스택생성
먼저, 스택을 자유저장소(==스택메모리)에 생성하는 CreateStack() 함수를 만듭니다.
void CreateStack(LLStack** stack) {
(*stack) = (LLStack*)malloc(sizeof(LLStack));
(*stack)->list = NULL;
(*stack)->top = NULL;
}
노드 생성
노드 만큼의 메모리를 할당 합니다.
문자열의 길이와 NULL문자에 필요한 1을 포함한 길이의 메모리를 할당받습니다.
그곳을 newNode의 data가 가리키도록 합니다.
자유저장소에 문자열을 저장해야 하므로, strcpy()를 이용하여 저장합니다.
strcpy() 와 strlen() 함수를 쓰려면 #include <string.h> 선언이 필요합니다.
Node* CreateNode(char* data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = (char*)malloc(strlen(data) + 1);
strcpy(newNode->data, data);
newNode->nextNode = NULL;
return newNode;
}
노드를 메모리에서 해제
문자열을 가리키는 포인터를 메모리에서 해제 후, 노드를 메모리에서 해제합니다.
void FreeNode(Node* targetNode) {
free(targetNode->data);
free(targetNode);
}
스택을 메모리에서 해제
스택 제거에 앞서 노드들을 메모리에서 전부 해제합니다.
마지막으로 스택을 메모리 해제 합니다.
// 스택의 메모리해제
void FreeStack(LLStack* targetStack) {
while (!IsEmpty(targetStack)) {
Node* popped = Pop(targetStack);
FreeNode(popped);
}
free(targetStack);
}
Push 연산
스택이 비었다면 새 노드가 헤드노드가 됩니다.
그렇지 않다면, 테일 노드를 찾아서 그 뒤에 새 노드를 붙입니다.
/* Push */
void Push(LLStack* stack, Node* newNode) {
printf("[ Push ] %s 삽입 \n", newNode->data);
if (NULL == stack->list) { // 스택이 비었다면, 뉴노드가 헤드.
stack->list = newNode;
}
else {
// 테일 노드를 찾아서, 그 뒤에 뉴 노드를 붙인다.
Node* tempNode = stack->list;
while (NULL != tempNode->nextNode) {
tempNode = tempNode->nextNode;
}
tempNode->nextNode = newNode;
}
stack->top = newNode;
}
다음과 같이 'top' 뒤에 새노르를 추가해도 됩니다.
void Push(LLStack* stack, Node* newNode) {
if (stack->top == NULL) {
stack->list = newNode;
}
else { // 테일 뒤에 붙인다
stack->top->nextNode = newNode;
}
stack->top = newNode;
}
Pop 연산
Pop 연산은 두 가지 경우를 처리합니다.
헤드가 탑인 경우 (스택에 노드가 하나 밖에 없다)
탑 직전 노드를 찾아야 하는 경우 (탑 직전 노드를 탑 노드로 갱신해준다)
Node* Pop(LLStack* stack) {
Node* topNode = stack->top;
Node* current = stack->list;
if (current == topNode) { // 헤드가 탑이라면, 1개 남은 노드를 제거하는 상황.
stack->top = NULL;
stack->list = NULL;
}
else { // top의 직전 노드를 찾는다
while (current->nextNode != stack->top) {
current = current->nextNode;
}
current->nextNode = NULL;
stack->top = current; //top 갱신
}
return topNode;
}
스택이 비어있는지 확인
int IsEmpty(LLStack* stack) {
return (NULL == stack->list);
}
스택에 노드가 몇개 있는지 확인
int GetSize(LLStack* stack) {
Node* temp = stack->list;
int count = 0;
while (temp != NULL) {
temp = temp->nextNode;
count++;
}
return count;
}
'알고리즘 > 알고리즘 C' 카테고리의 다른 글
| 링크드 큐 (0) | 2020.03.10 |
|---|---|
| 순환 큐 (0) | 2020.03.09 |
| 배열로 구현하는 스택 (0) | 2020.02.18 |
| 환형 링크드 리스트 (0) | 2020.02.17 |
| 더블 링크드 리스트 (0) | 2020.02.14 |
