9. 스택

링크드 리스트를 활용하여 스택 구현하기 : 

링크드 리스트를 이용하면 배열로 구현할 때 보다 메모리 제약에서 자유로움.

typedef struct _node {
	int data;
	struct _node* prev;
}Node;

우선 데이터와 이전 노드를 가리킬 포인터를 구조체 변수로 갖는 Node 변수를 만든다.

typedef struct _stack {
	Node* top;
	int size = 0;
}Stack;

Stack 구조체는 pop()과 push()가 실행될 때 사용할 top 포인터와 스택의 길이를 나타내는 사이즈 변수를 갖는다.

 

메인에서 스택을 선언한다.

int main() {
	Stack st;   //스택 생성
    push(&st, 1)
    push(&st, 2)
    push(&st, 3)

    pop(&st);
    
    return 0;
}

push 작업은

1) 새로 입력되는 노드의 prev 포인터가 top 포인터가 가리키던 노드를 가리키고

2) top 포인터는 새로 입력되는 노드를 가리킨다.

3) 노드의 사이즈 +1

int push(Stack* st, int data) {
	//size == 0 이면 head == NULL, top == NULL;
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	//stack의 크기가 0이면 이전 노드가 없음 NULL
	if (st->size == 0) {
		newNode->prev = NULL;
	}
	else {
		newNode->prev = st->top;
	}
	st->top = newNode;
	st->size++;

	return 0;
}

pop 작업은

1)top노드가 현재 가리키는 노드는 곧 pop되어 사라질 노드

2)top노드의 주소값을 담을 노드 생성

3)top노드가 top노드 이전 노드를 가리키고

4)이전 노드는 메모리 해제

3)사이즈 -1

int pop(Stack* st) {
	if (st->size == 0) {
		//Empty조건
		printf("E\n");
		return 0;
	}
	else {
		printf("%d\n", st->top->data);
	}
	Node* freeNode; //pop할 Node의 주소를 기억한 뒤 free 할 것이다.
	freeNode = st->top;
	st->top = st->top->prev;
	st->size--;
	free(freeNode);
	return 0;
}