Stack, deque, queue 관련 질문

지성

작성한 질문수 12

0

안녕하세요 지성님 ㅎㅎ

먼저 좋은 의견이라는 생각이 됩니다.

 

deque 같은 경우에는 stack과 queue 모두의 장점을 가지고 있고, 따로 시간적으로 더 복잡하거나 하지도 않는 것으로 이해하고 있는데, 그럼 deque만 사용하는게 더 좋은걸까요?

-> 음.. 한번 성능테스트를 해볼까요?

 

#include <bits/stdc++.h>
using namespace std;

const int N = 10000000;

long long test_stack() {
    stack<int> s;
    long long sum = 0;
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < N; i++) {
        s.push(i);
    }
    while (!s.empty()) {
        sum += s.top();
        s.pop();
    }
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    cout << "std::stack : " << duration << " ms, sum = " << sum << "\n";
    return duration;
}

long long test_queue() {
    queue<int> q;
    long long sum = 0;
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < N; i++) {
        q.push(i);
    }
    while (!q.empty()) {
        sum += q.front();
        q.pop();
    }
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    cout << "std::queue : " << duration << " ms, sum = " << sum << "\n";
    return duration;
}

long long test_deque_as_stack() {
    deque<int> d;
    long long sum = 0;
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < N; i++) {
        d.push_back(i);
    }
    while (!d.empty()) {
        sum += d.back();
        d.pop_back();
    }
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    cout << "std::deque (stack처럼) : " << duration << " ms, sum = " << sum << "\n";
    return duration;
}

long long test_deque_as_queue() {
    deque<int> d;
    long long sum = 0;
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < N; i++) {
        d.push_back(i);
    }
    while (!d.empty()) {
        sum += d.front();
        d.pop_front();
    }
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    cout << "std::deque (queue처럼) : " << duration << " ms, sum = " << sum << "\n";
    return duration;
}

int main() {
    cout << "C++ 컨테이너 성능 분석 (push/pop 연산)\n";
    cout << "테스트 원소 개수 N = " << N << "\n";
    long long t_stack = test_stack();
    long long t_queue = test_queue();
    long long t_dequeStack = test_deque_as_stack();
    long long t_dequeQueue = test_deque_as_queue();
    cout << "\n[성능 요약]\n";
    cout << "std::stack            : " << t_stack << " ms\n";
    cout << "std::queue            : " << t_queue << " ms\n";
    cout << "std::deque (stack형)  : " << t_dequeStack << " ms\n";
    cout << "std::deque (queue형)  : " << t_dequeQueue << " ms\n";
    return 0;
}

테스트 결과는 다음과 같습니다.

 

성능상 deque가 조금 더 좋은 것을 볼 수 있어서 stack, queue대신에 deque를 사용하셔도 될 것 같습니다.

 

그럼 deque만 사용하는게 더 좋은걸까요?

-> 앞의 코드처럼 간단한 테스트기반으로는 deque가 더 좋으니 deque만을 사용하는게 좋을 것 같아보이지만, 문제마다 다른 경우의 수도 있을 것 같아 무조건 deque만을 쓴다는 확답을 드리기에는 어렵습니다.

 

 

---

 

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

안녕하세요, 인프런 AI 인턴입니다. 지성님!

deque는 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, stack과 queue의 기능을 모두 구현할 수 있습니다. 그러나, stack과 queue가 각각의 역할을 명확히 하기 때문에 모든 경우에 deque를 사용하기보다 특정 상황에 맞는 자료구조를 선택하는 것이 중요합니다.

1. stack을 사용할 때:

   • LIFO(Last In, First Out) 구조가 필요할 때 주로 사용합니다. 예를 들어, 함수 호출의 활성 레코드를 관리하거나 괄호 검사기(균형 확인) 같은 특정 문제에 효과적입니다.
     

2. queue를 사용할 때:

   • FIFO(First In, First Out) 구조가 필요할 때 사용합니다. 작업 스케줄링(큐에 들어온 순서대로 처리)이나 너비 우선 탐색(BFS)와 같은 알고리즘에서 유용합니다.
     

deque는 이 두 가지 구조의 기능을 제공하면서 유연성을 artır지만, 코드의 가독성과 명확성 측면에서 stack과 queue를 구분해서 사용하는 것이 코드를 더 쉽게 이해하도록 도울 수 있습니다.

관련 질문 및 내용으로 추가적인 참고를 원하신다면 다음 유사한 게시물을 확인해보세요:
- “2-T 질문있습니다!”: deque와 관련된 stack 및 queue 활용에 관한 또 다른 질의응답을 확인하실 수 있습니다.

참고하시면서 추가적으로 궁금한 점이 있으시다면, 언제든 추가 질문 주시면 감사하겠습니다. 곧 지식공유자께서 더 상세한 답변을 제공할 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.