[자료구조] 스택 ( stack ) 의 구현. 연결 자료구조.

이전 포스팅의 순차 자료구조를 이용한 스택은 구현하기는 쉽지만, 물리적으로
크기가 고정된 배열을 사용하기 때문에 스택의 크기를 변경하기가 어렵고 메모

리의 낭비가 생길 수 있다는 문제가 있다. 이러한 순차 자료구조의 문제는 연결
자료구조를 사용함으로써 해결할 수 있다.

연결 자료 구조 중에서 단순 연결 리스트를 이용하여 스택을 구현하면 스택의

원소는 연결리스트의 노드가 된다. 스택에 원소를 삽입할 때 마다 연결 리스트

에 노드를 하나씩 연결한다. 그리고 스택 원소의 순서는 연결 리스트 노드의 링

크를 사용하여 표현한다. 스택의 top을 표현하기 위해서 노드에 포인터 top을

사용한다. 스택의 초기 상태는 포인터 top을 NULL 포인터로 설정하여 표현한

다.

다음은 간단히 구현해본 연결 자료구조 스택 소스 이다...

#include <stdio.h>

typedef struct stackNode{

 int data ;
 struct stackNode *link ;

}stackNode ;

stackNode* top ;

void push(int Num)
{
 stackNode* temp = new stackNode ;
 temp->data = Num ;
 temp->link = top ;
 top = temp ;
}

int pop()
{
 int Num ;
 stackNode* temp = top ;

 if(top == NULL )
  return 0 ;
 else
 {
  Num = temp->data ;
  top = temp->link ;
  delete temp ;
  return Num ;
 }
}

void printStack()
{
 stackNode* p = top ;
 
 printf("STACK [") ;

 while(p)
 {
  printf(" %d ", p->data ) ;
  p = p->link ;
 }
 printf(" ] \n ") ;
}

void main()
{
 top = NULL ;
 
 printStack() ;

 push(1) ;

 printStack() ;

 push(2) ;

 printStack() ;

 push(3) ;

 printStack() ;

 pop() ;

 printStack() ;

 pop() ;

 printStack() ;

 pop() ;

 printStack() ;
}

순차 구조와 거의 비슷하지만, 각 함수별로 저장하는 방식만 조금 다를 뿐이

다... 그리고 할당된 메모리를 해제하는 부분이 값을 빼는 부분에만 있기 때문

에 값을 많이 넣고, 그냥 종료해버리면 메모리누수가 생길 것이다..

이 것은 조금만 고민하면 알 수 있는 것이니 소스를 조금씩 개인적으로 수정해

서 쓰길 바란다..