열혈 자료구조 - 6-3. 연결 리스트 기반의 스택 구현

구현 논리

- 연결 리스트에 데이터를 저장할 때 HEAD에 추가하는 방식

- 그러면 push 할 때 HEAD에 추가하고 pop할 때는 HEAD가 가르키는 노드를 삭제하면 됨(HEAD는 그 다음 노드를 가르키게 해야함)

 

연결 리스트 기반의 배열 구현

- 구조체 정의

    -> HEAD에 데이터를 추가하면서 연결되고 HEAD가 가르키는 노드의 데이터를 조회, 삭제하기 때문에 노드 포인터 변수 head만 있으면 됨

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

typedef struct _listStack
{
	Node * head;
} ListStack;

- 초기화

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

- 비어있는지 확인

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

- 데이터 추가

void SPush(Stack * pstack, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));

	newNode->data = data;
	newNode->next = pstack->head;		// 현재 헤드가 가르키는 노드를 가르킴

	pstack->head = newNode;				// 헤드가 새 노드를 가르킴
}

- 데이터 삭제를 동반한 조회

Data SPop(Stack * pstack)
{
	Data rdata;
	Node * rnode;

	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	rdata = pstack->head->data;
	rnode = pstack->head;

	pstack->head = pstack->head->next;		// 현재 헤드가 가르키고 있던 다음 노드를 헤드로 만듬
	free(rnode);

	return rdata;							// 이전 헤드가 가지고 있던 데이터 반환
}

- 데이터 조회(삭제 X)

Data SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->head->data;		// 단순하게 헤드의 데이터를 반환
}