[C++] STL 자료구조: stack
vector와 string은 동적 배열로 임의 위치의 접근, 수정과 마지막 위치의 삽입, 삭제가 O(1)이고,
임의 위치의 삽입, 삭제가 O(n)이라는 특징을 가지고 있어서 연속적인 정보를 저장하는데 적합하다.
stack은 두 자료구조처럼 임의 위치의 접근, 수정을 제공하지 않으며, 마지막 위치의 접근, 삽입, 삭제에만 특화된 자료형이다.
따라서 stack은 원소들을 순서대로 집어넣거나 가장 최근에 들어온 원소를 확인할 때 주로 사용된다.
원소들은 삽입된 순서대로 가장 먼저 삽입된 원소가 맨 위에 오도록 저장되어있으며, 항상 가장 마지막에 삽입된 원소부터 접근할 수 있다. (프링글스를 뒤집어서 아래부터 감자칩을 넣는다고 생각하면 된다)이러한 특성을 LIFO(Last In First Out)이라고 한다.
vector에서 기능이 제한된건데 왜 쓸까?
stack의 연산만을 이용하는 경우에는 vector 대신 stack을 이용하는 게 의미가 더 명확할 수 있다.
하지만 stack 대신 vector를 사용해도 성능 차이는 거의 없으며 기능 또한 더 다양하게 사용할 수 있기 때문에 문제에 맞게 이용하면 된다.
생성자
stack<int> S;
함수
- push : 마지막 위치에 원소를 삽입. O(1)
- pop : 마지막 위치의 원소를 삭제. O(1)
- top : 마지막 위치의 원소를 reference로 반환. O(1)
- size : stack의 크기를 size_t 자료형으로 반환.
- empty : stack이 비어있는지 여부를 bool 자료형으로 반환.
백준>>
9012)
==>내코드:
int main(){
fastio;
int T;
cin>>T;
cin.ignore();
while(T--){
string s;
getline(cin,s);
stack<char> stck;
for(int i=0; i<s.length();i++){
if(s[i]=='(') {stck.push('(');}
else if(s[i]==')') {stck.pop();}
}
if(!stck.empty() || stck.top()=='(') {cout<<"NO"<<'\n';}
else {cout<<"YES"<<'\n';}
}
}
==> 수정
if(!stck.empty() || stck.top()=='(') {cout<<"NO"<<'\n';}
// stck.top()에서 스택이 비어있는 경우를 처리하지 않아 런타임 오류 발생
int main(){
fastio;
int T;
cin>>T;
cin.ignore();
while(T--){
string s;
getline(cin,s);
stack<char> stck;
bool flag = false; // bool 변수 사용
for(int i=0; i<s.length();i++){
if(s[i]=='(') {stck.push('(');}
else if(s[i]==')') {
if(stck.empty()) {
flag = true;
break;
}
stck.pop();
}
}
if(!stck.empty()) {flag = true;} // 스택이 비어있지 않으면 flag를 true로 설정
cout<<(flag? "NO":"YES")<<'\n';
}
return 0;
}
1873번
int main(){
fastio;
int N;
cin>>N;
stack<int> S;
stringstream out; // 출력 문자열을 버퍼에 저장하고 마지막에 한 번에 출력
for(int i=0, t=0; i<N; i++){
int x; cin>>x;
while(t<x) S.push(++t); out<<"+\n";
if(S.empty() || S.top()!=x)
return !(cout<<"NO"<<'\n'); //cout에 NO출력 + false문 반환(함수 종료)
S.pop(); out<<"-\n";
}
cout<<out.str(); //객체 내용을 문자열로 반환하고 cout에 출력
}
10799번) 쇠막대기
- ')'가 입력되었을 때 레이저가 만들어지거나 / 막대기의 끝과 닿는 2가지 경우이다.
- 레이저는 앞이 (일때 생성되며 막대기는 앞이 )일때 생성된다.
- 레이저가 완성된 후 남아있는 (의 개수가 곧 만들어지는 막대기의 수이다 (stack의 크기)
-얘도 구글링을 통해 풀었다 ㅎ;
int main(){
fastio;
string s;
int ans=0;
cin>>s;
stack<char> st;
for(int i=0; i<s.length();i++){
if(s[i]=='(') {st.push(s[i]);}
else{ // )가 들어갈때
if(s[i-1]=='(') {
st.pop();
ans +=st.size();
// )가 막대의 끝이면 ) 1개만 pop, 따라서 레이저 완성 후 남아있는 (의 개수가 곧 막대의 개수
}
else{ // 전 것이 )일때
st.pop();
ans++; //막대의 끝일 경우 1개만 추가
}
}
}
cout<<ans;
return 0;
}
1406번) 에디터
커서가 왼/오로 이동 + 왼쪽 문자 삭제 / 왼쪽에 문자 추가 등의 4가지 기능이 있다.
처음엔 string s[i]를 써서 추가하고 이동하려고 했는데 stack을 쓰기로 했다. / 또한 string<char, string>을 써서 한 풀이도 있었다.
우선 커서의 위치에 따라 left-stack과 right-stack으로 나눠서 풀어보았다.
int main(){
fastio;
string s; cin>>s;
int n; cin>>n;
cin.ignore();
stack <char> lft;
stack <char> rgt;
for(int i=0; i<s.length();i++){
lft.push(s[i]);
}
while(n--){
string c;
char a; getline(cin,c);
if (c[0]=='L'){
if(!lft.empty()){
a=lft.top();
rgt.push(a);
lft.pop();
}
}
else if (c[0]=='D'){
if(!rgt.empty()){
a=rgt.top();
lft.push(a);
rgt.pop();
}
}
else if (c[0]=='B') {
if(!lft.empty()){
lft.pop();
}
}
else if (c[0]=='P'){
lft.push(c[2]);
}
}
string ans;
while(!lft.empty()) {ans.push_back(lft.top()); lft.pop();}
reverse(ans.begin(), ans.end());
while(!rgt.empty()) {ans.push_back(rgt.top()); rgt.pop();}
cout<<ans<<'\n';
}
내가 풀어본 코드이고 더 간단한 코드는 아래 걸 참고하면 되겠다.
int main() {
fastio;
string s, ans; cin >> s;
stack<char, string> S1(s), S2;
int n; cin >> n;
while (n--) {
char c; cin >> c;
if (c == 'L') { if (S1.empty()) continue; S2.push(S1.top()); S1.pop(); }
else if (c == 'D') { if (S2.empty()) continue; S1.push(S2.top()); S2.pop(); }
else if (c == 'B') { if (S1.empty()) continue; S1.pop(); }
else if (c == 'P') { char x; cin >> x; S1.push(x); }
}
while (S1.size()) ans.push_back(S1.top()), S1.pop();
reverse(ans.begin(), ans.end());
while (S2.size()) ans.push_back(S2.top()), S2.pop();
cout << ans << '\n';
}