JArchive 프로그래밍 일기

스택과 스택의 노드 

링크드 리스트는 배열과 달리 인덱스로 노드에 접근할 수 없습니다. 

리스트를 쓰면 배열과는 달리 용량에 제한을 두지 않아도 된다는 장점이 있습니다. 

그러나 '인덱스'가 없기 때문에 자신의 위에 위치하는 노드를 가리키는 포인터가 필요합니다. 

( 자신의 위에 위치한다: 스택 구조에서 자기 노드를 기준으로 최상위 노드 방향을 '위'라고 한 것입니다. )

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;
}