[자료구조] 스택

1. 스택이란?

책상에 쌓여있는 책, 창고에 쌓여있는 상자등이 스택의 전형적인 예이다.

스택의 예시 : 쌓여있는 상자들

새로운 상자를 쌓을 때는 상자더미의 맨 윗부분에 놓을 것이고, 상자가 필요하면 상자더미의 맨 위에 있는 상자를 꺼낼 것이다. 만약 중간에서 상자를 꺼내면 전체 상자 더미가 붕괴될 것이다. 따라서 가장 최근에 들어온 상자가 가장 위에 있게 되고, 또 먼저 나가게 된다. 이런 입출력 형태를 후입선출(LIFO : Last-In First-Out)이라고 한다.

 

스택의 구조

스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 위 그림처럼 스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고 반대쪽인 바닥부분을 스택 하단(stack bottom)이라고 한다. 스택에 저장되는 것을 요소(element)라 부른다. 스택에 요소가 하나도 없을 때 그러한 스택을 공백 스택(empty stack)이라고 한다.

 

스택은 특히 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 매우 요긴하게 사용된다. 예를 들면 (A, B, C, D, E)의 데이터가 있을 때 데이터들의 순서를 (E, D, C, B, A)처럼 역순으로 하고 싶다면 데이터를 전부 스택에 입력했다가 다시 꺼내면 역순으로 만들 수 있다. 또 예를 들면 텍스트 에디터에서 "되돌리기"(undo) 기능을 구현할 때 스택을 사용할 수 있다. 왜냐하면 수행된 명령어들 중에서 가장 최근에 수행된 것부터 되돌리기를 하여야 하기 때문이다.

 

 

2. 시스템 스택을 이용한 함수 호출

컴퓨터 안에서는 수많은 함수 호출이 이루어지는데, 함수는 실행이 끝나면 자신을 호출한 함수로 되돌아가야 한다. 이때 스택이 사용된다. 즉 스택은 복귀할 주소를 기억하는데 사용된다. 함수는 호출된 역순으로 되돌아가야 하기 때문이다.

함수호출에서의 스택의 사용

위 그림은 함수 호출에서의 시스템 스택(운영체제가 사용하는 스택)의 사용을 보여준다. 시스템 스택에는 함수가 호출될 때마다 활성 레코드(activation record)가 만들어지며 여기에 복귀주소가 저장된다. 활성 레코드에는 프로그램 카운터 뿐만 아니라 함수 호출시 매개변수와 함수 안에서 선언된 지역 변수들이 같이 생성된다.

함수 호출이 일어나면 항상 시스템 스택에 동일한 방법으로 저장되므로, 함수가 자기 자신을 호출하여도 동일한 방법으로 활성 레코드가 만들어졌다가 없어지게 된다.

 

 

3. 추상 자료형 스택

스택을 추상 자료형으로 정의하여 보자. 추상 자료형으로서의 스택은 0개 이상의 요소를 가지는 선형 리스트의 일종으로 정의되며 스택에 요소를 추가하거나 삭제하는 연산과 현재 스택 상태를 검사하는 연산들로 구성된다.

객체 : 0개 이상의 원소를 가지는 유한 선형 리스트
연산 : 
  - create(size) : 최대 크기가 size인 공백 스택을 생성한다.
  - is_full(s) : if(스택의 원소수 == size) return TRUE;
                    else return FALSE;
  - is_empty(s) : if(스택의 원소수 == 0) return TRUE;
                        else return FALSE;
  - push(s, item) : if( is_full(s) ) return ERROR_STACKFULL;
                          else 스택의 맨 위에 item을 추가한다.
  - pop(s) : if( is_empty(s) ) return ERROR_STACKEMPTY;
                  else 스택의 맨 위의 원소를 제거해서 반환한다.
  - peek(s) : if( is_empty(s) ) return ERROR_STACKEMPTY;
                   else 스택의 맨 위의 원소를 제거하지 않고 반환한다.

 

스택에는 두 가지의 기본 연산이 있다. 하나는 삽입 연산으로 push 연산이라고 하고 또 하나는 삭제 연산으로 pop 연산이라고 한다. 밑에 그림은 스택에서의 push와 pop 연산 과정이다. 만약 push()를 했을 때 스택이 가득차서 입력이 불가능하다면 오류가 발생한다. 마찬가지로 pop() 연산 중에 스택에 데이터가 없어서 출력이 불가능하다면 역시 오류가 발생한다.

스택의 push()와 pop() 과정

 

스택을 구현하는 방법에는 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 있다. 배열은 구현하는 방법은 간단하고 성능이 우수한 반면에 스택의 크기가 고정되는 약점이 있다. 연결 리스트를 이용하는 방법은 구현이 약간 복잡한 반면, 스택의 크기를 필요에 따라 가변적으로 할 수 있다.

 

 

참고

• C언어로 쉽게 풀어쓴 자료구조 책