C로 만드는 자료구조- Stack이란?

스택(Stack)이란?

 영어 단어 stack은 ‘쌓다‘‘쌓다 ‘라는 뜻이 있고 명사로는 물건들이 쌓여있는 '더미'를 의미한다. 자료구조에서의 스택도 자료를 쌓아두는 기능을 한다. 일반적인 ’더미‘’ 더미‘와 다르게 스택은 스택만의 고유 특성을 가지고 있다.
 그 특성은 LIFO(Last-In-First-Out) - 후입선출(後入先出), 즉, 가장 나중에 들어간 자료가 가장 먼저 나오는 자료이다'라는 특성이다. 이러한 특성 때문에 스택에서 자료를 꺼낼 때에는 앞서 배운 리스트와 다르게 가장 나중에 들어간 자료만 꺼낼 수 있다. 추가적으로 스택은 선형 자료구조로, 선형의 의미는 저장된 자료들 사이의 선후관계가 모두 1대11대 1 관계라는 뜻이다. 다시말해 하나의 물건 위에는 오직 하나의 물건만을 쌓을 수 있다는 것이다.

 스택의 후입선출과 같은 특이한 특성 덕분에 스택 내에서의 자료 추가/제거는 무조건 스택의 끝에서만 이루어진다. 여기서 스택의 끝은 스택의 제일 위(Top)이라고 하며 가장 최근에 자료가 추가된 곳이다.  따라서 모든 곳에서 자료 추가/제거가 가능한 리스트와는 다르게 스택 내에서 연산을 구현할 때 스택의 제일 윗부분만 신경 쓰면 되기 때문에 구현은 비교적 간단한 편이다.

 후입선출의 특성을 지니는 스택은 이러한 특성 덕분에 여러 곳에서 사용된다. 특히 다양한 알고리즘에서 필수적인 요소로 사용된다. 예를 들어 수식을 해석하고 계산하는 데 사용되기도 하며, 웹 페이지에서 뒤로 가기,  재귀 함수 같은 경우도 스택을 기반으로 두고 있다. 그 외에도 트리나 그래프 등 복잡한 자료구조에도 내부적으로 사용된다.

스택의 개념

 앞서 말했듯이 스택은 자료를 한 방향으로만 쌓는 자료구조이다. 스택에는 3가지 핵심 연산이 있는데 이를 알아보자.

- 푸시(push)

push는 새로운 자료를 스택에 추가하는 연산을 말한다. 앞서 말했듯이 새로운 자료추가 즉, push 연산은 무조건 스택의 제일 위에서만 발생한다.

 이때 보통 스택을 만들 때 스택의 크기를 정하는데 스택의 크기는 저장할 수 있는 최대 자료의 수를 의미한다. 만약 push연산을 실행할 때 이미 자료가 가득 차있는 경우라면 스택의 크기를 초과하기 때문에 오류가 발생할 것이다. 이 현상을 넘침(overflow) 현상이라고 한다.

 추가적으로 가장 맨위에 저장되어 있는 자료를 가리키는 것을 스택의 탑(Top)라고 한다. 스택의 구현에서 자료의 추가/제거는 무조건 스택의 탑에서 발생하기 때문에 스택의 탑을 어떻게 변경해야 할지가 매우 중요하다.

- 팝(pop)

 pop은 스택에서 자료를 꺼내는 연산을 의미한다. 이때 자료를 반환하고 제거까지 한다. 또한 push연산과 마찬가지로 무조건 스택의 탑에서만 발생한다.

 만약 스택이 자료가 하나도 없는 공백 상태일 때 pop연산을 실행하면 어떻게 될까? 스택 내에서 반환할 자료가 아무것도 없기 때문에 오류가 발생할 것이다. 이 현상을 부족(Underflow) 현상이라고 한다.

- 피크(peek)

 peek연산은 pop연산과 똑같이 스택의 탑에 있는 자료를 반환한다는 점은 똑같지만 pop은 자료를 반환하고 제거까지 하지만 peek는 자료를 제거하지 않고 반환만 한다. 

스택의 추상자료형

스택 사용에 필요한 기본 연산을 정리한 스택의 추상 자료형(ADT:Abstract Data Type)을 표로 정리했다. 

이름	입력	출력	설명
스택 생성	최대 원소 개수 n	스택 S	최대 n 개의 원소를 가지는 공백 스택 S를 생성
공백 여부 판단 (isEmpty)	스택 s	True/False	스택 S가 공백 스택인지 확인
원소 추가 가능 여부 판단 (isFull)	스택 s	True/False	스택 S의 원소 개수가 최대 원소 개수보다 작은지 판단하여 원소 추가 여부 확인
자료 추가(push)	스택 s, 원소 e	성공/실패 여부	원소 e를 스택에 추가(맨 위에 있는 원소)
자료 제거(pop)	스택 s	해당 원소	스택 S에서 원소 e를 제거(맨 위에 있는 원소) 후 반환
자료 반환(peek)	스택 s	해당 원소	스택 S에서 원소 e를 반환(맨 위에 있는 원소)
스택 삭제	스택 s	N/A	스택 S를 삭제함

스택 생성시에 필요한 입력 파마리터 최대 원소 저장 개수를 뜻하는 n은 배열을 이용해 스택을 구현할때만 필요한 입력 파라미터 이다.
 push, pop, peek는 앞서 설명한 연산들을 의미하며 isFull과 isEmpty는 각각 스택이 가득 차있는 상태인지, 공백 스택인지 알려주며 연산을 실행할 때 도움을 준다.

스택의 구현

 이제 스택을 구현을 해볼 텐데 리스트 구현과 마찬가지로 배열을 이용해 구현하는 방법과, 포인터로 구현하는 방법 2가지가 있다. 차이점은 리스트 때와 마찬가지로 배열을 이용했을 때는 스택의 크기는 고정이고 포인터를 이용했을 때는 구현은 상대적으로 어렵지만 스택의 크기를 가변적으로 할 수 있어 메모리 효율이 높다는 점이다.

 또한 스택의 경우에는 앞서 구현해본 리스트보다 비교적 간단하다. 이는 스택의 탑에서만 연산이 이루어진다는 특성 때문에 모든 위치에 접근이 가능한 리스트에 비해 경우의 수가 적기 때문이다.