개념
스택(stack)이란 '쌓아 올린 더미'를 의미하는 말로써, 스택 자료 구조 또한 이와 유사한 특성을 가지고 있다. 대형 마트에 배치되어 있는 카트가 훌륭한 예시인데, 아래의 그림을 통해 쉽게 이해할 수 있을 것이다.
대형 마트의 카트 이외에도, 우리가 컴퓨터 프로그램에서 특정 명령을 수행하다가 잘못했을 때 사용하는 Ctrl + z, 즉 되돌리기 또한 이에 속한다.
스택의 경우 위의 그림에서 볼 수 있는 것 처럼 한 쪽이 막힌 구조로 되어 있어 가장 나중에 들어온 자료가 가장 먼저 출력 될 수 있게 한다. 이를 후입선출(LIFO : Last In First Out)이라고 하며, 자료의 출력 순서가 입력 순서와 반대일 경우 매우 유용한 자료 구조이다.
자료의 삽입과 삭제
스택은 일반적으로 배열이나 연결 리스트(Linked List)를 이용해 구현한다. 아래의 그림과 같이 배열의 크기를 n이라고 했을 때 첫 번째 원소는 stack[0]일 것이다. 그리고 마지막 원소는 stack[n-1]이 될 것이다.
크기가 3인 스택을 생성해 원소 A, B, C를 삽입한 후 한 개의 원소를 삭제하는 과정에 대해서 고려해 보자.
이는 아래의 과정으로 진행된다고 생각할 수 있다.
- 크기가 3인 스택을 생성한다.
- 해당 스택에 원소 A를 삽입한다.
- 해당 스택에 원소 B를 삽입한다.
- 해당 스택에 원소 C를 삽입한다.
- 해당 스택의 가장 위에 있는 원소를 삭제한다.
이때, 이 과정을 수행하기 위해 배열로 스택을 구현할 때, 스택의 top를 표시하기 위한 변수가 필수적일 것이다. 스택의 top을 가리키도록 설정한 변수를 앞으로 스택 포인터라고 부르고, 이를 바탕으로 삽입 연산과 삭제 연산을 수행하는 것에 대해 고민해 보자.
-
크기가 3인 스택을 생성
-
원소 A 삽입
-
원소 B 삽입
-
원소 C 삽입
-
제일 위의 원소 삭제
다음 글에서는 이를 어떻게 각각 C언어로 구현할 수 있는지, 그리고 추상 자료형으로서 스택은 어떻게 표현이 가능한 지에 대해서 다룰 것이다.
참고
정관용, 임종범, 박병기, 복대원. (2013). 고등학교 정보과학 (pp. 190-193). 서울: (주)현대아트컴.
