큐(queue)

이번엔 queue에 대해 이야기해보겠습니다. queue는 먼저 들어온 데이터가 먼저 나가는 First In First Out 구조입니다.
Stack과 마찬가지로 STL에선 deque로 대신할 수 있기 때문에 라이브러리 형태로 제공되진 않습니다.

First In First Out(FIFO)

대표적인 함수의 인터페이스는 아래와 같습니다.

push: 데이터를 입력하면 맨앞단에 추가됩니다.
pop: 맨앞단의 데이터를 삭제합니다.
front: 맨앞의 데이터를 반환합니다.
empty: 메모리가 비어있는지 확인하여 true or false를 반환합니다.
full: 메모리에 데이터가 가득 차 있는지 확인하여 true or false를 반환합니다

queue의 경운 내부적으로 1차원 배열을 사용하지만 논리적으로 배열을 순환하게있게 작성을 해 circular queue 형태로 사용을 합니다.
tail 앞에 head가 위치하면 메모리가 가득 찬 상태며 head와 tail이 같은 위치를 가리키면 비어있는 상태입니다.

circular queue의 full 조건과 empty 조건

이번엔 코드로 작성해보겠습니다.

#include <iostream>
using namespace std;
template <typename T>

class queue
{
private:
    #define MAX_SIZE 4
    T dataArray[MAX_SIZE];
    int head, tail;
public:
    queue():head(0), tail(0)
    {
        memset(dataArray, 0, sizeof(dataArray));
    }

    ~queue() {}

    void push(T data)
    {
        if (full())
        {
            printf("queue is full\n");
            return;
        }

        dataArray[tail] = data;
        tail = (tail + 1) % MAX_SIZE;
    }

    void pop()
    {
        if (empty())
        {
            printf("queue is empty\n");
            return;
        }

        head = (head + 1) % MAX_SIZE;
    }

    T front()
    {
        if (empty())
        {
            printf("queue is empty\n");
        }

        return dataArray[head];
    }

    bool full()
    {
        return ((tail + 1) % MAX_SIZE) == head;
    }

    bool empty()
    {
        return head == tail;
    }

    void print()
    {
        int h = head, t = tail;
        while (h != t)
        {
            printf("%d ", dataArray[h]);
            h = (h + 1) % MAX_SIZE;
        }
        printf("\n");
    }
};

int main()
{
    queue<int> que;
    que.push(1);
    que.print();

    que.push(2);
    que.print();

    que.push(3);
    que.print();

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

    que.push(4);
    que.print();

    return 0;
}