[C++] stack 클래스 정리
🦥 stack?
▶ LIFO (Last In First Out) 구조의 Container Adapter
1) Last In First Out (후입 선출)
한 쪽(top)에서만 자료를 넣고 뺄 수 있는 구조이다. ‘stack’이라는 단어를 사전에 찾아보면 ‘쌓다’라는 뜻이 나온다. stack에 대해 쉽게 이해하기 위해, 접시 여러 개를 ‘쌓아’ 올린다고 생각해보자. 여기에 새로운 접시를 추가한다고 할 때, 우리는 그 접시를 맨 위에 얹을 것이고, 뺄 때에도 역시 맨 위의 접시부터 빼게 된다. 이렇게 마지막(Last)에 넣은(In) 것을 처음(First)으로 빼는(out) 구조를 stack이라고 한다.
2) Container Adapter
template<
class T,
class Container = std::deque<T>
> class stack;
stack은 container가 아니라 container adapter이다.
즉, 기존의 container(vector, list, deque)를 기반으로 구현된 구조로, 해당 container가 가지고 있는 일부 member function을 활용할 수 있다. 위의 정의에서 볼 수 있듯이 default container는 deque이기 때문에 따로 명시하지 않고 stack<int> s로 선언하게 되면, deque를 기반으로 한 stack이 생성된다.
✅ 이 포스트는 C++ STL에서의 stack에 대한 글입니다. stack 자료구조의 특징, 장/단점, 시간 복잡도에 대해서 더 알아보려면 ▶ [자료구조] 스택(Stack), 큐(Queue), 덱(Deque)
🦥 stack의 생성자와 초기화
stack 헤더 추가
#include <stack>
1) 비어있는 stack s 생성
stack<int> s1;
2) {1, 2, 3, 4, 5}로 초기화 된 stack 생성
// s2.top()하면 5 나옴.
stack<int> s2({ 1, 2, 3, 4, 5 });
3) container(deque, list, vector)를 복사하여 stack을 생성
deque<int> d1(5, 10);
stack<int> s3(d1);
4) stack의 기반 container를 명시하여 생성
First parameter : Type of the stored elements
Second parameter : Type of the underlying container to use to store the elements
// vector를 container로 하는 stack 생성
stack <int, vector<int>> s4;
// deque를 container로 하는 stack 생성 (stack<int> s5와 동일)
stack <int, deque<int>> s5;
🦥 stack의 함수들
🌴 Iterator
사용 안함. stack의 목적이 iterator를 필요로 하지 않기 때문
🌴 Fuction
s.empty(): stack이 비어있는지 확인 / 시간 복잡도 : O(1)s.size(): stack의 원소 수를 반환 / 시간 복잡도 : O(1)s.top(): stack의 맨 위의 원소 리턴 / 시간 복잡도 : O(1)s.push(n): stack의 맨 위에 원소 ‘n’을 추가 / 시간 복잡도 : O(1)s.pop(): stack의 맨 위의 원소 삭제 / 시간 복잡도 : O(1)
실습 코드
#include <iostream>
#include <stack>
using namespace std;
void showAll(stack<int> s) {
while (!s.empty()) {
cout << s.top() << ' ';
s.pop();
}
}
int main()
{
stack <int> s;
s.push(10);
s.push(4);
s.push(5);
s.push(9);
s.push(2);
cout << "Show all elements(up to down) : ";
showAll(s);
cout << "\ns.size() : " << s.size();
cout << "\ns.top() : " << s.top();
s.pop();
cout << "\ns.pop() done\n";
cout << "Show all elements(up to down): ";
showAll(s);
return 0;
}
[실행 결과]
Show all elements(up to down) : 2 9 5 4 10
s.size() : 5
s.top() : 2
s.pop() done
Show all elements(up to down): 9 5 4 10
Reference
Leave a comment