큐

🔍 큐란?

먼저 들어간 데이터가 먼저 나오는 구조
front에서 꺼내고 back에서 넣는 방식

front << [1][2][3][4] << back

📌 활용 사례

• OS 프로세스 스케줄러
• 네트워크 패킷 처리
• BFS 알고리즘
• 프린터 출력 대기열
• 은행 번호표 시스템 등

---

✨ 배열 기반 큐 (ArrayQueue)

✅ 기본 구현

template<typename T>
class ArrayQueue
{
public:
    ArrayQueue() {}

    void push(const T& value)
    {
        if (_size == _container.size())
        {
            // 동적 크기 증설
            int newSize = max(1, _size * 2);
            vector<T> newData(newSize);

            for (int i = 0; i < _size; i++)
            {
                int index = (_front + i) % _container.size();
                newData[i] = _container[index];
            }

            _container.swap(newData);
            _front = 0;
            _back = _size;
        }

        _container[_back] = value;
        _back = (_back + 1) % _container.size();  // 순환 구조
        _size++;
    }

    void pop()
    {
        _front = (_front + 1) % _container.size();
        _size--;
    }

    T& front() { return _container[_front]; }
    bool empty() { return _size == 0; }
    int size() { return _size; }

private:
    vector<T> _container;
    int _front = 0;
    int _back = 0;
    int _size = 0;
};

---

🧠 동작 원리

• _front: 데이터를 꺼낼 위치
• _back: 데이터를 넣을 위치
• _size: 현재 큐에 들어있는 데이터 수
• % 연산으로 순환 배열 구조 구현

배열 끝에 도달하면 다시 앞으로 돌아가는 순환 큐 구조!

---

✅ 연결 리스트 기반 큐 (ListQueue)

template<typename T>
class ListQueue
{
public:
    void push(const T& value)         { _container.push_back(value); }
    void pop()                        { _container.pop_front(); }
    T& front()                        { return _container.front(); }
    bool empty()                      { return _container.empty(); }
    int size()                        { return _container.size(); }

private:
    list<T> _container;
};

📌 리스트 기반 큐는 배열처럼 복사하지 않고 삽입/삭제가 빠르고 유연합니다.
다만, 리스트는 인덱싱(random access)에 약합니다.

---

🧪 실습 예제

int main()
{
    ArrayQueue<int> q;

    for (int i = 0; i < 100; i++)
        q.push(i);

    while (!q.empty())
    {
        cout << q.front() << endl;
        q.pop();
    }

    int size = q.size();
    return 0;
}

---

✅ 실행 결과

0
1
2
...
98
99

가장 먼저 들어간 데이터가 가장 먼저 나오는 선입선출 구조가 정확히 반영됨!

---

🧩 STL std::queue와 비교

#include <queue>

queue<int> q;
q.push(1);
q.push(2);
q.push(3);

while (!q.empty()) {
    cout << q.front() << endl;
    q.pop();
}

결과는 위에서 직접 만든 ArrayQueue와 동일합니다. STL은 내부적으로 deque 기반입니다.

---