std::queue

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

std::queue

• STL에서 제공하는 큐 컨테이너 어댑터이다.
• 기본적으로 std::deque가 컨테이너로 사용된다.
• 선입선출(FIFO) 구조를 갖는다.
• 순회할 필요가 없으므로 반복자를 제공하지 않는다.
• Front와 Rear에서 원소에 접근할 수 있다.

 

std::queue의 성능

• 모든 연산은 O(1) 시간에 수행된다.

 

#include <iostream>
#include <queue>

using namespace std;

void main()
{
    queue<int> que;

    // 1, 2, 3 Push
    que.emplace(1);
    que.emplace(2);
    que.emplace(3);
    
    // Pop
    que.pop();

    cout << "Front: " << que.front() << endl;

    cout << "Rear: " << que.back() << endl;

    cout << "Empty: " << boolalpha << que.empty() << endl;

    cout << "크기: " << que.size() << endl;
}

 

출력

Front: 2
Rear: 3
Empty: false
크기: 2

 

반복자를 이용한 순회가 필요한 경우 std::deque, std::list 중 하나를 큐로 사용해도 된다.

 

#include <iostream>
#include <deque>

using namespace std;

ostream& operator<<(ostream& os, deque<int> deq)
{
    for (int e : deq)
        os << e << ' ';

    return os;
}

void main()
{
    deque<int> que;

    // 1, 2, 3 Push
    que.emplace_back(1);
    que.emplace_back(2);
    que.emplace_back(3);

    // Pop
    que.pop_front();

    cout << que << endl;

    cout << "Front: " << que.front() << endl;

    cout << "Rear: " << que.back() << endl;

    cout << "Empty: " << boolalpha << que.empty() << endl;

    cout << "크기: " << que.size() << endl;
}

 

출력

2 3
Front: 2
Rear: 3
Empty: false
크기: 2