stack using linked list

스택을 연결리스트로 구현한다. top 은 헤더역할을 하고 새로운 노드가 push되면 top은 새로운 노드를 가리킨다.

 

top의 위치가 헷갈렸다. 새 노드를 마지막노드 다음에 붙이고 거기에 top이 가리키게 한다..

이렇게 하면 삭제와 탐색이 불편해진다. 먼저 pop하기 위해서는 마지막의 이전노드가 필요하고, 탐색하려면 새로운 포인터가 첫 노드를 가리키고 탐색을 시작해야한다. 물론 어렵진 않다.

 

항상 새로운 노드를 push 할때는 마지막 노드의 주소를 다른 포인터변수에 넣어놓으면 그 주소는 새노드의 이전노드가 된다. 그리고 탐색은 head 역할하는 포인터가 있어야 할 듯하다.. 거의 queue 화 되가는 듯..

stack

top이 가리키고 있는 노드가 최신노드이다. 새로운 노드를 push하면 새 노드의 링크필드에 top의 값을 넣고 top은 다시 새 노드의 값는 갖는다. 이렇게 함으로서 top은 새로운 노드를 가리키게 되고 새로운 노드는 다음 노드를 가리킨다.

void push(int d){
	Node * temp = (Node *)malloc(sizeof(Node));
	temp->data = d;
	temp->next = top;
	top = temp;
}

pop을 수행하면 top은 top의 링크필드 값을 갖고 다음 노드를 가리킨다. 그리고 pop될 노드는 free(void *)로 메모리 해제를 한다. 물론 그전에 pop할 노드를 가리킬 포인터 변수를 하나 만들어놓아야 하지 않을까 싶다.

stack

int pop(){
	if(isStackEmpty()) return -1;

	int data = top->data;
	Node * temp = top;
	top = top->next;
	free(temp);
	return data;
}

역시나 연결리스트가 array보다 유연하다. 하지만 적은 데이터(최대갯수를 어느정도 정할 수 있는)가 매우 많이 push와 pop이 일어난다면 array가 더 효율적이지 않을까 싶다. array는 연속된 메모리가 할당되기 때문에 더 빠르게 접근이 가능하고 더 적은 공간과 간결한 명령어로 구현하기때문이다. 케바케로 선택하면 될 듯하다.