글 읽기 - queue와 stack 차이??

denfor123 2년 전 0

풀이과정 간략히 하면 타잔알고리즘으로 SCC 찾은 후 SCC 간 결합을 scc_adj에 넣었습니다.

그리고 시작점부터 scc_adj 간선들을 지나며 최댓값을 갱신했습니다.

이 때, stack을 이용해 DFS를 진행한 경우 시간초과가 나고 queue를 이용해 BFS를 하니 AC를 받았습니다. 구글링하니 stack과 queue의 성능차이는 크게 나지 않는다고 하는데 어떤 부분에서 차이를 만들어내는지 혹은 제가 어떤 부분을 놓치고 있는 건지 궁금합니다. 감사합니다.

ll findMaxCash(){
    ll res=0;
    //SCC간 간선 연결
    for(int s=1;s<=N;++s)
        for(int d:adj[s])
            if(low[s]!=low[d])
                scc_adj[low[s]].insert(low[d]);
    ll cache[id+1];
    memset(cache, -1, sizeof(cache));
    
    // stack 사용 (시간 초과)
    int start=low[S];
    cache[start]=sccCash[start];
    stack<int> s;
    s.push(start);
    while(!s.empty()){
        int here=s.top();
        s.pop();
        if(haveRest[here]) res=max(res, cache[here]);
        for(int next:scc_adj[here]){
            if(cache[here]+sccCash[next]>cache[next]){
                cache[next]=cache[here]+sccCash[next];
                s.push(next);
            }
        }
    }
    return res;

    // queue 사용 (통과)
    // int start=low[S];
    // cache[start]=sccCash[start];
    // queue<int> q;
    // q.push(start);
    // while(!q.empty()){
    //     int here=q.front();
    //     q.pop();
    //     if(haveRest[here]) res=max(res, cache[here]);
    //     for(int next:scc_adj[here]){
    //         if(cache[here]+sccCash[next]>cache[next]){
    //             cache[next]=cache[here]+sccCash[next];
    //             q.push(next);
    //         }
    //     }
    // }
    // return res;
}

slah007 2년 전 0

단순히 push, pop의 시간복잡도는 차이가 없겠지만 stack과 queue는 원소를 pop 할 때 순서가 서로 반대입니다. stack은 선입후출이고(먼저 넣은 원소가 나중에 나옴) queue는 선입선출(먼저 넣은 순서대로 나옴)입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

queue와 stack 차이??

denfor123 2년 전 0

slah007 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말