스택 기본 문제 풀이

 (0) [BOJ 10828] 스택

문제에 주어진 함수들을 그대로 구현하면 해결할 수 있습니다.

//code by RiKang, weeklyps.com
 
#include <stdio.h>
typedef int node_type;
const int stack_size_max = 1000000;
 
struct DS_stack{
    int stack_size=0;
    node_type arr[stack_size_max];
    
    node_type top(){
        if(stack_size==0) return -1;
        return arr[stack_size-1];
    }
    void push(node_type v){
        arr[stack_size++] = v;
    }
    int pop(){
        int ret = top();
        if(stack_size!=0)
            stack_size--;
        return ret;
    }
    int empty(){
        if(stack_size==0) return 1;
        return 0;
    }
    int size(){
        return stack_size;
    }
};
 
int main() {
    DS_stack st;
    int t;
    scanf("%d",&t);
    
    char a[15];
    while(t--){
        scanf("%s",a);
        if(a[0]=='p' && a[1]=='u'){ // push
            int in;
            scanf("%d",&in);
            st.push(in);
        }
        else if(a[0]=='p'){ // pop
            printf("%d\n",st.pop());
        }
        else if(a[0]=='s'){ // size
            printf("%d\n",st.size());
        }
        else if(a[0]=='e'){ // empty
            printf("%d\n",st.empty());
        }
        else{ // top
            printf("%d\n",st.top());
        }
    }
    return 0;
}

 (1) [BOJ 1874] 스택 수열

 스택 수열에서 pop을 할 때 k라는 숫자가 나오기 위해서는, 스택의 top에 k가 있어야 합니다. 따라서 스택 수열의 다음 숫자가 k라면, top이 k가 될 때까지 push를 해줘야 합니다. 만약 top 에 k를 넣을 수 없다면, NO를 출력합니다. 그런 경우는 k가 이미 스택 안에 있으면서 top이 아닌 경우입니다.

//code by RiKang, weeklyps.com
 
#include <stdio.h>
typedef int node_type;
const int stack_size_max = 1000005;
 
struct DS_stack{
    int stack_size=0;
    node_type arr[stack_size_max];
    
    node_type top(){
        if(stack_size==0) return -1;
        return arr[stack_size-1];
    }
    void push(node_type v){
        arr[stack_size++] = v;
    }
    void pop(){
        if(stack_size!=0)
            stack_size--;
    }
};
 
int m;
char ans[1000005];
 
int main() {
    DS_stack st;
    int n;
    scanf("%d",&n);
    int push_num=0;
    for(int i=1; i<=n; i++){
        int in;
        scanf("%d",&in);
        while(push_num<in){
            st.push(++push_num);
            ans[m++] = '+';
        }
        if(st.top()!=in){
            printf("NO");
            return 0;
        }
        st.pop();
        ans[m++] = '-';
    }
    for(int i=0; i<m; i++)
        printf("%c\n",ans[i]);
    return 0;
}

 (2) [BOJ 9012] 괄호

문자열을 순서대로 보면서 '('가 나오면 push, ')'가 나오면 pop이라고 생각하면 stack과 동일한 문제임을 알 수 있습니다. 더 간단한 방법도 있지만, 여기서는 스택까지 사용하는 방법을 소개하겠습니다.

 

//code by RiKang, weeklyps.com
 
#include <stdio.h>
#include <string.h>
typedef char node_type;
const int stack_size_max = 1000005;
 
struct DS_stack{
    int stack_size=0;
    node_type arr[stack_size_max];
    
    node_type top(){
        if(stack_size==0) return -1;
        return arr[stack_size-1];
    }
    void push(node_type v){
        arr[stack_size++] = v;
    }
    void pop(){
        if(stack_size!=0)
            stack_size--;
    }
};
 
void solve(){
    DS_stack st;
    char a[105];
    bool ans = true;
    
    scanf("%s",a);
    for(int i=0; i<strlen(a); i++){
        if(a[i]=='(') st.push('(');
        else{
            if(st.stack_size==0) ans = false;
            st.pop();
        }
    }
    ans &= st.stack_size==0;
    printf("%s\n",ans?"YES":"NO");
}
 
 
int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}