스택(stack)도 연결리스트와 마찬가지로 선형자료구조다. 우리가 알고있는 메모리의 스택도 같은 구조를 가진다. 스택의 특성은 LIFO(Last in First Out)으로 저장되는 구조인데, 스택을 비우는 순서는 가장 마지막으로 넣은 정보부터 빠지게된다. 책을 박스에 차곡차곡 쌓아서 보관해 놓았는데, 다시 책들을 꺼내기 위해서는 맨 위에서부터 빼내야 하는 이치와 같다. 우리가 알고있는 재귀함수를 이용하는 것도 스택의 특성을 사용한다. 좀 더 예를 들어보면 우리가 C프로그래밍을 할 때 가장먼저 호출되는 함수는 main함수다. 하지만 main함수는 가장 마지막에 반환된다. (LIFO == FILO )
우리가 구현하고자 하는 스택을 간략히 표현해 보겠다.
2014/02/28 - [프로그래밍/C언어] - 동적배열 자료구조의 시작
2014/03/17 - [프로그래밍/C언어] - 동적배열에서 memmove함수 사용하기 연습 C언어
2014/03/20 - [프로그래밍/C언어] - 자료구조 - 연결리스트[linked list] C언어
2014/03/22 - [프로그래밍/C언어] - 자료구조 큐(Queue) C언어
stack포인터에 동적으로 크기가 10인 배열을 할당하였다. 데이터공간에 순서대로 4개의 데이타가 들어가 있고, p변수가 마지막 데이타의 첨자를 지니고 있다. 배열의 동적할당은 익숙할 것이다. 여기서 주목해야할 부분은 마지막에 입력된 데이타의 offset을 가지고 있는 p다. p가 항상 마지막에 입력된 데이타의 오프셋을 가지고 있어야 삽입과 삭제를 할 수 있다.
그러면 위 그림을 참고하여 스택에서 필요한 전역변수를 선언해보자.
int *stack;
int size;
int p;
스택을 초기화 하기 위해서는 size를 인수로 입력받고(어떻게하든 상관없다), satck 포인에 size만큼 동적할당을 해야한다. 그리고 p의 위치를 지정해야하는데, 이부분은 p를 -1로 해놓고 데이터입력시 ++p로 해도 되고, p=0으로 초기화 하고 p++ 을 해도 된다.
여기선 p를 -1로 초기화 해보겠다.
다음으로 데이타 입력 함수를 작성하겠다.
bool InStack(int data) {
if (p+1>=size) {
return false;
}
stack[++p] = data;
return true;
}
p+1>=size 의 조건에서 p는 0부터 시작하는 배열의 첨자고 size는 배열의 크기를 나타낸다는 것에 주의하자. 입력함수기 때문에 오버플로우에 대한 조건을 검사한다.
그러면 다음으로 데이타를 꺼내는 함수를 작성할텐데 위와는 반대로 데이타가 텅 비어 있는지를 검사해야한다. 텅 빈상태라면 더이상 꺼낼 데이타가 없으므로 false를 반환해야 할 것이다.
int OutStack() {
if (p<=-1){
return -999;
}
int temp;
temp = stack[p--];
return temp;
}
데이타를 꺼내는 시점에 그 데이타가 어떤 데이타인지를 반환하고, 데이타가 텅비는 시점에서는 -999라는 수를 반환하였다. -999는 더이상 꺼낼 데이타가 없다는 것을 알려주는 반환값으로 보통 스택이 다루지 않는 특이한 값을 선택하도록 하는 것이 좋다.
집어넣는 수의 순서는 1,2,4,7 이지만 반환되는 순서는 7,4,2,1로 반대가 된다. 다음에는 스택과 비슷하지만 스택과 반대로 집어넣는 순서대로 꺼내지는 자료구조인 큐를 공부하겠다.