[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 스택(Stack)
- STL stack
- Q&A
- 마치며
1. 스택(Stack)
- 스택(Stack)
: 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조
스택은 구조적으로 제일 먼저 들어간 원소가 제일 나중에 나오게 됨.
FILO(First in Last out) 자료구조.
스택, 큐 ,덱 모두 특정 위치에서만 원소를 넣거나 뺄 수 있음.
그래서 'Restricted Structure'라고 부름.
1) 스택의 성질
(1) 원소의 추가 / 제거 O(1)
(2) 최상단의 원소 확인 O(1)
(3) 최상단이 아닌, 나머지 원소들의 확인 / 변경이 원칙적으로 불가능
2) 스택의 구현
const int MX = 1000005;
int dat[MX];
int pos = 0;dat배열에는 스택 원소들의 값이 들어가고, pos는 다음 원소가 추가될 때 삽입해야하는 곳을 가리키고 있음.
그리고 pos의 값은 곧 스택의 길이, 즉 원소의 개수를 나타냄.
const int MX = 1000005;
int dat[MX];
int pos = 0;
void push(int x){
dat[pos++] = x;
}
void pop(){
pos--;
}
int top(){
return dat[pos-1];
}3) 벡터와 스택
사실 벡터는 스택의 모든 기능을 대체할 수 있음.
(마지막 원소의 추가 / 제거는 push_back(), pop_back(). 또한 []연산자를 통해 임의 위치에 접근 가능.)
하지만 그럼에도 불구하고 스택을 쓰는 경우가 있음.
바로, stack의 연산만을 이용하는 경우.(의미가 더 명확해짐)
하지만 벡터를 사용한다고 하더라도 성능 차이는 거의 없음.
(사실, push, pop, top연산이 정의된 자료구조는 모두 stack이라 부름(vector, string, deque, list). 하지만 c++에서 스택은 std::stack을 의미)
2. STL stack
1) 생성자
1. stack<int> S;1번은 비어있는 스택을 생성합니다.
(스택을 내부적으로 stack의 연산을 지원하는 deque, vector 등을 이용해 구현되며, default값은 deque입니다.)
2) 멤버 함수
stack<int> S;
// S = { 1, 2, 3, 4, 5 }
for(int i = 1; i <= 5; i++) S.push(i);
while(!S.empty()){
cout << S.size() << ' ' << S.top() << '\n';
S.pop();
}(1) push / pop
마지막 위치에 원소를 삽입 / 삭제. O(1)
push는 emplace로 대체 가능.
pop의 반환값은 void이며 마지막 원소가 아님(파이썬 list의 pop()과 다름)
빈 stack에서 둘을 호출하는 것은 'UB(Undefined Behavior)'이며 런타임 에러를 발생시킴.
(2) top
마지막 위치의 원소를 reference로 반환. O(1)
(3) size / empty()
stack의 크기를 size_t 자료형으로 반환.
stack이 비어있는지 여부를 bool 자료형으로 반환.
(4) 참고
std::stack에는 clear라는 멤버 함수가 없음.
따라서 해당 동작을 하고자 하면
while(S.size()){ S.pop() }으로 처리해야 함.
또한 deque와 달리 []연산자, iterator가 없으므로 top()이외의 원소에는 접근할 수 없음.
3. Q&A
-
4. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
