자료구조 - 스택(연결 리스트 기반)

스택은 배열  또는  연결리스트로 구현할 수 있다.

 

연결리스트로 구현해보면 다음과 같은 헤더파일과 실행파일을 통해 스택을 구현할 수 있다.

헤더파일

실행 파일

 

코드 부분설명▼

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

스택 초기화 부분

(포인터 변수 head는 NULL 로 초기화한다.)

 

 

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

스택이 비어있는지 확인하는 함수

(head가 NULL 이면 True 반환 아니면 False 반환)

 

 

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

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

	pstack->head = newNode;
}

스택의 push 연산을 담당하는 함수

(새 노드에 메모리를 할당하여 data 를 삽입하고 새 노드가 최근에 추가된 노드를 가리킴)

 

 

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

스택의 pop 연산을 담당하는 함수

(head가 가리키는 노드를 소멸시키고 소멸된 노드의 데이터를 반환)

 

 

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

	return pstack->head->data;
}

스택의 peek 연산을 담당하는 함수

(스택이 비어있으면 종료, 아니면 head가 가리키는 노드에 저장된 데이터를 반환)

 

 

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

메인 문

(스택을 생성하고 초기화한 후 1 2 3 4 5 순으로 데이터를 삽입한 뒤 pop 연산을 통해 5 4 3 2 1 순으로 출력되도록 한다.)