Stack, 스택 , 자료구조 [CPP]

 

이번엔 스택을 알아보자

 

스택은 First In Last Out으로 

삽입과 삭제 연산이 동일한 장소에서 일어나는 자료구조다.

역시 삽입, 삭제 연산에 있어서 상수 시간복잡도를 가진다.

 

FILO구조는 다시 말하면 LIFO구조다. 마지막에 들어온 것이 먼저 나온다는 이야기다.

데이터를 역으로 추적할 때와 같은 상황에 사용한다.

 

---

 

 

연결리스트와 유사한 자료구조라고도 한다. (연결리스트로 스택 구현가능)

스택 같은 경우에는

중위-후위 변환

재귀함수와 같은 함수 호출 구현

**웹브라우저의 뒤로가기 (페이지기록)

문서 어플리케이션,에디터의 Ctrl + z , undo 기능등과 같은 곳에 쓰인다.

 

---

 

스택은 배열, 동적배열(Vector), 연결리스트로 구현이 가능하다.

 

---

 

 

push(), pop()이 같은 장소에서 일어나고

queue와는 다르게 top()만이 값을 반환한다.

size()로 크기를 알 수 있고

empty()로 비어있는지를 알 수 있다.

 

 

---

 

문제를 보자

www.acmicpc.net/problem/10773

 

0을 감지하면

가장 최근에 쓰인 데이터를 지운다.

삭제 연산이 일어나는데

가장 마지막에 삽입이 일어난 장소에서 삭제연산이 일어나는 것이다.

즉, 삽입과 삭제가 같은 장소에서 일어난다.

-> 스택을 떠올렸으면 좋다.

 

#include <iostream>
#include <stack>

int main(){
	//변수
    int num;
    int sum;
    
    sum = 0;
    std::stack<int> stk;
    std::cin >> num;
    
    //스택에 집어넣기
    for(int i=0; i<num; i++){
        int N;
        std::cin>> N;
        if(N == 0){
          stk.pop();
        }else{
          stk.push(N);
        }
    }
    // 현 스택의 사이즈저장
    int size = stk.size();
    
    //직접 스택의 사이즈 메서드로 할당하면 런타임중 바뀌기 때문에 결과 제대로 안나옴
    for (int i = 0; i<size; i++){
        sum += stk.top();
        stk.pop();
    }
    
    std::cout<< sum;
}

 

---

다른 문제도 보자

www.acmicpc.net/problem/9012

즉, 제대로 괄호가 안 닫히면 VPS가 아니란 말이다.

여는 괄호와 닫는 괄호가 서로 만나서 사라지고 그래도 괄호가 남는다면 VPS가 아니란 말이다.

즉, 괄호를 순서대로 넣는 과정에서 닫는 괄호가 나올 경우 가장 최근에 넣은 열린 괄호를 삭제한다.

**최근에 넣은 것(가장 마지막에 삽입한 것)이 열린 괄호라는 것이 보장되어 있는 이유

-> 닫힌 괄호가 나오면 무조건 위의 내용을 실행할 것이기 때문에 닫힌 괄호는 스택에 들어갈 수 없다.

 

이것 또한 마지막에 삽입한 것에서 삭제가 일어나야만 한다.

간단하기 때문에 스택으로 풀지 않는 방법도 있지만

스택으로도 풀어보자

 

** ios_base::sync_with_stdio(false);  cin.tie(0);

는 연산속도를 높이기 위해 입력한다.

jaimemin.tistory.com/1521

 

스택아닌 방법

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
	//변수들
    int N;
    cin >> N;

    for(int i = 0; i < N; i++) {
    	//입력된 문자열
        string str;
        cin >> str;
        int cnt = 0;
        
        
        for(char c: str) {
            if(c == '(')
            	cnt++;
            else if(c == ')' && cnt)
            	cnt--;
            else {
                cnt = -999;
                break;
            }
        }
        
        
        if(cnt == 0)
        	cout << "YES\n";
        else
        	cout << "NO\n";
    }
}

 

 

스택으로 푸는 방법

#include <iostream>
#include <stack>


int main() {
    
    int N;
    
    std::cin >> N;

    for(int i = 0; i < N; i++) {
    //for문 돌 때마다 bool, stack, str 초기화시켜줘야한다.
        std::stack<char> stk;
        bool check = true;
        std::string str;
        std::cin >> str;
        int len = (int)str.length();
        for(int i = 0; i<len; i++) {
            char c = str[i];
            if(c == '('){
                stk.push(c);
            }else{
                if(!stk.empty()){
                    stk.pop();
                }else{
                    check = false;
                    break;
                }
            }
        }
        if(!stk.empty()){
            check = false;
        }
        if(check){
           std::cout << "YES\n";
        }
        else{
           std::cout << "NO\n";
        }
    }
}

 

 

---

참고링크

 

github.com/VSFe/Algorithm_Study