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

오늘 한 일 

환형 링크드 리스트를 다시 보고, 스택을 배열로 짜봤다. 

공부한 내용과 코드를 포스팅으로 정리했다. 

생각거리 

나름 깔끔한 포스팅을 위해 카카오 오븐을 이용해 그림을 그렸는데. 귀찮으면서도 재미있었다.

포스팅을 정성껏 해주는 사람들의 정성을 절감했다. 

내일은 SQLD에 더 시간을 들여야지. 

스택이란?

스택에 10, 20, 30 순서로 숫자를 3개 넣어봅니다. (push 연산)

가장 먼저 들어간 10이 맨 아래에 있게 됩니다. 

10을 즉시 꺼낼 수 없고, 30 부터 꺼내야 마지막으로 10을 얻을 수 있습니다. (pop 연산)

이처럼 '가장 먼저 들어간 요소가 가장 마지막에 나오는 구조 입니다. 

그래서 FILO (First In Last Out) 라고 부릅니다. 

자동메모리가 스택을 기반으로 동작하고, 대부분의 네트워크 프로토콜도 스택을 기반으로 구성되어 있습니다. 

배열로 구현하는 스택 

배열을 이용하면, 동적으로 스택의 길이를 조절할 수 없지만, 구현이 간단합니다. 

사용자가 정한 숫자만큼의 길이를 가진 배열을 만듭니다. 

그리고 최상위 노드의 위치를 알고있는 변수로 삽입과 제거 연산을 합니다. 

스택의 노드 

스택에 들어갈 노드입니다. 

데이터 하나를 담는 노드를 구조체로 표현합니다. 

노드의 위치는 배열의 인덱스로 알 수 있습니다. 

typedef struct Node {
	int data;
}Node;

다음은 스택 구조체입니다. 

구조체 ArrayStack에 필요한 필드는 세 가지 입니다. 

배열의 길이
배열
최상위 노드의 위치 

노드가 최대 몇 개 들어갈 수 있는지 배열의 길이를 알아야 합니다. 

그리고 노드를 저장할 '배열'이 필요하고, 최상위 노드의 위치로 삽입/제거 합니다. 

typedef struct ArrayStack {
	int capacity;		/* 배열 용량 */
	int top;	/* 최상위 노드 위치 */
	Node* arrayNodes;	/* 노드들을 보관하는 스택배열 */
}ArrayStack;

노드 배열은 포인터로 선언되어 있습니다. (포인터는 배열로 사용할 수 있습니다)

스택의 생성과 메모리해제 

CreateArrayStack() 함수는 배열의 최대길이를 이용하여 스택을 생성합니다.  

/* 스택 생성.  메모리 할당 */
void CreateArrayStack(ArrayStack** stack, int capacity) {
	printf("[ 스택 생성 CreateArrayStack ]\n");

	/* 스택을 자유 저장소에 생성 */
	(*stack) = (ArrayStack*)malloc(sizeof(ArrayStack));

	/* 용량 만큼의 노드들을 자유 저장소에 생성 */
	(*stack)->arrayNodes = (Node*)malloc(sizeof(Node) * capacity);

	// 필드 초기화 
	(*stack)->capacity = capacity;
	(*stack)->top = 0;
}

FreeArrayStack() 함수는 노드와 스택을 자유 저장소에서 해제합니다.

void FreeArrayStack(ArrayStack** stack) {
	printf("[ 메모리 해제 FreeArrayStack ]\n");

	free((*stack)->arrayNodes);
	free((*stack));
}

삽입 연산 (PUSH)

스택 구조체가 알고있는 top 위치의 노드에 데이터를 넣습니다.

배열 인덱스가 top이 됩니다. 

데이터를 넣고, top위치를 갱신해줍니다. 

void Push(ArrayStack* stack, int inputData) {
	printf("[ 삽입연산 Push ] %d를 Push \n", inputData);

	int location = stack->top;

	stack->arrayNodes[location].data = inputData;
	stack->top = location + 1;
}

스택이 꽉 찼을 때를 확인하는 Push 함수 

스택이 꽉 찼을 때 push를 안하고 종료하는 코드를 추가해봤습니다. 

capacity와 top이 같은지 확인합니다. 

Push의 리턴을 bool로 바꾸고, 삽입이 불가하면 false를 리턴하도록 했습니다. 

bool Push(ArrayStack* stack, int inputData) {
	printf("[ 삽입연산 Push ] %d를 Push \n", inputData);

	if (stack->capacity == stack->top) {
		printf("[ 용량초과! ] 삽입이 불가합니다. \n");
		return false;
	}

	int location = stack->top;

	stack->arrayNodes[location].data = inputData;
	stack->top = location + 1;

	return true;
}

삽입/제거 연산을 확인해본 main 함수 코드입니다.

int main() {

	ArrayStack* stack = NULL;

	CreateArrayStack(&stack, 10);

	// 12번 Push
	for (int i = 10; i <= 120; i+=10) {
		if (!Push(stack, i)) {
			break;
		}
	}

	// 5번 Pop
	for (int i = 0; i < 5; i++) {
		printf("%3d를 제거합니다.\n", Pop(stack));
	}
	
	return 0;
}

배열 최대 길이가 10인데, Push 연산을 12번 했을 경우 콘솔 화면 입니다. 

10번 넣고, 11번 넣으려고 할때 용량이 초과되서 for 문을 break 합니다.

이어서 제거 연산을 5번 수행합니다. 

스택용량이 Full 인지 확인하는 함수로 분리하면 더 좋을 것 같습니다. 

제거 연산 (POP)

삽입과는 달리, top 값을 1 감소하면 됩니다. 

그리고 top 위치에 있던 data를 호출자에게 반환합니다. 

int Pop(ArrayStack* stack) {
	printf("[ 제거연산 Pop ]\n");

	int location = --(stack->top);

	return stack->arrayNodes[location].data;
}

POP 연산 시, 배열의 인덱스를 주의해야 합니다. 

왜냐하면 top이 1이라면, 노드가 위치하는 실제 인덱스는 0이기 때문입니다. 

스택이 비었는지 확인  : Pop 전에 확인 

/* 스택이 비었는지 확인 : 제거 전에 확인  */
int isEmpty(ArrayStack* stack) {
	// true 1 반환. false 0 반환 
	return (0 == stack->top);
}

전체 코드 

배열길이는 10을 주고 10부터 100까지 10개의 숫자를 PUSH 합니다. 

12번의 POP을 시도하지만 10번까지만 하고 종료되는 코드입니다. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct Node {
	int data;
}Node;

typedef struct ArrayStack {
	int capacity;		/* 배열 용량 */
	int top;	/* 최상위 노드 위치 */
	Node* arrayNodes;	/* 노드들을 보관하는 스택배열 */
}ArrayStack;


/* 스택 생성.  메모리 할당 */
void CreateArrayStack(ArrayStack** stack, int capacity) {
	printf("[ 스택 생성 CreateArrayStack ]\n");

	/* 스택을 자유 저장소에 생성 */
	(*stack) = (ArrayStack*)malloc(sizeof(ArrayStack));

	/* 용량 만큼의 노드들을 자유 저장소에 생성 */
	(*stack)->arrayNodes = (Node*)malloc(sizeof(Node) * capacity);

	// 필드 초기화 
	(*stack)->capacity = capacity;
	(*stack)->top = 0;
}

/* 메모리 해제 */
void FreeArrayStack(ArrayStack** stack) {
	printf("[ 메모리 해제 FreeArrayStack ]\n");

	free((*stack)->arrayNodes);
	free((*stack));
}

/* 삽입 Push 연산 */
void Push(ArrayStack* stack, int inputData) {
	printf("[ 삽입연산 Push ] %d를 Push \n", inputData);

	int location = stack->top;

	stack->arrayNodes[location].data = inputData;
	stack->top = location + 1;
}

/* 스택이 비었는지 확인 : 제거 전에 확인  */
int isEmpty(ArrayStack* stack) {
	// true 1 반환. false 0 반환 
	return (0 == stack->top);
}

/* 제거 Pop 연산 */
int Pop(ArrayStack* stack) {
	printf("[ 제거연산 Pop ]\n");

	int location = --(stack->top);

	return stack->arrayNodes[location].data;
}



int main() {

	ArrayStack* stack = NULL;

	CreateArrayStack(&stack, 10);

	// 10개 Push
	for (int i = 10; i <= 100; i+=10) {
		Push(stack, i);

	}

	// 12번을 pop 해본다 
	for (int i = 0; i < 12; i++) {

		if (isEmpty(stack)) {
			printf("스택이 비었습니다. \n");
			break;
		}
		else {
			printf("%3d를 제거합니다.\n", Pop(stack));
		}
	}
	
	return 0;
}

콘솔 결과 입니다. 

다음 포스팅에서는 링크드 리스트로 구현하는 스택을 다루겠습니다.

오늘 한 일 

환형 더블 링크드 리스트를 공부하고 코딩했다. 

최호성님의 C언어 강의에서 '스택메모리'를 공부하는 '함수응용' 강의를 들었다. 

생각거리 

환형 더블 링크드 리스트. 이름 참 길다.

노드 추가, 삭제만 했는데, 더블 링크드를 두번 짜봐서 그런지 크게 힘들지는 않았다. 

다행이다.

내일도 화이팅!! 

환형 링크드 리스트 

환형 링크드 리스트도 더블 링크드 리스트와 비슷합니다. 

유의할 점은 테일의 다음 노드 포인터가 헤드를 가리키게 하면 됩니다. 

이것 빼고는 더블 링크드 리스트와 똑같습니다. 그래서 노드 추가, 삭제만 살펴볼 것입니다. 

테일의 다음이 헤드이고, 헤드의 앞이 테일이기 때문에 "뒤"부터 검색할 수도 있습니다!

그래서 탐색과 추가 기능의 성능을 개선할 수 있습니다. 

환형 더블 링크드 리스트의 주요 연산 

유의할 점은 다음 두 가지 입니다. 

첫 번째, 테일은 헤드의 '앞 노드'이다. 
두 번째, 헤드는 테일의 '뒷 노드'이다. 

노드 추가 

void AppendNode(Node** head, Node* newNode) {
	printf("[AppendNode] %d를 추가합니다. \n", newNode->data);

	if (NULL == (*head)) { // 헤드가 비었다면 뉴 노드가 헤드
		
		(*head) = newNode;
		(*head)->nextNode = (*head);
		(*head)->prevNode = (*head);

	}
	else { // 테일과 헤드 사이에 뉴노드 삽입 

		// 뉴노드의 다음은 헤드, 뉴노드 이전은 테일 
		newNode->nextNode = (*head);
		newNode->prevNode = (*head)->prevNode;

		// 기존테일의 다음노드가 뉴노드.
		(*head)->prevNode->nextNode = newNode;
		// 뉴노드가 새로운 테일이 된다.
		(*head)->prevNode = newNode;

	}
}

리스트 출력 (do-while 이용)

환형 리스트 이므로, while 조건문에 유의하여 리스트를 출력했습니다. 

void PrintList(Node* list) {
	printf("[PrintList] 리스트 전체를 출력합니다. \n");

	Node* current = list;

	do {
		printf("%3d", current->data);
		current = current->nextNode;
	} while (current->nextNode != list->nextNode);

	printf("\n");
}

노드 탐색 

인덱스를 입력하여 노드의 주소를 리턴합니다. 

Node* GetLocation(Node* head, int location) {
	printf("[GetLocation] %d번째 노드를 찾아보자. \n", location);

	Node* current = head;

	while ((--location) >= 0) {
		//printf("location : %d 번째 탐색 \n", location);
		current = current->nextNode;
	}

	return current;
}

노드 삭제 

RemoveNode() 함수는 특정 주소에 있는 노드를 삭제합니다. 

void RemoveNode(Node** head, Node* target) {
	printf("[RemoveNode] %d를 삭제합니다. \n", target->data);

	if ((*head) == target) {
    	// 헤드의 앞뒤 노드의 포인터를 갱신  
		(*head)->prevNode->nextNode = (*head)->nextNode;
		(*head)->nextNode->prevNode = (*head)->prevNode;

		// 헤드를 갱신 
		(*head) = (*head)->nextNode;
	}
	else {
    	// 타겟의 앞뒤 노드의 포인터를 갱신 
		target->prevNode->nextNode = target->nextNode;
		target->nextNode->prevNode = target->prevNode;
	}

	// 타겟 메모리해제 
	target->nextNode = NULL;
	target->prevNode = NULL;
	free(target);
}

전체 코드 입니다. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>	

// 환형 링크드 리스트  

/* 노드 정의 */
typedef struct Node {
	int data;
	struct Node* prevNode;
	struct Node* nextNode;
}Node;

/* 노드 생성*/
Node* CreateNode(int data) {

	Node* newNode = (Node*)malloc(sizeof(Node));

	newNode->data = data;
	newNode->prevNode = NULL;
	newNode->nextNode = NULL;

	return newNode;
}



/* 리스트 출력 */
void PrintList(Node* list) {
	printf("[PrintList] 리스트 전체를 출력합니다. \n");

	Node* current = list;

	do {
		printf("%3d", current->data);
		current = current->nextNode;
	} while (current->nextNode != list->nextNode);

	printf("\n");
}

/* 노드 탐색 */
Node* GetLocation(Node* head, int location) {
	printf("[GetLocation] %d번째 노드를 찾아보자. \n", location);

	Node* current = head;

	while ((--location) >= 0) {
		//printf("location : %d 번째 탐색 \n", location);
		current = current->nextNode;
	}

	return current;
}


/* 노드 추가 */
void AppendNode(Node** head, Node* newNode) {
	printf("[AppendNode] %d를 추가합니다. \n", newNode->data);

	if (NULL == (*head)) { // 헤드가 비었다면 뉴 노드가 헤드
		
		(*head) = newNode;
		(*head)->nextNode = (*head);
		(*head)->prevNode = (*head);

	}
	else { // 테일과 헤드 사이에 뉴노드 삽입 

		//Node* tail = (*head)->prevNode;

		// 뉴 노드의 다음은 헤드, 뉴 노드 이전은 테일 
		newNode->nextNode = (*head);
		newNode->prevNode = (*head)->prevNode;

		// 기존테일의 다음노드가 뉴노드.
		(*head)->prevNode->nextNode = newNode;
		// 뉴노드가 새로운 테일이 된다.
		(*head)->prevNode = newNode;
	}
}


/* 노드 삭제 */
void RemoveNode(Node** head, Node* target) {
	printf("[RemoveNode] %d를 삭제합니다. \n", target->data);

	if ((*head) == target) {
		(*head)->prevNode->nextNode = (*head)->nextNode;
		(*head)->nextNode->prevNode = (*head)->prevNode;

		(*head) = (*head)->nextNode;
	}
	else {
		target->prevNode->nextNode = target->nextNode;
		target->nextNode->prevNode = target->prevNode;
	}

	// 타겟 메모리해제 
	target->nextNode = NULL;
	target->prevNode = NULL;
	free(target);
}

int main() {
	Node* list = NULL;

	AppendNode(&list, CreateNode(10));
	AppendNode(&list, CreateNode(20));
	AppendNode(&list, CreateNode(30));

	PrintList(list);
	
	// 3번째 노드 삭제(인덱스2)
	RemoveNode(&list, GetLocation(list, 2));
	PrintList(list);

	AppendNode(&list, CreateNode(40));
	PrintList(list);

	// 1번째 노드 삭제(인덱스0)
	RemoveNode(&list, GetLocation(list, 0));
	PrintList(list);

	// 2번째 노드 삭제(인덱스1)
	RemoveNode(&list, GetLocation(list, 1));
	PrintList(list);

	return 0;
}

콘솔 결과 입니다. 

오늘 한 일 

뇌를 자극하는 알고리즘 도서를 보고  '더블 링크드 리스트' 를 공부했다. 

생각거리

공부한 내용을 정리한 포스팅을 전체공개 하기에는, 저작권 법을 위반하게 되니까. 

배운 내용 중에서 가장 중요한 내용만 나만의 코드로 변형해서 정리해야겠다. 

주의해야지 :)