I'm taehee.won.

 지금까지 만든 스택 연결 리스트가 올바르게 동작하는지 확인하기 위한 출력 함수를 구현하였다.

스택 연결 리스트의 데이터의 입력, 출력이 일어날 Top 의 위치, 데이터를 출력한다.

 스택 연결 리스트의 선언부 이다.(Stack.h)

 스택 연결 리스트의 생성과 관련된 함수(ifCreateStackLinkedList), 소멸과 관련된 함수(ifDestroyStackLinkedList), 기본 기능과 관련된 함수(vfPushStackLinkedList, unfPopStackLinkedList, unfTopStackLinkedList, ifEmptyStackLinkedList) 로 이루어져 있다. 필요에 따라 함수를 수정, 추가, 구현하거나, 저장되는 자료형을 추가한 후, 생성함수를 수정하여 사용할 수 있다.

 스택 연결 리스트의 구현부 이다.(Stack.c)

 마지막으로 스택 연결 리스트를 사용하는 예제이다.

 vfPrintStackLinkedList 함수가 호출되는 시점을 기준으로 다음과 같이 3 단계로 나눌 수 있다.

1 단계 : 스택을 생성한 후, "1, 2, 3, 4, 5" 를 스택에 Push(데이터 저장)

2 단계 : 스택에서 2 번 Pop(데이터 제거)

3 단계 : 스택의 가장 마지막 데이터 출력

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

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

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

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

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

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

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

 지금까지 만든 스택 배열이 올바르게 동작하는지 확인하기 위한 출력 함수를 구현하였다.

 스택 배열의 크기, 데이터의 입력, 출력이 일어날 Top 의 위치, 데이터를 출력한다.

 스택 배열의 선언부 이다.(Stack.h)

 스택 배열의 생성과 관련된 함수(ifCreateStackArray), 소멸과 관련된 함수(ifDestroyStackArray), 기본 기능과 관련된 함수(ifPushStackArray, unfPopStackArray, unfTopStackArray, ifEmptyFullStackArray) 로 이루어져 있다. 필요에 따라 함수를 수정, 추가, 구현하거나, 저장되는 자료형을 추가한 후, 생성함수를 수정하여 사용할 수 있다.

 스택 배열의 구현부 이다.(Stack.c)

 마지막으로 그 동안 구현한 스택 배열을 사용하는 예제이다.

 vfPrintStackArray 함수가 호출되는 시점을 기준으로 다음과 같이 3 단계로 나눌 수 있다.

1 단계 : 배열의 크기를 10 으로 스택을 생성한 후, "1, 2, 3, 4, 5" 를 스택에 Push(데이터 저장)

2 단계 : 스택에서 2 번 Pop(데이터 제거)

3 단계 : 스택의 가장 마지막 데이터 출력

 이해하기 쉬운 배열로 스택을 구현하려 한다. 배열로 스택을 구현하면, 데이터에 접근하기가 쉽고, 구현이 간단하다는 장점이 있다. 하지만, 메모리를 고정하여 사용하기 때문에, 처음에 구성된 스택의 크기를 벗어나는 데이터를 저장할 수 없다는 단점이 있다. 아래의 그림과 같이 스택을 배열로 구현할 것이다. 고정된 크기의 배열을 생성하고, Top 위치를 저장하고 있다가 Push, Pop 등의 연산을 통해 데이터를 저장하고, 제거할 것이다.

 다음은 스택 배열 구조체의 선언이다.

 스택 배열의 크기, 그리고 데이터의 입력, 출력이 일어날 Top 의 위치, 데이터 메모리 주소를 저장한다.

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

 처음에 요청된 스택 배열의 크기만큼의 데이터 공간을 가지고 있게 된다.

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

 가장 위의 그림에서 보여준 것과 같이 기능을 구현하였다. Push(데이터 저장) 함수는 스택의 데이터 공간의 가장 위에 데이터를 저장하고, 가장 위를 저장하는 변수를 증가시킨다. 반대로 Pop(데이터 제거) 함수는 스택의 데이터 공간의 가장 위의 데이터를 반환하고, 가장 위를 저장하는 변수를 감소시킨다.

 일반적으로 사용되는 함수와 다르게 구현한 부분은 Empty 함수이다. 일반적으로 Empty 인지를 반환하는 함수인데, 여기서는 Empty 와 Full 여부를 반환하도록 구현하였다. 이를 통하여, Push 전에 Full 인지를 확인하여, 스택의 데이터 공간이 모두 사용 중이면, Push 를 하지 않거나, Pop 전에 Empty 인지를 확인하여, 스택의 데이터 공간이 하나도 사용하지 않고 있다면, Pop 을 하지 않는 용도로 사용할 수 있다.

 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝 먼저 내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(FILO - First In Last Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸시(push) 라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop) 이라고 하는데, 이 때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

(참고 : http://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D)

 데이터를 저장하는 방법인 스택은 FILO(First In Last Out), LIFO(Last In First Out) 으로 불리는데, 먼저 들어간 자료가 나중에 나오고, 나중에 들어간 자료가 먼저 나온다는 의미이다. 스택의 중요 기능으로는, 데이터를 저장하는 Push, 데이터를 빼내는 Pop 이 있다. 아래의 그림과 같이 Push 를 통해 스택에 데이터를 쌓고(저장), Pop 을 통해 스택에서 데이터를 빼내게(삭제) 된다.

 그 밖의 기능으로는 스택이 비어있는지 확인하는 Empty, 스택의 가장 마지막 데이터를 확인하는 Top 이 있다. 기능만 보더라도 스택은 데이터의 입력, 출력이 자유롭지 않다는 것을 알 수 있다. 단지, 가장 마지막에 저장된 데이터만을 사용할 수 있다. 그럼에도 스택은 범용적으로 쓰이는 자료구조이다. 예를 들어, 정적으로 사용되는 자동 메모리도 스택으로 구현되어 있으며, 네트워크 프로토콜들도 대부분 스택으로 구현되어 있다.