자료 구조 - 스택(Stack)

스택은 앞선 링크드 리스트와 반대로 가장 먼저 들어간 노드가 가장 마지막에 나오는 선입 후출(First In, Last Out) 구조로 되어 있습니다. 스택은 소프트웨어에서 널리 쓰이는 자료 구조입니다. C에서 사용하는 자동 메모리, 대부분의 네트워크 프로토콜들이 스택으로 이루어져 있습니다.

 

스택은 배열과 링크드 리스트로 구현할 수 있습니다. 이번 포스팅에서는 링크드 리스트로 구현한 스택을 알아보겠습니다. 링크드 리스트로 구현하면 스택의 용량에 제한을 두지 않아도 된다는 장점이 있습니다.

typedef struct tagNode
{
	char* Data; //데이터
	struct Node* NextNode; //자기 위에 쌓여있는 노드를 가르킨다.
} Node;

링크드 리스트로 구현된 스택은 두가지 포인터를 가지고 있습니다.

첫 번째로는 스택 최상위 노드인 Top포인터와 스택의 최하위 노드(테일) 노드인 List포인터입니다.

물론 스택의 특징인 선입 후출에 의하면 테일 노드에 접근하기 위해선 Top포인터에서 출발하여 순차 탐색으로 접근해야 하지만 List 포인터를 사용함으로써 빠르게 접근할 수 있습니다.

typedef struct tagLinkedListStack
{
	Node* Top; // 최상위 노드 포인터
	Node* List; // 최하위 노드 포인터(테일)
} LinkedListStack;

 

스택 노드의 삽입

---

스택의 노드 삽입은 링크드 리스트에서 노드 추가와 동일합니다.

먼저 생성한 스택의 최상위 노드에 노드를 연결한 후 Top포인터에 새로 연결한 노드를 등록해주기만 하면 완료됩니다.

void LLS_Push(LinkedListStack* Stack, Node* NewNode) {
	if (Stack->List == NULL) {
		Stack->List = NewNode; //스택에 들어있는 노드가 없을 때 새로운 노드를 List에 등록
	}
	else {
		Node* OldTop = Stack->List; // 노드 시작점
		while (OldTop->NextNode != NULL) // 반복문을 통해 마지막 노드로 접근
		{
			OldTop = OldTop->NextNode;
		}
		OldTop->NextNode = NewNode; // 노드 연결
	}

	Stack->Top = NewNode; // 최상위 노드로 등록
}

머릿속에 그려지는 그림은 단순히 링크드 리스트이지만, Top노드에 최상위 노드를 등록하고 삭제 시 Top노드부터 삭제하는 것으로 스택의 선입 후출이 완성되는 듯합니다.

 

스택 노드의 제거

---

스택 노드의 제거는 아래의 단계로 수행됩니다.

1. 현재 최상위 노드(Top)의 주소를 다른 포인터에 복사해 둔다.
2. 새로운 최상위 노드, 즉 현재 최상위 노드의 이전 노드를 찾는다.
3. 스택의 구조체의 Top노드에 새로운 최상위 노드의 주소를 등록한다.
4. 1번에 저장해둔 옛날의 최상위 노드의 주소를 반환한다.

Node* LLS_Pop(LinkedListStack* Stack) {
	Node* TopNode = Stack->Top; // 현재 최상위 노드를 저정해준다.

	if (Stack->List == Stack->Top) { // 만약 테일 노드가 최상위 노드일 때
		Stack->List = NULL; // 널 초기화
		Stack->Top = NULL; // 널 초기화
	}
	else { 
		Node* NewTopNode = Stack->List; // 새로운 최상위 노드에 접근하기 위해 변수 할당

		while (NewTopNode != NULL && NewTopNode->NextNode != Stack->Top) {
			NewTopNode = NewTopNode->NextNode; // 다음 노드가 Top노드일때까지 이동
		}

		Stack->Top = NewTopNode; // 새로운 최상위 노드 등록
		NewTopNode->NextNode = NULL; // 널 초기화
	}
	return TopNode; // 옛날 최상위 노드 반환
}