[자료구조] Queue 큐

글의 요약 

 

목차

 

---

Queue 큐

입력과 출력을 담당하는 창구가 따로 존재한다. 먼저 들어간 데이터가 먼저 나오는 자료구조이다. 

대기열을 떠오리면 쉽다. 은행 대기열은 번호표를 뽑은 순서대로 창구에 간다. 

 

FIFO(First-In-First-Out) 선입선출

 

---

Enqueue & Dequeue 삽입과 제거 연산

큐의 삽입(Enqueue)연산은 끝에서

큐의 제거(Dequeue)연산은 첫부분에서 수행된다.

 

 

 

 

---

 

Circular Queue 순환 큐

시작과 끝을 연결하여 효율적인 삽입/삭제가 가능하다.

큐 배열을 생성할 때 실제 용량보다 1만큼 더 크게 만들어서 Front와 Rear 사이를 비워준다. 비워준 노드를 더미 노드라고 부른다.

Rear은 실제 Rear보다 1 더 큰 값을 갖는다.

 

' Node의 크기 x ( Capacity + 1) '의 크기로 자유 저장소에 할당한다.

 

Circular Queue의 구조체 4요소

1. Capacity (용량)
2. Front (전단의 위치)
3. Rear (후단의 위치)
4. Pointer (순환 큐의 배열에 대한 포인터)

 

 

---

 

Linked Queue 링크드 큐

본문내용넣기

 

 

 

 

 

---

 

코드 예시

마

#include <iostream>
#include <queue>
using namespace std;
 
int main()
{
    queue<int> q;
 
    for (int i = 0; i < 100; i++)
        q.push(i);
 
    while (q.empty() == false)
    {
        int value = q.front();
        q.pop();
        cout << value << endl;
    }
 
    int size = q.size();
}

#include <iostream>
#include <stack>
#include <vector>
#include <list>
#include <queue>
using namespace std;
 
template<typename T>
class ListQueue
{
public:
    void push(const T& value)
    {
        _container.push_back(value);
    }
 
    void pop()
    {
        //_container.erase(_container.begin());
        _container.pop_front();
    }
 
    T& front()
    {
        return _container.front();
    }
 
    bool empty() { return _container.empty(); }
    int size() { return _container.size(); }
private:
    //vector<T> _container;
    list<T> _container;
};
 
int main()
{
    ListQueue<int> q;
 
    for (int i = 0; i < 100; i++)
        q.push(i);
 
    while (q.empty() == false)
    {
        int value = q.front();
        q.pop();
        cout << value << endl;
    }
 
    int size = q.size();
}

---

 

#include <iostream>
#include <stack>
#include <vector>
#include <list>
#include <queue>
using namespace std;
 
template<typename T>
class ArrayQueue
{
public:
    ArrayQueue()
    {
    }
 
    void push(const T& value)
    {
        // TODO : 다 찾는지 체크
        if (_size == _container.size())
        {
            // 증설 작업
            int newSize = max(1, _size * 2);  // max(a, b) a와 b값 중 큰 값을 return 해준다.
            vector<T> newData;
            newData.resize(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;
};
 
int main()
{
    ArrayQueue<int> q;
 
    for (int i = 0; i < 100; i++)
        q.push(i);
 
    while (q.empty() == false)
    {
        int value = q.front();
        q.pop();
        cout << value << endl;
    }
 
    int size = q.size();
}
 

 

---

위 코드들의 실행값은 모두 다음과 같다.