먼저들어간 원소가 가장 나중에 나오게되는 자료구조이다.
후입선출. LIFO(Last In, First Out) 구조를 가지고있다.
스택의 성질 :
- 원소의 추가 O(1).
- 원소의 제거 O(1).
- 제일 상단의 원소 확인이 O(1).
- LIFO 구조 : 마지막에 추가된 요소가 가장 먼저 제거됩니다.
- 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능.
스택의 주요 멤버 함수 :
- push(value) : 스택의 top에 요소(value)를 추가합니다.
- pop() : 스택의 맨 위 요소를 제거합니다. 이 함수는 요소를 반환하지 않으며, 단순히 제거합니다.
- top() : 스택의 맨 위 요소를 반환합니다. 요소를 제거하지는 않습니다.
- empty() : 스택이 비어 있는지를 확인합니다. 비어있으면 true 그렇지않으면 false를 반환합니다.
- size() 스택에 있는 요소의 개수를 반환합니다.
주의 할 점 :
- stack은 비어 있을 때 top()이나 pop()을 호출하면 정의되지 않은 동작(Undefined Behavior)이 발생합니다. 즉, 프로그램이 비정상적으로 종료되거나 예상치 못한 결과가 나타날 수 있습니다.
- 때문에 empty()를 사용하여 예외처리를 해주는 것이 중요합니다.
사용 예 :
- 함수 호출 스택 : 프로그램에서 함수 호출을 관리하기 위해 사용됩니다. 함수가 호출될 때마다 호출된 함수의 정보가 스택에 쌓이고, 함수가 종료되면 스택에서 제거 됩니다.
- 괄호 검사 : 문자열에서 괄호가 올바르게 열리고 닫히는지를 검사할 때 사용됩니다.
- 그래프 탐색 : DFS 알고리즘에서 재귀를 사용하지 않고 스택을 이용하여 그래프를 탐색할 수 있습니다.
스택의 선언 및 초기화 :
- 기본적인 std::stack 선언 및 초기화 :
#include <iostream>
#include <stack>
int main() {
// int 타입의 스택 선언
std::stack<int> s;
// 스택에 요소 추가
s.push(10);
s.push(20);
s.push(30);
// 스택의 맨 위 요소 출력
std::cout << "Top element: " << s.top() << std::endl; // 출력: 30
return 0;
}
2. 초기값을 가지는 선언 및 초기화
std::stack은 자체적으로 초기값을 설정할 수는 없지만, 다른 컨테이너를 초기화하여 이를 기반으로 std::stack을 초기화 할 수 있습니다.
#include <iostream>
#include <stack>
#include <vector>
int main() {
// 초기값을 가진 vector를 이용해 stack 초기화
std::vector<int> vec = {10, 20, 30};
std::stack<int, std::vector<int>> s(vec);
// 스택의 맨 위 요소 출력
std::cout << "Top element: " << s.top() << std::endl; // 출력: 30
return 0;
}