[C언어] 스택 연결리스트 자료구조 구현하기

노드 구조체 구현

#define MaxStackSize 100

typedef struct node
{
	char data;
	struct node* next;
}nodeType;

nodeType* stack_top;

- 데이터와 링크(넥스트)를 묶어서 구조체를 선언한다.

- 노드를 가리키는 처음 stack_top 포인터 선언

 

 

스택 초기화 함수

void init() {
	stack_top = NULL;
}

 

 

 

스택 빈 여부 확인 함수

int isEmpty() {
	if (stack_top == NULL) {
		return 1;
	}
	else return 0;
}

- stack_top이 여전히 NULL이라면 옳기 때문에 1을 반환

- 그렇지 않다면 0 false를 반환

 

 

 

스택 사이즈 가져오기

int getSize() {
	nodeType* ptr;
	int count = 0;

	for (ptr = stack_top; ptr != NULL; ptr = ptr->next) {
		count++;

	} return count;

}

- 동적으로 움직일 수 있는 노드 ptr을 선언하고

- count 변수를 선언한다.

- 스택을 한 바퀴 돌아야 하므로, for문을 구현한다.

- 시작점인 stack_top에서 ptr이 NULL이지 않은 곳까지 링크를 타고 안으로 깊이 들어가도록 한다.

- 이때마다 count를 하나씩 늘려준다.

- 카운트를 리턴한다.

 

 

스택이 가득찼는지 확인 함수

int isFull() {

	if (getSize() == MaxStackSize) {
		return 1;
	}	else return 0;
		
}

 

 

스택 푸쉬push함수

void push(char item) {
	nodeType* ptr = (nodeType*)malloc(sizeof(nodeType));
	ptr->data = item;
	ptr->next = stack_top;
	
	stack_top = ptr;

}

- 데이터를 집어넣어야 하므로, 노드타입을 메모리 할당과 함께 선언하고,

- 파라미터 변수값을 ptr 노드에 삽입한다.

- ptr 노드의 링크가 stack_top이 가리키던 링크값과 같아져야 하므로, ptr->next에 stack_top노드를 지정한다.

- stack_top 노드에 ptr노드를 대입한다.

 

 

 

스택 pop 함수

char pop() {
	nodeType* ptr;

	if (stack_top == NULL) {
		printf("stack is empty");
	}

	ptr = stack_top;
	stack_top = stack_top->next;
	free(ptr);
	return (ptr->data);
}

 

스택 프린트 함수

void printStack() {
	nodeType* ptr;

	printf("스택의 크기는 %d\n", getSize());

	for (ptr = stack_top; ptr != NULL; ptr = ptr->next) {
		printf("%c\n", ptr->data);
	}
}

 

 

#include <stdio.h>
#include "stack_list.h"

void main() {

	init();

	push('A');
	push('B');
	push('C');
	push('D');
	
	pop();
	pop();

	push('O');
	push('P');

	pop();
	pop();
	pop();
	pop();
	
	pop();






}

D
C
P
O
B
A
stack is empty

 

 

스택 오버플로우란?

프로그램 호출 스택에서 이용 가능한 공간 이상을 사용하려고 시도할 때, 스택 오버플로우가 발생한다. 이 경우 일반적으로 프로그램 동작이 중단된다.