스택stack 어원은 ‘쌓는다’입니다. 스택은 어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조입니다. 스택은 우리 주변에서도 쉽게 찾아볼 수 있습니다. 티슈를 생각해봅시다. 티슈를 만들 때는 먼저 넣은 티슈가 가장 아래에 위치합니다. 그래서 티슈를 사용할 때는 가장 위에 있는 티슈부터 사용할 수 있죠.
이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 또는 LIFO(Last In First Out)이라고 합니다. 이때 스택에 삽입하는 연산을 푸시(push), 꺼내는 연산을 팝(pop)이라고 합니다.
[코딩 테스트] C++ 스택 | 원리, 정의, 구현
1. 스택 개념
1.1 스택의 동작 원리 이해하기
다음 그림을 통해 스택에서 원소가 이동하는 과정을 이해해봅시다.
01단계 초기에는 빈 스택이 있습니다.
02단계 여기에 데이터 ‘1’을 푸시해봅시다. 그럼 다음과 같을 겁니다.
03단계 그럼 여기에 데이터 ‘2’를 또 푸시하면 어떻게 될까요? ‘1’ 위로 ‘2’가 올라갑니다.
04단계 그럼 팝을 하면 어떻게 될까요? 가장 위에 있는 데이터 ‘2’가 빠져나옵니다.
05단계 그리고 다시 데이터 ‘3’을 푸시하면? 다시 ‘1’위에 ‘3’이 위치하게 되었습니다.
06단계 팝을 2번 연속으로 하면 ‘3’, ‘1’ 순서로 데이터가 빠져나올 겁니다.
이를 통해 스택에서 데이터가 이동하는 원리를 잘 이해했길 바랍니다.
2. 스택의 정의
스택이 어떤 방식으로 동작하는지는 이해했을 겁니다. 이제 스택의 ADT라는 것을 정의해보고 실제 스택이 동작하는 원리를 설명하겠습니다. ADT는 우리말로 추상 자료형(abstract data type)인데요. 추상 자료형이란 인터페이스만 있고 실제로 구현되지 않은 자료형입니다. 일종의 자료형의 설계도라고 생각하면 됩니다. 그렇다면 스택은 어떤 정의가 필요한 자료구조일까요?
※ 언어에 따라 표준 라이브러리에서 스택 제공 여부는 다릅니다. C++은 STL에서 스택을 사용할 수 있도록 제공합니다.
2.1 스택의 ADT
우선 스택에는 ① 푸시(push), ② 팝(pop), ③ 가득 찼는지 확인(isFull), ④ 비었는지 확인(isEmpty)과 같은 연산을 정의해야 합니다. 그리고 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 ⑤ 탑top도 있어야 합니다. 표와 그림으로 정리하면 다음과 같습니다.
※ 여기서는 스택의 내부 데이터를 배열로 관리하는 모습을 예로 들었습니다. 하지만 스택의 원소는 배열이 아니라 다른 자료 구조로 관리할 수도 있습니다.
그림은 스택의 ADT를 나타낸 겁니다. 스택 외부와 내부에 네모 모양으로 표현한 연산과 상태가 보입니다. 그림에서는 연산 시 해야 할 동작과 상태가 가지고 있어야 할 값을 정의하고 있기는 하지만 세부 구현 내용, 즉, 프로그래밍 언어는 무엇을 사용해야 하고 데이터는 이렇게 저장해야 한다는 등의 내용은 없습니다. data 배열을 보면 최대 크기는 maxsize이므로 인덱스의 범위는 0부터 maxsize – 1입니다. top은 가장 최근에 추가한 데이터의 위치를 참조합니다. 지금 그림에서는 아무 데이터도 없으므로 top에 -1이 들어 있습니다. 만약 top이 0이면 데이터가 1개 있는 것이므로 초깃값을 0이 아니라 -1로 했음에 주목하세요.
그렇다면 우리는 스택을 공부를 할 때 ADT만 알면 되고 세부 구현은 몰라도 될까요? 사실은 세부 구현을 알아두면 도움이 됩니다. 왜냐하면 어떤 문제도 ‘스택으로 푸세요’라고 대놓고 알려주지는 않기 때문입니다. 만약 여러분이 어떤 문제를 보고 ‘스택으로 푸는 게 좋겠다’라는 생각이 떠오르려면 스택의 세부 동작을 충분히 아는 것이 좋습니다.
💡합격 조언 : 자료구조의 세부 동작을 공부하면 큰 도움이 됩니다
자료구조의 세부 동작을 이해하면 코딩 테스트뿐 아니라 면접에도 큰 도움이 됩니다. 왜냐하면 자료구조의 세부 동작을 공부하면 그 자료구조의 성능 및 특성을 이해하는 것이고, 이는 효율적인 알고리즘을 떠올릴 수 있게 해주기 때문입니다. 실제로 자료구조의 이해도를 요구하는 문제가 출제되기도 합니다. 꼭 한 번은 자료구조의 세부 동작을 공부하기 바랍니다.
2.2 스택 세부 동작에 대해 조금 더 자세히 알아보기
스택에 데이터를 추가하는 경우를 생각해봅시다. 이번에 설명할 내용은 이 푸시 연산을 수행할 때 스택 내부에서 일어나는 과정입니다. 그림은 push(3) 연산을 수행하며 데이터 3이 추가되는 모습을 보여줍니다.
연산 과정은 push(3)을 호출하면 내부적으로 ① IsFull( )을 수행해 우선 data 배열에 데이터가 가득 찼는지 확인하고, ② 그렇지 않다면 top을 1만큼 증가시킨 후 top이 가리키는 위치 ③ data[0]에 3을 추가합니다.
반대로 pop( ) 연산을 수행한다면 어떨까요?
그림에서 보듯 pop( ) 함수를 수행하면 내부적으로 ① IsEmpty( ) 함수를 우선 수행해 data 배열에 데이터가 없는 건 아닌지 확인하고, 데이터가 있다면 ② top을 1만큼 감소시키고 ③ 데이터 ‘3’을 반환합니다. 여기서 ‘3이 남아 있는데?’라고 생각할 수도 있습니다. 앞서 정의한 스택의 ADT에서 top은 최근에 삽입한 데이터의 위치라고 했습니다. 즉, top이 가리키는 위치는 -1이므로 실제 data 배열에 데이터가 남아 있더라도 스택은 비어 있다고 보아도 됩니다.
2.3 스택 구현하기
코딩 테스트에서는 문제에 적용할 자료구조 혹은 알고리즘을 파악하는 능력이 중요합니다. 문제에서 의도한 데이터 흐름이 스택에 딱 맞는지 알아차리는 것이 중요하죠. 예를 들어 데이터를 그냥 저장하고 순서와 상관없이 임의 접근하기만 해도 되면 배열을 사용하면 되지만 최근에 삽입한 데이터를 대상으로 뭔가 연산해야 한다면 스택을 떠올리는 것이 좋습니다. C++은 STL에서 스택을 제공하기 때문에 바로 사용하면 됩니다. 스택의 주요 메서드를 활용하는 코드 예를 한 번 보면 쉽게 사용할 수 있을 겁니다.
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> st; // int 타입의 스택 생성
// push() : 요소를 스택 맨 위에 추가. 시간 복잡도: O(1)
st.push(10); // 스택: 10
st.push(20); // 스택: 10, 20
st.push(30); // 스택: 10, 20, 30
// 스택이 비어 있을 때까지 반복
while (!st.empty()) {
// top(): 스택에 마지막으로 삽입한 원소 반환. 시간 복잡도: O(1)
cout << st.top() << " "; // 현재 스택의 맨 위 요소 출력
// pop() : 스택의 맨 위 원소 제거. 시간 복잡도: O(1)
st.pop(); // 출력한 요소 제거
}
cout << endl; // 줄바꿈
return 0;
}
위 코드의 출력값은 30 20 10입니다. LIFO대로 동작하죠. 다만 ADT에서 설명한 top( ), pop( ) 메서드와 결은 비슷하지만 세부 동작이 달라 헷갈릴 수 있습니다. STL의 스택은 top( )은 최근에 넣은 원소를 반환하고, pop( )은 최근에 넣은 원소를 삭제한 후 아무것도 반환하지 않습니다. 스택의 LIFO 동작은 옳게 구현되었으나 세부 동작이 다른 것이므로 오해 없기 바랍니다. 이 부분은 언어마다 상이하지만 C++에서 스택을 사용할 때는 반환값이 없다는 것을 알아두세요.
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
