[자료구조] 큐 (Queue)

큐 (Queue)

---

큐는 FILO(First In First Out, 선입선출) 구조로 가장 먼저 넣은 데이터가 먼저 나오는 자료구조이다. std::deque기반의 컨테이너 어댑터로 list, vector등 다른 컨테이너로 변경해서 사용하는 것도 가능하다. 삽입과 삭제 연산은 항상 front, back위치에서 이루어지기 때문에 모든 연산의 시간 복잡도는 O(1)이다.

멤버함수	설명
push(const T& value)	큐의 맨 뒤에 데이터 추가
pop()	큐의 맨 앞 요소 제거 (리턴값 없음)
front()	맨 앞 요소 참조 반환
back()	맨 뒤 요소 참조 반환
empty()	큐가 비었는지 확인
size()	큐 크기 확인
emplace(args...)	새 요소를 생성 후 큐의 맨 뒤에 삽입 (C++11)

 

 

큐 기본 코드

#include <iostream>
#include <queue>

int main() {
    // queue 생성
    std::queue<int> q;

    // push
    q.push(10);
    q.push(20);
    q.push(30);

    std::cout << "Front element: " << q.front() << std::endl; // 10
    std::cout << "Back element: " << q.back() << std::endl;   // 30

    // pop
    q.pop();
    std::cout << "Front element after pop: " << q.front() << std::endl; // 20

    // size & empty
    std::cout << "Queue size: " << q.size() << std::endl; // 2
    std::cout << "Is empty? " << (q.empty() ? "Yes" : "No") << std::endl;

    return 0;
}

 

 

 deque를 기반으로 한 큐 구조 (컨테이너 어댑터)

template <class T, class Container = std::deque<T>>
class queue {
protected:
    Container c; // queue는 내부 컨테이너에 위임해서 데이터를 관리한다.

public:
    void push(const T& value) { c.push_back(value); }
    void pop() { c.pop_front(); }
    T& front() { return c.front(); }
    T& back() { return c.back(); }
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
};

 

 

다른 컨테이너로 Queue를 사용하려면? 

queue생성시에 템플릿 두번째 인자로 원하는 컨테이너를 넘겨주면 된다.

#include <iostream>
#include <queue>
#include <list>
#include <deque>

int main() {
    std::queue<int> q1;                       // 기본 deque 기반
    std::queue<int, std::list<int>> q2;       // list 기반

    q2.push(1);
    q2.push(2);
    std::cout << q2.front() << std::endl;     // 1
    std::cout << q2.back() << std::endl;      // 2
}

 

 

큐의 활용 사례

• 프로세스 관리 (운영체제의 작업 스케줄링: 먼저 들어온 작업이 먼저 처리됨)
• 버퍼(Queue Buffer) (네트워크 데이터 처리, IO 처리)
• BFS (너비 우선 탐색) 알고리즘 구현
• 프린터 대기열 같은 순차적 작업 처리

 

 

큐의 종류

1. 큐 (Queue)
   • FIFO 자료구조로 기본 큐이다.
   • std::queue
2. 원형 큐 (Circular Queue / Ring Buffer)
   • 고정 크기 배열을 원처럼 순환시켜 사용하는 큐로 인덱스가 배열 끝에 도달하면 다시 앞(0)으로 돌아간다. 고정 배열로 연속된 메모리 공간에 할당되어 캐시 친화적이다.
   • STL 제공 x
3. 우선순위 큐 (Priority Queue)
   • 단순 FIFO가 아닌, 우선순위가 높은 요소가 먼저 나오는 큐 이다. 오름차순/ 내림차순을 지정하여 우선순위를 지정할 수도 있다. 내부적으로는 보통 힙(Heap) 자료구조로 구현된다.
   • std::priority_queue
4. 이중 큐 (Deque, Dourble-ended Queue)
   • 양쪽 끝에서 push, pop이 가능한 큐로 큐와 스택의 특성을 동시에 가진다. (push_front, push_back, pop_front, pop_back)
   • std::deque
5. 이중 우선순위 큐 (Double-ended Priority Queue)
   • 최소값과 최대값을 모두 빠르게 꺼낼 수 있는 큐로 양쪽에서 우선순위를 관리할 수 있다.
   • STL 제공 x
6. 동시성 큐 (Concurrent Queue/ Lock-free Queue)
   • 멀티스테드 환경에서 동시에 여러 스레드가 안전하게 접근할 수 있는 큐이다. 일반적인 큐는 하나의 스레드만 안전하게 사용 가능한데, 멀티 스레드 환경에서 push나 pop을 하면 데이터가 깨지거나 잘못된 값이 나올 수 있다. 동시성 큐는 락(lock)이나 CAS(Compoare-And-Swap)연산을 통해 이 문제를 해결한다.
   • STL 제공 x
7. 이중 연결 큐 (Input=restricted/ Output-restricted Deque)
   • Deque의 변경 자료구조로 입력은 한쪽 끝에서만, 출력은 양쪽에서 가능하게 하는 Input-restricted deque와 출력을 한쪽 끝에서만, 입력은 양쪽에서 가능하게 하는 Output-restricted deque가 있다.
   • STL 제공 x

 

 

---

wooj22 - Overview

양우정