스택(Stack)은 마지막에 삽입된 데이터가 가장 먼저 삭제되는 LIFO(Last In First Out, 후입선출) 방식으로 동작하는 대표적인 자료구조입니다. 이러한 특성 덕분에 스택은 수식 평가(expression evaluation), 함수 호출 관리, 재귀(recursion) 처리 등 다양한 컴퓨터 과학 분야에서 폭넓게 활용됩니다. 이번 글에서는 스택의 핵심 연산들을 살펴보고, 스택 ADT를 활용한 예제까지 함께 확인해 보겠습니다.
ADT(추상 자료형)란 무엇인가?
ADT(Abstract Data Type, 추상 자료형)는 값들의 집합과 그 위에서 수행할 수 있는 연산들의 집합으로 동작이 정의되는 특수한 자료형입니다. '추상(Abstract)'이라는 표현이 붙는 이유는, 사용자가 해당 자료형을 자유롭게 활용해 여러 연산을 수행할 수 있지만 그 연산이 내부적으로 어떻게 구현되어 있는지는 완전히 숨겨져 있기 때문입니다. 즉, ADT는 기본(primitive) 자료형들을 조합해 만들어지지만, 연산의 실제 구현 로직은 외부에 노출되지 않습니다.
스택 ADT의 주요 연산
- isFull() : 스택이 가득 찼는지 여부를 확인합니다.
- isEmpty() : 스택이 비어 있는지 여부를 확인합니다.
- push(x) : 요소 x를 스택에 삽입합니다.
- pop() : 스택의 최상단(top)에서 요소 하나를 삭제합니다.
- peek() : 스택의 최상단 요소를 삭제하지 않고 조회합니다.
- size() : 현재 스택에 저장된 요소의 개수를 반환합니다.
C++ 예제 코드
#include<iostream>
#include<stack>
using namespace std;
main(){
stack<int> stk;
if(stk.empty()){
cout << "Stack is empty" << endl;
} else {
cout << "Stack is not empty" << endl;
}
//insert elements into stack
stk.push(10);
stk.push(20);
stk.push(30);
stk.push(40);
stk.push(50);
cout << "Size of the stack: " << stk.size() << endl;
//pop and dispay elements
while(!stk.empty()) {
int item = stk.top(); // same as peek operation
stk.pop();
cout << item << " ";
}
}실행 결과
Stack is empty Size of the stack: 5 50 40 30 20 10
코드 설명
위 예제는 C++ STL의 stack 컨테이너를 활용한 것입니다. 프로그램 시작 시점에는 스택이 비어 있으므로 empty() 함수가 true를 반환해 "Stack is empty"가 출력됩니다. 이후 push()를 통해 10부터 50까지 다섯 개의 정수를 차례로 삽입하면, size()는 5를 반환합니다. 마지막 while 루프에서는 top()(peek 연산과 동일한 역할)으로 최상단 값을 읽어낸 뒤 pop()으로 제거하면서 모든 요소를 출력합니다. LIFO 특성 때문에 가장 나중에 삽입한 50부터 역순으로 출력되는 것을 확인할 수 있습니다.