[C] 스택 (Stack) 연결 리스트 (Linked List) 1. 생성 / 소멸 / 기능(Push, Pop, Etc)

 연결 리스트 (Linked List) 로 스택을 구현하려 한다. 연결 리스트로 스택을 구현하면, 배열 스택의 단점인 고정된 데이터 저장 공간이라는 점을 극복할 수 있다. 아래의 그림과 같이 스택을 연결 리스트로 구현할 것이다. 단순 연결 리스트 (Single Linked List) 로 구현하되, 마지막 노드를 가리키는 포인터 변수를 저장하여 Push 와 Pop 연산시, 마지막 노드를 탐색하는 시간을 줄이도록 한다.

 

  다음은 스택 연결 리스트 구조체의 선언이다.

 데이터가 저장되는 리스트의 첫번째 노드, 마지막 노드를 가리키는 포인터 변수를 저장한다.

 

 다음은 스택 연결 리스트의 생성 함수, 스택 연결 리스트의 사용이 끝났을 때, 해당 메모리를 반환하는 함수이다.

 

 다음은 스택의 기능인 Push(데이터 저장), Pop(데이터 제거), Top, Empty 함수이다.

 가장 위의 그림에서 보여준 것과 같이 기능을 구현하였다. 단순 연결 리스트는 이전에 구현하였으므로, 구현해놓은 헤더파일(SingleLinkedList.h) 을 포함시켜서 이용하였다. Push(데이터 저장), Pop(데이터 제거) 함수는 기능상 동일하나, 단순 연결 리스트이므로, Pop 시에 이전 노드를 가리키기 위한 연산이 추가되었다. 이 연산을 더 효율적으로 하기 위해서는 이중 연결 리스트 (Double Linked List) 로 구현하면 된다.

 연결 리스트 스택은 배열 스택과 달리 스택이 Full 인지를 확인할 필요가 없다. 메모리를 데이터에 맞게 할당받아 저장하기 때문에 필요에 따라 계속해서 데이터를 저장할 수 있다.