스택(stack)

스택은 탑(top)이라고 하는 한쪽 끝에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트이다. 스택에서는 제일 마지막으로 삽입된 원소가 제일 먼저 삭제되기 때문에 후입선출(LIFO, Last In First Out) 리스트라고도 한다.

스택을 구현하는 가장 쉬운 방법은 1 차원 배열 stack[MAXSIZE]를 사용하는 것인데, 여기서 MAXSIZE는 허용할 수 있는 스택의 최대 크기이다. 스택의 첫 번째 원소, 즉 최하위 원소는 stack[0]에 저장되고, 두 번째 원소는 stack[1], 그리고 i 번째 원소는 stack[i-1]에 저장된다.

변수 top은 스택의 최상위 원소를 가리킨다. 초기에 top은 -1의 값을 가지며 이는 공백 스택을 나타낸다.

다음의 예에서는 element라는 하나의 key 필드 만을 가지는 구조를 사용하지만, 이는 예를 들기 위한 것일 뿐 일반적으로 하나의 필드만을 갖는 구조는 생성하지 않는다. 변수 top과 상수 MAXSIZE를 사용하면...