오늘의 공부

스택  C언어로 구현하기 (연결리스트)

Stack!

먼저 들어온 데이터가 나중에 나가는 구조를 가지고 있는 스택은 배열과 연결리스트로 구현할 수 있다.

그 중 연결리스트의 구현 방법은 다음과 같다. 

◎ 연결리스트

배열을 이용한 것과 달리 연결 리스트로 구현한 스택에서는 요소들을 한꺼번에 할당하는 것이 아니다.

동적 할당을 이용해서 필요할 때마다 하나씩 할당하는 방식을 이용한다. 

연결리스트로 구현하기 위한 스택은 아래와 같은 노드 구조체를 추가로 정의해야 한다.

이 때 스택에 저장할 정보(데이터 필드)와 함께 다음 노드를 가리키기 위한 포인터(링크 필드)를 멤버로 가진다.

typedef struct LinkedNode
{
	int data; // 데이터 필드
	struct LinkedNode* link // 링크 필드(포인터) -> 다음 노드를 가리킴
 } Node; 

배열에서는 top(제일 위의 값)을 index값으로 저장했지만 연결리스트에서는 포인터로 저장해야 한다.

즉 헤드포인터를 저장하는 것이다.

헤드 포인터가 이해가 안된다면 ?

○삽입

만약 C->B->A 순으로 연결되어 있다면 헤드 포인터 top은 C를 가리키고 있고 C의 링크 필드가 B를 B의 링크 필드가 A를 가리키고 있을 것이다. 

여기에 새로운 노드 D를 삽입하려고 하면 성공했을 경우 top은 D의 노드를 가리키고 D는 C를 가리켜야 한다.

(왜? 스택의 특성상 먼저 들어온 값이 앞, 또는 위에 있기 때문에) 

1. 노드 D의 링크 필드가 노드 C를 가리키도록 함 p->link = top;

2. 헤더 포인터 top이 노드 D를 가리키도록 함 top = p;

이 두 가지의 과정을 거치면 push를 구현할 수 있다. 

void push(int e)
{
	Node* p = (Node*)malloc(sizeof(Node));
 	p->data = e;   // 데이터를 초기화
    
	p->link = top; // 1번
	top = p;   // 2번
 } 

○삭제

삭제 연산은 가장 최근에 삽입된 요소를 꺼내서 반환하는 연산이다.

스택은 FIFO, 즉 First in First Out인 큐와 달리 FILO(First in Last Out)이므로 삭제 시에 가장 최근에 삽입된 요소를 꺼내게 된다. 

1. 포인터 변수 p가 노드 C를 가리키도록 함 p = top

2. 헤더 포인터 top이 다음 노드를 가리키도록 함 top = p->next 

이 연산을 구현할 때 신경써야 할 부분은 메모리를 동적으로 해제하는 것이다.

항목을 반환하기 위해서 해제 하기 전에는 데이터 필드를 저장해두고 노드를 해제한 후에 저장된 항목을 반환해야 한다. 

int pop()
{
	Node* p;
	int e;
	if(is_empty())   // 스택이 비었는지 확인 -> 비었으면 pop할 데이터 X
    	error("스택 공백 에러");

	p = top;
	top = p->link;
	e = p->data;
	free(p); // 노드 동적 해제하기
	return e; // 반환
} 

참고 자료;

두근두근 자료구조 (출판사; 생능출판, 저;최영규, 천인국, 공용해)