연결리스트로 스택 구현

1. 노드 선언

 

배열이 아닌 연결리스트로 스택을 구현해보자.

 

배열을 이용한 스택과는 달리 연결된 스택에서는 각 요소들을 한꺼번에 할당하지 않고 필요할 때 마다 하나씩 동적으로 할당한다. 

 

노드 구조체를 정의해야 하는데, 데이터필드와 다음 노드를 가리키는 링크필드를 다음과 같이 정의한다.

 

typedef int Element; // 노드의 데이터필드인 Element를 정의한다.
//여기서는 int가 데이터형이 된다.

//자기 참조 구조체를 통해서 노드를 정의해주고
struct LinkedNode {
	Element data;
	struct LinkedNode* link;
};

typedef struct LinkedNode Node;

//typedef 함수를 이용하여 'strcut LinkedNode'를 'Node'라는 이름으로 정의해준다.

 

배열이 아니므로 데이터배열 data[]을 선언할 필요도 없다. index를 나타내던 top은 포인터가 된다.

 

연결 리스트로 구현한 스택에서 top은 헤드 포인터이다. 오류를 막기 위해 선언 하면서 NULL로 초기화한다.

 

 

Node* top = NULL;

 

연결된 스택에서 공백상태는 헤드 포인터 top이 NULL값을 갖는 경우이다. 그리고 포화 상태는 동적 메모리 할당만 된다면 노드를 생성할 수 있기 때문에 의미가 없다. 따라서 스택의 초기화는 공백상태로 만드는 것이므로 top에 NULL을 복사하면 된다.

 

2. 삽입 연산

 

먼저 그림과 같이 헤드 포인터 top이 노드 C를 가리키고 있고, C의 링크 필드가 노드 B를, B의 링크 필드가 다시 노드 A를 가리키고 있다고 하자. 이것은 스택에 노드 A, 노드 B, 노드 C가 순서대로 삽입된 상황이다. 노드 A의 링크 필드는 NULL 값을 갖는데, 이것은 더 이상 연결된 노드가 없다는 것을 의미한다.

 

새로운 노드 D를 스택에 삽입하는 연산을 생각해 보자. 연산이 성공하면 top은 노드 D를 가리키고, D는 C를 가리켜야 한다. 포인터 p가 노드 D를 가리키고 있다고 하면, 삽입 연산은 다음과 같이 두 단계로 이루어진다.

 

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

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

 

삽입 연산은 다음과 같이 쓸 수 있다.

 

void push(Element e)
{
	Node* p = (Node*)malloc(sizeof(Node)); //노드 동적 할당
	p->data = e; // Element e로 초기화해줌

	p->link = top; // 기존 헤더가 가지고 있던 주소를 link에 저장
	top = p; // 새롭게 추가된 노드의 주소가 헤더로 저장됨.
}

 

void main()
{
	Element a = 10;
	Element b = 20;
	Element c = 30;

	push(a);
	push(b);
	push(c);

	printf("%d", top->link->link->link);
}

 

직접 a, b, c 차례대로 푸쉬를 해봤다. a의 링크 값인 Null이 나온다.

 

3. 삭제 연산

스택에서의 삭제는 가장 최근에 삽입된 요소를 꺼내 반환하는 것이다. 삭제 연산 과정은 다음과 같다.

(1) 포인터 변수 p가 노드 C를 가리키도록 함: p = top;

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

 

코드로 나타내면.

 

Element pop()
{
	Node* p; // top이 가지고 있던 주소를 임시로 받아줄 포인터변수 p 선언
	Element e;

	p = top; // top이 가지고 있던 주소를 임시로 받고
	top = p->link; // 그 주소에 있는 노드의 링크를 top에 넣는다
	e = p->data; // 데이터를 e로 받고
	free(p);//할당된 동적 메모리를 해제한다.
	return e; // 데이터를 반환한다.
}

 

근데 굳이 포인터변수 p를 선언하고 해야하나?

 

Element pop()
{
	Element e;
	e = top->data;
	top = top->link;
    return e;
}

 

위에 처럼 써도 똑같이 나온다..

 

Node* p; 를 선언하지 않고

e= top->data;

top=top->link; 를 해도 잘 되는데 왜 포인터 변수 p를 사용하는지는 모르겠다. 나중에 알게 되겠지 흠.