[C++ STL] stack 완벽 정리: 기본부터 심화까지 (면접 대비)
카테고리: STL
태그: algorithm C++ coding test data structure stack implementation STL stack
1. 📚 stack의 개념
C++ STL(Standard Template Library)에서
std::stack은 LIFO(Last In First Out) 원칙을 따르는 컨테이너 어댑터로, 기본적으로std::deque를 기반으로 구현되며, 그 단순성과 효율성 덕분에 다양한 상황에서 활용된다.
📌 stack의 특징
- LIFO 구조: 마지막에 삽입된 요소가 가장 먼저 제거되는 후입선출 구조를 따른다.
- 제한된 접근: 스택의 맨 위(top)에서만 요소를 추가하거나 제거할 수 있다.
- 컨테이너 어댑터: 실제 컨테이너를 감싸서 스택 인터페이스를 제공하는 래퍼 클래스이다.
- 어댑터 패턴: 기존 컨테이너의 인터페이스를 새로운 인터페이스로 변환하는 디자인 패턴을 사용한다.
- 기반 컨테이너:
std::deque,std::vector,std::list등이 기반 컨테이너로 사용될 수 있다. - 인터페이스 제한: 기반 컨테이너의 모든 기능을 노출하지 않고, 스택에 필요한 기능만 제공한다.
- 템플릿 매개변수:
template <class T, class Container = deque<T>> class stack;T: 저장할 요소의 타입Container: 기반이 될 컨테이너 타입 (기본값:std::deque<T>)
- 요구사항: 기반 컨테이너는 다음 멤버 함수들을 반드시 제공해야 한다.
back(): 마지막 요소 접근push_back(): 끝에 요소 추가pop_back(): 마지막 요소 제거empty(): 컨테이너가 비어있는지 확인size(): 컨테이너의 크기 반환
- 기본 컨테이너: 기본적으로
std::deque를 사용하지만, 다른 컨테이너로 변경 가능하다.
🔍 컨테이너 어댑터의 장점
- 코드 재사용: 기존 컨테이너의 구현을 재사용하여 코드 중복을 방지한다.
- 유연성: 기반 컨테이너를 쉽게 교체할 수 있어 상황에 맞는 최적화가 가능하다.
- 인터페이스 단순화: 복잡한 컨테이너의 인터페이스를 단순하고 직관적인 인터페이스로 변환한다.
- 일관성: STL의 다른 컨테이너 어댑터(
std::queue,std::priority_queue)와 일관된 사용법을 제공한다.
💡 컨테이너 어댑터 사용 예시
// 기본 컨테이너(std::deque)를 사용하는 스택
std::stack<int> default_stack;
// std::vector를 기반으로 하는 스택
std::stack<int, std::vector<int>> vector_stack;
// std::list를 기반으로 하는 스택
std::stack<int, std::list<int>> list_stack;
// 기존 컨테이너로 초기화
std::vector<int> vec = {1, 2, 3, 4, 5};
std::stack<int, std::vector<int>> initialized_stack(std::move(vec));
2. 💻 stack의 기본 사용법
📋 stack 선언 및 초기화
-
기본 선언:
std::stack<T> stack_name; // T는 요소의 타입 -
다른 컨테이너를 사용한 선언:
std::stack<T, std::vector<T>> stack_name; // vector를 기반으로 하는 스택 std::stack<T, std::list<T>> stack_name; // list를 기반으로 하는 스택 -
기존 컨테이너로 초기화:
std::vector<int> vec = {1, 2, 3, 4, 5}; std::stack<int, std::vector<int>> s(std::move(vec)); // vector를 이동하여 초기화
🔧 요소 추가 및 삭제
-
요소 추가:
s.push(6); // 맨 위에 요소 추가 s.emplace(7); // 맨 위에 요소를 직접 생성하여 추가 (임시 객체 생성 방지) -
요소 제거:
s.pop(); // 맨 위 요소 제거 (반환값 없음)
🔍 요소 접근
-
맨 위 요소 접근:
int top_element = s.top(); // 맨 위 요소 반환 (제거하지 않음) -
스택 상태 확인:
size_t size = s.size(); // 스택의 현재 크기 반환 bool is_empty = s.empty(); // 스택이 비어있는지 확인
3. ⚡ stack의 내부 작동 및 성능
📊 기본 컨테이너 선택
- std::deque (기본값):
- 양쪽 끝에서 O(1) 시간에 삽입/삭제가 가능하다.
- 메모리 블록이 분산되어 있어 큰 데이터에 적합하다.
- 중간 접근이 필요한 경우 비효율적이다.
- std::vector:
- 끝에서 O(1) 시간에 삽입/삭제가 가능하다 (재할당 제외).
- 연속된 메모리 공간으로 캐시 효율성이 좋다.
- 재할당 시 O(n) 시간이 소요된다.
- std::list:
- 양쪽 끝에서 O(1) 시간에 삽입/삭제가 가능하다.
- 메모리 오버헤드가 크다.
- 중간 삽입/삭제가 필요한 경우에 유용하다.
🚀 성능 고려사항
- 기본 컨테이너 선택 기준:
- 대부분의 경우 기본
std::deque가 최적의 선택이다. - 메모리 효율성이 중요하면
std::vector를 고려한다. - 중간 삽입/삭제가 필요한 경우
std::list를 고려한다.
- 대부분의 경우 기본
4. 🛠️ stack의 주요 멤버 함수
| 함수 | 설명 | 시간 복잡도 |
|---|---|---|
empty() |
스택이 비어있는지 확인 | O(1) |
size() |
스택의 현재 크기 반환 | O(1) |
top() |
맨 위 요소 반환 | O(1) |
push(val) |
맨 위에 요소 추가 | O(1) |
emplace(args) |
맨 위에 요소를 직접 생성하여 추가 | O(1) |
pop() |
맨 위 요소 제거 | O(1) |
swap(other) |
다른 스택과 내용을 맞바꿈 | O(1) |
5. 🔄 스택 구현 예시
📝 기본적인 stack 사용 예시
#include <iostream>
#include <stack>
#include <string>
int main() {
// 스택 선언 및 초기화
std::stack<std::string> s;
// 요소 추가
s.push("First"); // 맨 위에 "First" 추가
s.push("Second"); // 맨 위에 "Second" 추가
s.push("Third"); // 맨 위에 "Third" 추가
// 스택 순회 (비어있을 때까지)
std::cout << "스택 내용 (LIFO 순서):\n";
while (!s.empty()) {
std::cout << s.top() << "\n"; // 맨 위 요소 출력
s.pop(); // 맨 위 요소 제거
}
return 0;
}
🔄 다른 컨테이너를 사용한 스택 예시
#include <iostream>
#include <stack>
#include <vector>
#include <list>
int main() {
// vector 기반 스택
std::stack<int, std::vector<int>> vec_stack;
vec_stack.push(1); // 맨 위에 1 추가
vec_stack.push(2); // 맨 위에 2 추가
vec_stack.push(3); // 맨 위에 3 추가
// list 기반 스택
std::stack<int, std::list<int>> list_stack;
list_stack.push(4); // 맨 위에 4 추가
list_stack.push(5); // 맨 위에 5 추가
list_stack.push(6); // 맨 위에 6 추가
// 각 스택의 내용 출력
std::cout << "Vector 기반 스택:\n";
while (!vec_stack.empty()) {
std::cout << vec_stack.top() << " "; // 맨 위 요소 출력
vec_stack.pop(); // 맨 위 요소 제거
}
std::cout << "\n";
std::cout << "List 기반 스택:\n";
while (!list_stack.empty()) {
std::cout << list_stack.top() << " "; // 맨 위 요소 출력
list_stack.pop(); // 맨 위 요소 제거
}
std::cout << "\n";
return 0;
}
6. ⚠️ 주의사항 및 팁
🚨 빈 스택 접근
top()이나pop()을 빈 스택에 호출하면 정의되지 않은 동작이 발생한다.- 항상
empty()로 확인 후 접근해야 한다.
🔄 반복자 사용 불가
- 스택은 반복자를 제공하지 않는다.
- 모든 요소에 접근하려면
pop()을 사용하여 순차적으로 제거해야 한다.
🧹 메모리 관리
- 스택은 기본 컨테이너의 메모리 관리 방식을 따른다.
std::vector를 사용할 경우 재할당을 주의해야 한다.std::list를 사용할 경우 메모리 오버헤드를 고려해야 한다.
7. 💡 실제 활용 예시
📝 괄호 짝 맞추기
#include <iostream>
#include <stack>
#include <string>
bool isBalanced(const std::string& str) {
std::stack<char> s;
for (char c : str) {
if (c == '(' || c == '[' || c == '{') {
s.push(c); // 여는 괄호는 스택에 추가
} else if (c == ')' || c == ']' || c == '}') {
if (s.empty()) return false; // 닫는 괄호가 있는데 스택이 비어있음
char top = s.top(); // 스택의 맨 위 괄호 확인
s.pop(); // 맨 위 괄호 제거
// 괄호 쌍이 맞는지 확인
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return s.empty(); // 모든 괄호가 짝이 맞았는지 확인
}
int main() {
std::string test = "{[()]}";
std::cout << (isBalanced(test) ? "균형잡힌 괄호" : "균형잡히지 않은 괄호") << std::endl;
return 0;
}
🔄 후위 표기법 계산기
#include <iostream>
#include <stack>
#include <string>
#include <sstream>
int evaluatePostfix(const std::string& expr) {
std::stack<int> s;
std::istringstream iss(expr);
std::string token;
while (iss >> token) {
if (isdigit(token[0])) {
s.push(std::stoi(token)); // 숫자는 스택에 추가
} else {
int b = s.top(); s.pop(); // 두 번째 피연산자
int a = s.top(); s.pop(); // 첫 번째 피연산자
// 연산 수행 후 결과를 스택에 추가
switch (token[0]) {
case '+': s.push(a + b); break;
case '-': s.push(a - b); break;
case '*': s.push(a * b); break;
case '/': s.push(a / b); break;
}
}
}
return s.top(); // 최종 결과 반환
}
int main() {
std::string expr = "3 4 + 2 *"; // (3 + 4) * 2
std::cout << "결과: " << evaluatePostfix(expr) << std::endl;
return 0;
}
8. 🎯 면접 대비 핵심 개념
📝 기본 개념 및 특징
Q1. std::stack이란 무엇인가요? 어떤 자료구조를 기반으로 하나요?
A. std::stack은 LIFO(Last In First Out) 원칙을 따르는 컨테이너 어댑터입니다.
- 주요 특징:
- LIFO 구조 (후입선출)
- 컨테이너 어댑터 (실제 컨테이너를 감싸는 래퍼)
- 기본적으로
std::deque기반 - 제한된 인터페이스 (top, push, pop)
- 기반 컨테이너:
- 기본:
std::deque - 대안:
std::vector,std::list - 요구사항:
back(),push_back(),pop_back()지원
- 기본:
💡 주요 멤버 함수 및 사용법
Q2. push()와 emplace()의 차이점은 무엇인가요?
A. 두 함수는 요소 추가 방식이 다릅니다.
push():- 객체를 생성한 후 스택에 복사/이동
- 복사 연산의 경우:
stack.push(MyClass(1, 2)); // 1. 임시 객체 생성 // 2. 복사 생성자로 스택에 추가 (깊은 복사) // 3. 임시 객체 파괴 (원본 데이터 유지) - 이동 연산의 경우:
stack.push(std::move(obj)); // 1. 임시 객체 생성 // 2. 이동 생성자로 스택에 추가 (리소스 이동) // 3. 임시 객체 파괴 (이동된 객체는 유효하지만 비어있음)
emplace():- 스택 내부에서 직접 객체 생성
- 생성자 인자만 전달하여 내부에서 직접 생성
- 임시 객체 생성/파괴 과정 없음
- 예시:
stack.emplace(1, 2); // 생성자 인자만 전달하여 스택 내부에서 직접 생성
Q3. 스택의 반복자가 없는 이유는 무엇인가요?
A. 스택의 LIFO 특성 때문입니다.
- 설계 의도:
- LIFO 구조는 맨 위 요소만 접근 가능
- 중간 요소 접근은 스택의 본질적인 특성 위배
- 반복자 제공 시 스택의 추상화가 깨질 수 있음
🔧 메모리 관리 및 성능
Q4. 스택의 기본 컨테이너로 std::deque를 선택한 이유는 무엇인가요?
A. std::deque가 스택 연산에 최적화되어 있기 때문입니다.
- 장점:
- 양쪽 끝에서 O(1) 시간에 삽입/삭제
- 재할당 없이 크기 조절 가능
- 메모리 블록이 분산되어 있어 큰 데이터 처리에 적합
- 다른 컨테이너와 비교:
vector: 재할당 시 O(n) 시간 소요list: 메모리 오버헤드가 큼
⚡ 성능 및 최적화
Q5. 스택의 성능을 최적화하는 방법은 무엇인가요?
A. 사용 사례에 따라 여러 방법이 있습니다.
- 컨테이너 선택:
- 작은 데이터:
std::vector(캐시 효율성) - 큰 데이터:
std::deque(재할당 없음) - 중간 삽입/삭제:
std::list(포인터 조작)
- 작은 데이터:
- 메모리 관리:
vector사용 시reserve()로 미리 공간 확보- 불필요한 복사/이동 연산 피하기
emplace()사용으로 임시 객체 생성 방지
📊 실제 활용
Q6. 스택의 일반적인 사용 사례는 무엇인가요?
A. 여러 알고리즘과 문제 해결에 활용됩니다.
- 일반적인 사용 사례:
- 괄호 짝 맞추기
- 후위 표기법 계산
- 깊이 우선 탐색(DFS)
- 함수 호출 스택 구현
- 실행 취소(Undo) 기능
Q7. 스택을 사용한 알고리즘의 시간 복잡도는 어떻게 되나요?
A. 기본 연산의 시간 복잡도는 다음과 같습니다.
- 기본 연산:
push(): O(1)pop(): O(1)top(): O(1)empty(): O(1)size(): O(1)
- 전체 알고리즘:
- n개 요소 처리: O(n)
- 각 요소당 상수 시간 연산
🎯 추가 면접 팁
- 스택 vs 큐:
- 스택: LIFO (Last In First Out)
- 큐: FIFO (First In First Out)
- 스택 구현 방법:
- 배열 기반
- 연결 리스트 기반
- STL 컨테이너 기반
- 자주 사용되는 패턴:
- 두 개의 스택으로 큐 구현
- 스택으로 재귀 함수 비재귀적 구현
- 스택으로 트리 순회 구현