04-(2) ADTs Queue

큐 (Queue)

• 논리적인 (ADT) 수준에서의 큐

  • 동일한 (homogeneous) 요소들로 이루어진 순서 있는 그룹으로,
    한쪽 끝(후단, rear)에서 새로운 요소의 삽입이 일어나고, 다른 한쪽 끝(전단, front)에서 요소의 제거가 일어난다.
  • FIFO (First In, First Out) 구조
    
    

• 구현(implementation) 수준에서의 큐

  • 선형 큐 (linear queue)

    • 요소를 삽입하거나 제거할 때 큐의 인덱스 (front/ rear)는 모두 증가한다.
    • 선형 큐는 정적 배열로 구현되기 때문에, 할당된 메모리의 크기에 제한이 있다.
      → 사용되지 않는 메모리가 있음에도 불구하고 인덱스(front/ rear)가 큐의 끝에 도달할 경우, 해당 큐를 더 이상 사용할 수 없는 문제가 있다.

  • 원형 큐 (circular queue, ring queue)

    • 메모리의 끝에 도달할 경우, 다시 처음 인덱스(0)로 돌아온다.
    • 나머지 연산자(modulus, %)를 통해 구현한다.

      if (rear == maxQue - 1) //front도 마찬가지
      	rear = 0;
      else
      	rear = rear + 1;

      rear = (rear + 1) % maxQue; //front도 마찬가지

---

원형 큐

실제로 원형 X, 논리적인 구조가 원형 O (메모리는 선형)

1. 기본적인 구조의 원형 큐
   • 선형 큐의 메모리 문제를 해결할 수 있지만,
     큐가 비어 있는 상태(empty)와 가득 차 있는 상태(full)를 구분할 수 없다는 문제가 있다.

     //queue is full
     rear + 1 === front
       
     //queue is empty
     rear + 1 == front;

2. front 포인터가 큐의 가장 앞 쪽에 있는 요소보다 한 칸 앞의 요소를 가리키는 큐!
   • front 와 rear 를 maxQue - 1 로 초기화 한다.
   • front 포인터가 가리키는 메모리 공간은 예약된(reserved)/낭비되는 공간
     → 사용 가능한 메모리 공간의 크기가 하나 줄어든다는 단점이 있다.
     
   • 기본적인 구조의 원형 큐에서 발생하는 구분 문제를 해결할 수 있다.

     //queue is full
     (rear + 1) % maxQue == front;
     
     //queue is empty
     rear == front;

3. 길이를 나타내는 변수 length를 활용한 큐
   • 기본적인 구조의 원형 큐에서 발생하는 구분 문제를 해결할 수 있다.
   • 구현
     : QueType 클래스를 상속 받는 CountedQueType 클래스 생성 → 함수 오버라이딩

---

큐의 연산

📌 해당 코드는 2번 큐(front 포인터가 큐의 가장 앞 쪽에 있는 요소보다 한 칸 앞의 요소를 가리키는 큐) 기준!

• 생성자 및 소멸자 (Constructor and Destructor)
  • QueType()

    template<class ItemType>
    QueType<ItemType>::QueType(int max) {
        maxQue = max + 1;
        front = maxQue - 1;
        rear = maxQue -1;
        items = new ItemType[maxQue]; //dynamic allocation
    }

    maxQue = max + 1
    : front가 한 칸 앞을 가리키는 원형 큐이기 때문에 메모리 한 칸은 사용할 수 없는 공간이다. 따라서 사용자가 원하는 수에 +1을 한 크기로 큐를 만든다.

  • ~QueType()

    template<class ItemType>
    QueType<ItemType>::~QueType() {
    	delete[] items; //deallocates array
    }

• 변환자 (Transformer)
  • Enqueue

    //function: adds newItem to the rear of the queue.
    //preconditions: queue has been initilaized and is not full.
    //postconditions: newItem is at rear of queue.
    
    template<class ItemType>
    void QueType<ItemType>::Enqueue(ItemType newItem) {
    	rear = (rear + 1) % maxQue;
    	items[rear] = newItem;
    }

  • Dequeue

    //function: removes front item from queue and return it in item.
    //preconditions: queue has been initilaized and is not empty.
    //postconditions: front element has been removed from queue and item is a copy of removed element.
    
    template<class ItemType>
    void QueType<ItemType>::Dequeue(ItemType& item) {
    	front = (front + 1) % maxQue;
    	item = items[front];
    }

• 관찰자 (Observer)
  • IsEmpty

    template<class ItemType>
    bool QueType<ItemType>::IsEmpty() {
    	return (rear == front);
    }

  • IsFull

    template<class ItemType>
    bool QueType<ItemType>::IsFull() {
    	return ((rear + 1) % maxQue == front);
    }