[자료구조] 스택(Stack) 완벽 정리: 작동 원리와 코딩 테스트 활용 전략

1 스택 개념

stack의 어원은 쌓는다이다. 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다. 먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 또는 LIFO(Last In First Out)라고 한다. 이때 스택에 삽입하는 연산을 push, 꺼내는 연산을 pop이라고 한다.

스택의 동작 원리 이해하기

2 스택의 정의

스택의 ADT(Abstract Data Type)라는 것을 정의해보고 실제 스택이 동작하는 원리를 보자. ADT는 추상 자료형이며, 추상 자료형이란 인터페이스만 있고 실제로 구현되지 않은 자료형이다. 일종의 자료형의 설계도라고 생각하면 된다.

스택의 ADT

스택에는 푸시(push), 팝(pop), 가득 찼는지 확인(isFull), 바었는지 확인(isEmpty)과 같은 연산을 정의해야 한다. 그리고 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 탑(top)도 있어야 한다.

구분	정의	설명
연산	boolean isFull()	스택에 들어 있는 데이터의 개수가 maxsize인지 확인해 boolean 값을 반환한다. 가득 차 있다면 True, 아니면 False이다.
연산	boolean isEmpty()	스택에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환한다. 데이터가 하나라도 있으면 False, 아니면 True이다.
연산	void push(ItemType item)	스택에 데이터를 푸시한다.
연산	ItemType pop()	스택에서 최근에 푸시한 데이터를 팝하고, 그 데이터를 반환한다.
상태	Int top	스택에서 최근에 푸시한 데이터의 위치를 기록한다.
상태	ItemType data[maxsize]	스택의 데이터를 관리하는 배열이다. 최대 maxsize개의 데이터를 관리한다.

스택의 원소는 배열이 아니라 다른 자료구조로 관리할 수도 있다.

그림에서는 연산 시 해야 할 동작(operation)과 상태(status)를 정의하고 있지만 세부 구현 내용, 즉, 프로그래밍 언어는 무엇을 사용해야 하고 데이터는 이렇게 저장해야 한다는 등의 내용은 없다. data 배열을 보면 최대 크기는 maxsize이므로 인덱스의 범위는 0부터 maxsize - 1이다. top은 가장 최근에 추가한 데이터의 위치를 참조한다. 지금 그림에서는 아무 데이터도 없으므로 top에 -1이 들어 있다. 만약 top이 0이면 데이터가 1개 있는 것이므로 초기값을 0이 아니라 -1로 했음에 주의하자.

세부 구현을 알아두면 문제를 풀 때 도움이 된다. 코딩 테스트의 문제는 스택으로 풀어라처럼 대놓고 알려주지 않기 때문이다. 내가 어떤 문제를 보고 스택으로 푸는 게 좋겠다! 라는 생각이 떠오르려면 스택의 세부 동작을 충분히 아는 것이 좋다.

자료구조의 세부 동작을 공부하면 큰 도움이 된다. 자료구조의 세부 동작을 이해하면 코딩 테스트뿐 아니라 면접에도 큰 도움이 된다. 자료구조의 세부 동작을 공부하면 그 자료구조의 성능 및 특성을 이해하는 것이고, 이는 효율적인 알고리즘을 떠올릴 수 있게 해주기 때문이다. 실제로 자료구조의 이해도를 요구하는 문제가 출제되기도 한다.

스택 세부 동작에 대해 조금 더 자세히 알아보기

스택에 데이터를 추가하는 경우를 생각해보자. 푸시 연산을 수행할 때 스택 내부에서 일어나는 과정이다. 그림은 push(3) 연산을 수행하며 데이터 3이 추가되는 모습을 보여준다.

연산 과정은 push(3)을 호출하면 내부적으로 1. IsFull()을 수행해 우선 data 배열에 데이터가 가득 찼는지 확인하고, 2. 그렇지 않다면 top을 1만큼 증가시킨 후 top이 가리키는 위치 3. data[0]에 3을 추가한다.

pop() 연산을 수행하는 모습을 보자.

pop() 연산을 수행하면 내부적으로 1. IsEmpty() 함수를 우선 수행해 data 배열에 데이터가 없는 건 아닌지 확인하고, 데이터가 있다면 2. top을 1만큼 감소시키고 3. 데이터 3을 반환한다. 여기서 중요한 점은 data[0] 위치에 있던 3을 지우지 않았다는 점이다. 앞서 정의한 스택의 ADT에서 top은 최근에 삽입한 데이터의 위치라 하였고 top이 가리키는 위치가 -1이므로 실제 data 배열에 데이터가 남아 있더라도 스택은 비어 있다고 보아도 된다. 또한 언어마다 세부적 구현이 달라 pop() 연산을 수행하여 3을 반환하지 않고 그냥 top을 1만큼 감소만 시키는 구현이 될 수도 있으므로 언어별 세부 구현을 확인해야 한다. C++은 pop() 연산을 해도 값을 반환하지는 않는다.

스택 구현하기

코딩 테스트에서는 문제에 적용할 자료구조 혹은 알고리즘을 파악하는 능력이 중요하다. 문제에서 의도한 데이터 흐름이 스택에 딱 맞는지 알아차리는 것이 중요하다. 예를 들어 데이터를 그냥 저장하고 순서와 상관없이 임의 접근하기만 해도 되면 배열을 사용하면 되지만 최근에 삽입한 데이터를 대상으로 뭔가 연산해야 한다면 스택을 떠올리는 것이 좋다. C++은 STL에서 스택을 제공하기 때문에 바로 사용하면 된다.

Python의 경우 표준 라이브러리에 스택 전용 모듈이 없지만 여러 모듈에서 스택처럼 사용 가능한 클래스가 있다.

Algorithm Theory 카테고리 내 다른 글 보러가기