[기초] 자료구조 / 스택(stack)

 

 

스택(stack)

 

 

한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조

 

마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out (LIFO) 라고도 합니다.

 

 

출처 : 위키피디아

 

- push : 스택에 자료를 넣는 연산

- pop : 스택에서 자료를 빼는 연산

- top : 스택의 가장 위에 있는 자료를 보는 연산

- empty : 스택이 비어있는지 아닌지를 알아보는 연산

- size : 스택에 저장되어있는 자료의 개수를 알아보는 연산

 

 

그림에서 top은 6이고 4가 push 되면 top은 4가 됩니다.

빨간색 숫자가 자료가 들어온 순서를 나타냅니다.

 

 

 

스택은  이미 구현된 라이브러리를 사용할 수있습니다.

 

C++의 경우 STL의 stack

JAVA의 경우 java.util.Stack

 

 

 

직접 구현할 경우 배열을 이용해서 구현할 수 있고 size변수를 설정하여

push 하면 스택의 size 변수 인덱스에 값을 넣어주고 size변수에 +1 해줍니다.

pop 하면 스택의 (size 변수 -1) 인덱스에 값을 0으로 만들어 주고, size변수에 -1 해줍니다.

 

 

---

 

스택을 이용한 백준 괄호 문자열 문제입니다.

 

문자열을 입력받아 괄호 모양이 바르게 구성된 문자열(VPS) 여부를 판단합니다.

 

https://www.acmicpc.net/problem/9012

9012번: 괄호

 

 

stack 자료구조를 사용하였고, 경우를 나눠서 풀이하였습니다.

 

 

 

- 풀이내용 -

 

 

1. '('이면 무조건 stack에 push

 

2. ')'이면 스택이 비어있을경우 push / 스택이 비어있지 않고 top이 '('인 경우에만 pop

(그냥 pop을 해주면 입력값이 '))' 이런 경우에 예외발생)

 

3. 입력값의 길이만큼 반복을 하고 empty를 통해 stack이 비어있음을 확인하면 VPS로 판단

 

#include<iostream>
#include<stack>

using namespace std;

void checkVPS(string p){
    stack<char> checkP;
    for(int i = 0; i < p.size(); i++){
        if(p[i]=='('){
            checkP.push('(');
        }
        else{
            if(checkP.empty()){
                checkP.push(')');
            }
            else if(checkP.top() == '('){
                checkP.pop();
            }
        }
    }
    if(checkP.empty()){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}

int main(){
    string par;
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> par;
        checkVPS(par);
    }
    return 0;
}

 

 

---

백준 에디터 문제입니다.

 

문자열을 출력하는 에디터를 규칙에 맞게 만들어야 합니다.

 

https://www.acmicpc.net/problem/1406

1406번: 에디터