이 글에서는 C++를 이용해 스택(Stack) 자료구조를 구현하는 방법을 단계별로 살펴봅니다. 스택은 요소들의 집합을 저장하는 추상 자료구조로, LIFO(Last In First Out), 즉 '나중에 들어간 데이터가 가장 먼저 나온다'는 원칙을 따릅니다.
스택의 핵심 연산은 다음과 같습니다.
- Push(푸시) – 스택의 맨 위(top)에 새로운 데이터를 추가합니다.
- Pop(팝) – 스택의 맨 위에 있는 데이터를 제거합니다.
- Peek(픽) – 스택의 맨 위 데이터를 제거하지 않고 값만 확인합니다.
동작 원리
예를 들어 스택에 11, 22, 33, 44, 55, 66 순서로 데이터를 push하면, pop할 때는 반대 순서인 66, 55, 44, 33, 22, 11 순으로 꺼내게 됩니다. 이것이 바로 LIFO 방식입니다.
알고리즘
1. push(item)
시작
top 포인터를 1 증가시킨다
top 위치에 item을 삽입한다
끝
2. pop()
시작
item = 스택의 최상위 요소
top 포인터를 1 감소시킨다
item을 반환한다
끝
3. peek()
시작
item = 스택의 최상위 요소
item을 반환한다
끝
C++ 예제 코드 (배열 기반)
아래는 배열을 사용해 스택을 구현한 전체 코드입니다. 메뉴 형식으로 push, pop, display 기능을 선택할 수 있도록 작성되었습니다.
#include <iostream>
using namespace std;
int stack[100], n = 100, top = -1;
void push(int val) {
if(top >= n-1)
cout<<"Stack Overflow"<<endl;
else {
top++;
stack[top] = val;
}
}
void pop() {
if(top <= -1)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< stack[top] <<endl;
top--;
}
}
void display() {
if(top>= 0) {
cout<<"Stack elements are:";
for(int i = top; i>= 0; i--)
cout<<stack[i]<<" ";
cout<<endl;
} else
cout<<"Stack is empty";
}
int main() {
int ch, val;
cout<<"1) Push in stack"<<endl;
cout<<"2) Pop from stack"<<endl;
cout<<"3) Display stack"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter choice: "<<endl;
cin>>ch;
switch(ch) {
case 1: {
cout<<"Enter value to be pushed:"<<endl;
cin>>val;
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
cout<<"Exit"<<endl;
break;
}
default: {
cout<<"Invalid Choice"<<endl;
}
}
}while(ch!=4);
return 0;
}실행 결과
1) Push in stack 2) Pop from stack 3) Display stack 4) Exit Enter choice: 1 Enter value to be pushed: 2 Enter choice: 1 Enter value to be pushed: 6 Enter choice: 1 Enter value to be pushed: 8 Enter choice: 1 Enter value to be pushed: 7 Enter choice: 2 The popped element is 7 Enter choice: 3 Stack elements are:8 6 2 Enter choice: 5 Invalid Choice Enter choice: 4 Exit
코드 해설 및 핵심 포인트
이 코드에서 주목해야 할 부분은 다음과 같습니다.
- top 변수 초기화: top을 -1로 설정하여 스택이 비어 있는 상태를 나타냅니다.
- 오버플로우 처리: push 시 top이 n-1보다 크거나 같으면 더 이상 삽입할 공간이 없으므로 'Stack Overflow' 메시지를 출력합니다.
- 언더플로우 처리: pop 시 top이 -1 이하면 스택이 비어 있어 삭제할 요소가 없으므로 'Stack Underflow' 메시지를 출력합니다.
- display 함수: top부터 0까지 역순으로 출력하기 때문에 가장 나중에 들어간 요소가 먼저 표시됩니다.
배열 기반 스택은 구현이 간단하고 접근 속도가 빠르다는 장점이 있지만, 크기가 고정되어 있다는 한계가 있습니다. 실무에서는 std::stack 컨테이너 어댑터를 사용하거나 동적 배열·연결 리스트 기반 구조를 활용하면 유연하게 확장할 수 있습니다.