Chapter 06. 스택의 연결 리스트 기반 구현

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

이번 시간에는 연결 리스트를 기반으로 스택을 구현합니다. 그런데 이에 앞서 연결 리스트로 까다로운데 이걸로 스택을 구현하겠다니 걱정할 수도 있겠습니다. 하지만 전혀 그런 걱정할 필요가 없습니다. 스택의 구조는 매우 단순합니다. 예를 들어 연결 리스트에서 머리에 데이터를 추가하고 머리부터 데이터 조회를 한다면 그것이 바로 스택의 구조가 됨을 눈치챌 수 있습니다.

---

연결 리스트 기반 스택을 구현하기 위해서는 head 포인터가 필요합니다. 다음은 연결 리스트 기반 스택의 헤더 파일을 정의한 것입니다.

//LBStack.h 헤더 파일로 저장
#ifndef LB_STACK_H
#define LB_STACK_H

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct Node
{
	Data data;
	struct Node* next;
} Node;

typedef struct ListStack
{
	Node* head;
}ListStack;

typedef ListStack Stack;

void StackInit(Stack* pstack);
int SIsEmpty(Stack* pstack);
void SPush(Stack* pstack, Data data);
Data SPop(Stack* pstack);
Data SPeek(Stack* pstack);

#endif 

---

이제 위의 헤더 파일을 바탕으로 각각의 함수들을 구현해 봅니다.

먼저 스택을 초기화하는 StackInit 함수의 구현입니다.

void StackInit(Stack* pstack)
{
	pstack->head = NULL;
}

 

다음은 스택이 비어 있는지 확인하는 SIsEmpty 함수의 구현입니다.

int SIsEmpty(Stack* pstack)
{
	if (pstack->head == NULL) return TRUE;
	return FALSE;
}

 

다음은 스택에 데이터를 저장하는 SPush 함수의 구현입니다.

void SPush(Stack* pstack, Data data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL)
	{
		printf("메모리 공간이 부족합니다.\n");
		exit(1);
	}

	newNode->data = data;
	newNode->next = pstack->head;
	pstack->head = newNode;
}

데이터를 추가하면 newNode를 생성합니다. 그리고 newNode에 데이터를 저장하고 newNode->next와 스택의 머리를 연결합니다. 이후 스택의 머리를 newNode로 바꿉니다.

 

다음은 SPop 함수의 구현입니다.

Data SPop(Stack* pstack)
{
	if (pstack->head == NULL)
	{
		printf("스택의 참조 범위를 벗어난 접근입니다.\n");
		exit(1);
	}

	Node* delNode = pstack->head;
	Data delData = delNode->data;

	pstack->head = pstack->head->next;

	free(delNode);
	return delData;
}

반환할 데이터가 남아 있는지 먼저 확인합니다. 이후 임시 노드와 임시 데이터를 생성하고, 스택의 머리 위치를 다음 노드로 옮긴 후 삭제 과정이 이루어집니다. 그리고 임시 데이터를 반환합니다.

 

다음은 SPeek 함수의 구현입니다.

Data SPeek(Stack* pstack)
{
	if (pstack->head == NULL)
	{
		printf("스택의 참조 범위를 벗어난 접근입니다.\n");
		exit(1);
	}

	return pstack->head->data;
}

해당 함수에서는 노드의 삭제가 이뤄지지 않습니다. 스택에 남아 있는 데이터가 있는지 확인하고, 스택 머리의 데이터를 반환합니다.

 

헤더 파일을 정의하고 함수들을 구현했으므로 이를 확인하기 위한 main 함수를 작성하여 그 실행결과를 보겠습니다.

//LBStack.h 헤더 파일로 저장
#ifndef LB_STACK_H
#define LB_STACK_H

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct Node
{
	Data data;
	struct Node* next;
} Node;

typedef struct ListStack
{
	Node* head;
}ListStack;

typedef ListStack Stack;

void StackInit(Stack* pstack);
int SIsEmpty(Stack* pstack);
void SPush(Stack* pstack, Data data);
Data SPop(Stack* pstack);
Data SPeek(Stack* pstack);

#endif 

//LBStack.c 소스 파일로 저장
#include "LBStack.h"
#include <stdio.h>
#include <stdlib.h>

void StackInit(Stack* pstack)
{
	pstack->head = NULL;
}

int SIsEmpty(Stack* pstack)
{
	if (pstack->head == NULL) return TRUE;
	return FALSE;
}

void SPush(Stack* pstack, Data data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL)
	{
		printf("메모리 공간이 부족합니다.\n");
		exit(1);
	}

	newNode->data = data;
	newNode->next = pstack->head;
	pstack->head = newNode;
}

Data SPop(Stack* pstack)
{
	if (pstack->head == NULL)
	{
		printf("스택의 참조 범위를 벗어난 접근입니다.\n");
		exit(1);
	}

	Node* delNode = pstack->head;
	Data delData = delNode->data;

	pstack->head = pstack->head->next;

	free(delNode);
	return delData;
}

Data SPeek(Stack* pstack)
{
	if (pstack->head == NULL)
	{
		printf("스택의 참조 범위를 벗어난 접근입니다.\n");
		exit(1);
	}

	return pstack->head->data;
}

//main.c 소스 파일로 저장
#include "LBStack.h"
#include <stdio.h>

int main(void)
{
	//Stack의 성생 및 초기화
	Stack stack;
	StackInit(&stack);

	//데이터 넣기
	SPush(&stack, 1);
	SPush(&stack, 2);
	SPush(&stack, 3);
	SPush(&stack, 4);
	SPush(&stack, 5);

	//데이터 꺼내기
	while (!SIsEmpty(&stack))
	{
		printf("%d ", SPop(&stack));
	}

	return 0;
}

/*
실행결과

5 4 3 2 1

*/