(C언어) 연결 리스트로 스택 구현해 보기[자료구조]

(C언어) 연결 리스트(1) [자료구조]

(C언어) 연결 리스트(1) [자료구조]

연결 리스트로 이전에 배운 스택을 구현해 보자.

배열로 구현한 스택

스택을 배열로 구현했을 때의 모습이다. 배열로 구현했기 때문에 구현은 간단했지만 크기가 제한됐었다. 우리가 배운 스택을 어떻게 연결 리스트로 구현할 수 있을까??

리스트로 구현한 스택

위 그림처럼 연결 리스트로 구현한다면 외부적으로 스택과 완전히 일치한다. 연결 리스트의 장점인 동적으로 구현할 수 있다는 점을 이용해 크기에 제한받지 않고 스택을 구현할 수 있다. 하지만 동적 메모리 할당과 해제 부분에서 삽입이나 삭제 시간은 배열로 구현한 스택보다 느릴 수 있다.

 

C언어로 직접 구현해 보자.

---

##함수

1. 리스트의 구조체 선언

-> 스택에 특성에 맞게 top 포인터를 추가하여 노드를 선언

2. init

-> 스택의 초기화 함수

3. is_empty

-> 스택이 비어있는지 검사하는 함수

4. push

-> 스택에 삽입하는 함수

5. pop

-> 스택에서 삭제하는 함수

6. print_stack

-> 스택을 출력하는 함수

---

1) 리스트의 구조체 선언

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

typedef struct{
	Node *top; // 스택의 top을 나타내는 포인터
}Stack;

연결 리스트의 기본적인 노드 정의 방식이다. 추가로 스택에서 가장 최근에 입력된 데이터를 나타내는 top을 노드를 가리키는 포인터로 선언한다. (헤드 포인터 느낌으로 사용했다고 해도 무관하다.) 구현에 필요한 모든 함수들은 Stack 구조체의 포인터를 매개변수로 사용한다.

2) init

void init(Stack *s)
{
	s->top = NULL;
}

스택이 비어있다면 top 포인터가 NULL 값인지에 대한 참 거짓을 반환하게 한다. 그 이유는 pop 함수에서 찾아볼 수 있다.

3) is_empty

int is_empty(Stack *s)
{
	return (s->top == NULL);
}

스택이 비어있다면 top 포인터가 NULL 값인지에 대한 참 거짓을 반환하게 한다. 그 이유는 pop 함수에서 찾아볼 수 있다.

4) push

삽입 연산

단순 연결 리스트에서 맨 앞에 삽입하는 과정과 동일하다. 동적 메모리 할당으로 노드를 만들고 이를 첫 번째 노드로 삽입한다.

void push(Stack *s,int item)
{
	Node *temp = (Node *)malloc(sizeof(Node)); // 동적노드 생성
	temp->data = item; // 새로운 노드에 입력할 값 복사
	temp->link = s->top; // 새로운 노드가 기존의 top 노드를 가르키도록 함
	s->top = temp; // temp 노드가 top 노드로 선언
}

5) pop

삭제 연산

삭제 연산은 temp 포인터를 선언하여 top 노드를 가리키도록 한 후 top의 값을 top->link로 바꿔준다. 그리고 temp 값을 메모리 해제시켜 준다.

int pop(Stack *s)
{
	if(is_empty(s)){ // 스택이 비어 있는지 확인
		printf("stack empty\n");
	}
	else{
		Node *temp = s->top; // temp포인터를 top노드를 가르키도록 함
		int data= temp->data; // 삭제한 값 반환하기 위해서 기존의 데이터를 temp노드에 삽입
		s->top = s->top->link; // top 노드는 기존의 top노드가 가르키는 노드가 됨
		free(temp); // 동적 메모리 해제
		return data; // 삭제할 값 반환
	}
}

is_empty 함수에서 top 포인터가 NULL인 경우로 설정해놓은 이유를 알 수 있다. pop 함수에서 top 노드가 기존의 top 노드가 가리키는 노드가 된다. 스택의 마지막 노드의 링크 값은 NULL이므로 결국 노드가 하나 남은 상태에서 pop 함수를 실행했다면 s->top == NULL 이 됨을 알 수 있다. is_empty 함수에서 공백 상태 조건이 이해가 갈 것이다.

6) print_list

void print_stack(Stack *s)
{
	for(Node *p = s->top; p!=NULL;p = p->link)
		printf("%d-> ",p->data);
	printf("NULL \n");
}

---

int main()
{
	Stack s;
	init(&s);
	push(&s,11); print_stack(&s);
	push(&s,22); print_stack(&s);
	push(&s,33); print_stack(&s);
	push(&s,44); print_stack(&s);
	
	pop(&s); print_stack(&s);
	pop(&s); print_stack(&s);
	pop(&s); print_stack(&s);
	pop(&s); print_stack(&s);
	return 0;
}

다음과 같이 메인 함수를 실행해 보자.

결괏값

스택의 모습으로 잘 구현된 것을 볼 수 있다. 연결 리스트로 스택을 구현해 보았는데 이전에 배열로 구현했던 방식과 차이점을 느끼면서 공부해 본다면 큰 도움이 될 것 같다.