Queue

특징

• Stack과 동일한 선형 자료구조
• FIFO(First In, First Out)의 특징을 가져 가장 먼저 입력된 값이 가장 먼저 출력됨
• Array나 Linked List 방식, 2가지 방식으로 구현가능

구성

Stack과 공통적인 요소

• MAX_STACK_SIZE : array를 사용해 구현할 경우 array 생성시 사이즈 지정, IsFull() 체크시 기준이 됨
• Peek() : 가장 위에 있는 아이템을 제거하지 않고 보여줌
• IsEmpty() : Queue가 비어있는지 여부를 출력
  (비어있는데 Dequeue() 또는 Peek()을 호출해 underflow 오류 발생하는 것을 방지)
• IsFull() : Queue가 가득 차있는지 여부를 출력
  (가득 차있는데 Enqueue(item)를 호출해 overflow 오류 발생하는 것을 방지)
• GetSize() : 현재 포함하고 있는 아이템의 개수를 출력

Stack과 구분되는 요소

• front : -1로 초기화. 데이터가 있는 첫번째 칸의 1칸 앞에 위치
• rear : -1로 초기화. 데이터가 있는 마지막 칸에 위치
  (해당 2개의 요소를 통해 Queue가 비어있는지 여부를 확인할 수 있음)
• Enqueue(item) : 값을 배열의 뒤에 추가. 배열에 값을 추가하면서 rear에 1을 더함
• Dequeue() : front에 값을 1 더한 후 배열의 해당 위치의 값을 반환

구현

#include <iostream>
using namespace std;
template <typename T>
class Queue
{
private:
    int front, rear;
    const static int maxSize = 100;
    T arr[maxSize];

public:
    Queue()
    {
        front = -1;
        rear = -1;
    }

    bool IsFull() { return rear == maxSize - 1; }
    bool IsEmpty() { return front == rear; }
    int GetSize() { return rear - front; }

    void Enqueue(T value)
    {
        if(IsFull())
        {
            throw "Queue is full";
        }

        arr[++rear] = value;
    }

    T Dequeue()
    {
        if(IsEmpty())
        {
            throw "Queue is empty";
        }

        return arr[++front];
    }

    T Peek()
    {
        if(IsEmpty())
        {
            throw "Queue is empty";
        }

        return arr[front + 1];
    }

    void Display()
    {
        if(IsEmpty())
        {
            throw "Queue is empty";
        }

        for(int i = front + 1; i <= rear; i++)
        {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

Private 필드

private:
    int front, rear;
    const static int maxSize = 100;
    T arr[maxSize];

• 배열의 값이 포함된 시작 지점과 끝 지점을 표시하는 front와 rear
• 배열을 생성할 때 초기 값이 될 maxSize와 배열 arr

Public 필드

생성자

    Queue()
    {
        front = -1;
        rear = -1;
    }

• 생성시 front와 rear를 -1로 초기화

boolean 함수

    bool IsFull() { return rear == maxSize - 1; }
    bool IsEmpty() { return front == rear; }

• 최대 크기에서 1을 뺀 값이 rear와 같다면 배열의 마지막 부분까지 값이 저장된 것이므로 배열이 가득 찬 것으로 판단할 수 있음
• front와 rear 값이 같다면 비어있는 것으로 판단할 수 있음

Enqueue, Dequeue

Enqueue()

    void Enqueue(T value)
    {
        if(IsFull())
        {
            throw "Queue is full";
        }

        arr[++rear] = value;
    }

• 기존 rear 값에 1 더하고 배열의 해당 위치에 입력받은 value 값을 저장

Dequeue()

    T Dequeue()
    {
        if(IsEmpty())
        {
            throw "Queue is empty";
        }

        return arr[++front];
    }

• front는 값이 저장된 위치보다 1칸 앞을 가리키기 때문에, 값을 1 더해 해당 위치에 있는 값을 반환

한계점

• 지금 방식으로 Queue를 구현할 경우 값을 추가하는 것을 반복하다보면 rear가 무조건 배열의 끝까지 도달할 수 밖에 없음
• 해당 문제를 극복하기 위해서는 Dequeue가 실행될 때 모든 배열 내의 요소를 앞으로 1칸씩 이동시키는 조치가 필요함

    T Dequeue()
    {
        if(IsEmpty())
        {
            throw "Queue is empty";
        }

        T result = arr[front + 1];

        for(int i = front + 1; i <= rear; i++)
        {
            arr[i - 1] = arr[i];
        }

        rear--;

        return result;
    }