Algorithm&DataStructure - Queue

1. Linear Queue

- 선입선출(FIFO, First In First Out) 방식의 선형 자료구조

- 문제점 : rear, front는 계속 증가만 한다. 나중에 한정된 메모리 끝에 rear가 도달 했을 때, 사실상 메모리에 비어 있는 공간이 있을 수 있다. 즉, int 100개 만큼의 메모리를 할당해도 100개의 정수를 넣기도 전에 rear가 끝에 도달 할 수 있다.

- 해결 1 : 빈 공간이 생길 때 마다 원소들을 앞으로 당긴다.

- 해결 2 : Circular Queue

- 해결 3 : Linked List로 구현

class Queue
{
private:
  int front;
  int rear;
  int count;
  const int size;
  int* values;

public:
  Queue():size(2000000),front(0),rear(0),count(0)
  {
    values = new int[size];
  }
  ~Queue()
  {
    delete []values;
  }

  bool IsEmpty() const
  {
    if(front==rear)
      return true;
    else
      return false;
  }

  bool IsFull() const
  {
    if(rear >= size)
      return true;
    else
      return false;
  }

  int Back() const
  {
    if(!IsEmpty())
      return values[rear-1];
    else
      return -1;
  }

  int Front() const
  {
    if(!IsEmpty())
    {
      return values[front];
    }
    else 
      return -1;
  }

  void Push(int v)
  {
    if(!IsFull())
    {
      values[rear] = v;
      rear = rear +1;
      count++;
    }
  }

  void Pop()
  {
    if(!IsEmpty())
    {
      printf("%d\n",values[front]);
      front++;
      count--;
    }
    else printf("%d\n",-1);
  }

  int Size() const
  {
    return count;
  }

};

2. Circular Queue

- 원형 큐가 가득 차 있음을 표현하기 위해 배열 끝 칸은 저장용으로 사용하지 않는다. 그래야 (rear+1)%size == front로 IsFull()을 만들 수 있다.