[ C언어 ] 자료구조_스택(LinkedList)

[ C언어 ] 자료구조_스택(배열)

저번에는 스택 자료구조를 배열을 사용하여 구현해 보았습니다.

 

이번에는 스택을 연결 리스트(LinkedList) 를 사용하여 구현해 보겠습니다.

 

1. 구현방식

스택은 후입선출(LIFO) 구조이기 때문에 마지막 노드의 주소와 각 노드는 이전 노드의 주소만 알면 됩니다.

 

그럼 push를 통해 새로운 노드를 추가하려면 새로운 노드를 HEAD 노드로 변경하고 기존의 HEAD 노드의 주소를 가리키면 됩니다.

 

반대로 pop를 수행하려면 HEAD 노드가 가리키는 노드에게 HEAD를 넘겨주고 제거하면 됩니다.

 

2. 구현

Stack.h

typedef int element;

typedef struct Node {
	struct Node* link;
	element data;
}Node;

int push(Node* node, element data);
element pop(Node* node);

 

 

Stack.c

#include <stdlib.h>
#include "Stack.h"

int push(Node** head, element data)
{
	Node* newNpde = malloc(sizeof(Node));
	if (newNpde == NULL) return -1;

	newNpde->link = NULL;
	newNpde->data = data;

	if (*head == NULL) {
		*head = newNpde;
		return -1;
	}

	newNpde->link = *head;
	*head = newNpde;

	return 0;
}
element pop(Node** head)
{
	if (*head == NULL) {
		return -1;
	}

	element data = (*head)->data;
	Node* deleteNode = *head;
	*head = (*head)->link;
	free(deleteNode);

	return data;
}

 

 

main.c

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

int main() {
	Node* stack = NULL;

	push(&stack, 1);
	push(&stack, 5);
	push(&stack, 3);

	printf("%d ", pop(&stack));
	printf("%d ", pop(&stack));
	printf("%d ", pop(&stack));

	return 0;
}

 

실행결과

 

위 연결리스트 방식으로 구현하면 push와 pop 연산의 모든 경우의 시간복잡도가 O(1) 이 되므로 연산 속도 측면에서 배열의 인덱스를 통해 접근하는 것과 비슷한 성능을 낼 수 있습니다.

 

하지만 메모리적으로는 효율이 떨어지기 때문에 배열을 사용한 방법이 메모리적으로 더 유리합니다.

 

이상으로 스택을 연결 리스트를 사용하여 구현해 보았습니다.

저의 글을 봐주셔서 감사합니다.