Queue의 정의

• 논리(ADT) 수준
  • 동형의 순서가 있는(ordered) 원소들이 존재
  • 새 원소는 뒤에 추가되고, 앞에서 원소들이 하나씩 제거되며 꺼내진다.
• 큐는 FIFO(First in, First out) 구조이다.

Queue 연산

• 뒤에서 추가
• 앞에서 제거

Queue ADT Members

• MakeEmpty: 큐를 빈 상태로 만듦
• IsEmpty: 큐가 빈 상태인지 확인
• IsFull: 큐가 가득 찼는지 확인
• Enqueue(ItemType newItem): 큐의 뒤에 새 아이템을 추가
• Dequeue(ItemType &item) : 앞에서 아이템을 제거하고 제거한 그 아이템을 반환함.

QueType의 Public Interface

typedef char ItemType;
class QueType
{
public:
  QueType(int max);
  QueType();
  ~QueType();
  void MakeEmpty();
  bool IsEmpty() const;
  bool IsFull() const;
  void Enqueue(ItemType item);
  void Dequeue(ItemType &item);
private:
  // ...
}

Queue - array based

Fixed Front

• A, B, C, D를 넣는다

  • [A][B][C][D]

• Deque를 호출한 후

  • [][B][C][D] $\rightarrow$ [B][C][D][] (앞으로 당김)
  • Deque를 호출할 때마다 원소들을 앞으로 당겨야 한다.

Moving Front

• A, B, C, D를 넣는다

  • [A][B][C][D]

• Deque를 호출한 후

  • 원소는 큐에서 움직이지 않는다
  • [][B][C][D]

• IsFull의 문제

  • 아래와 같은 경우, 정말 큐가 가득 찬 것일까?

bool QueType::IsFull() const
{
  return (rear == MAX_ITEMS - 1);
}

Circular Queue

• 큐 요소 둘러싸기

rear = (rear + 1) % MAX_ITEMS;
items[rear] = newItem;

• Full, Empty 판별의 문제

  • Empty
    • [][][N][][] : front=2, rear=2
    • [][][][][] : front=3, rear=2
  • Full
    • [L][M][][J][K] : front=3, rear=1
    • [L][M][N][J][K] : front=3, rear=2

• One Slot Reservation

  • front = 첫 번째 요소 한 칸 앞으로 지정
    • Empty
      • [][][N][][] : front=1, rear=2
      • [][][][][] : front=2, rear=2
    • Full
      • [L][M][(reserved)][J][K] : front=2, rear=1
      • An enqueue operation fails: The stack is full

class FullQueue{};
class EmptyQueue{};
typedef char ItemType;

class QueType
{
public:
  QueType();
  QueType(int max);
  ~QueType();
  void MakeEmpty();
  bool IsEmpty() const;
  bool IsFull() const;
  void Enqueue(ItemType newItem);
  void Dequeue(ItemType &item);
private:
  int front;
  int rear;
  ItemType *items;
  int maxQue;
};

QueType::QueType(int max)
{
  maxQue = max + 1;
  // Initially points to the last slot
  front = maxQue - 1;
  rear = maxQue - 1;
  items = new ItemType[maxQue];
}

QueType::QueType()
{
  maxQue = 501;
  front = maxQue - 1;
  rear = maxQue - 1;
  items = new ItemType[maxQue];
}

QueType::~QueType()
{
  delete []items;
}

void QueType::MakeEmpty()
{
  front = maxQue - 1;
  rear = maxQue - 1;
}

bool QueType::IsEmpty() const
{
  return (rear == front);
}

bool QueType::IsFull() const
{
  return ((rear + 1) % maxQue == front);
}


void QueType::Enqueue(ItemType newItem)
{
  if (IsFull())
    throw FullQueue();
  else {
    rear = (rear + 1) % maxQue;
    items[rear] = newItem;
  }
}

void QueType::Dequeue(ItemType& item)
{
  if (IsEmpty())
    throw EmptyQueue();
  else {
    front = (front + 1) % maxQue;
    item = items[front];
  }
}

Queue - Linked List based

class QueType
{
public:
    QueType();
    ~QueType();
    void MakeEmpty();
    bool IsEmpty() const;
    bool IsFull() const;
    void Enqueue(ItemType newItem);
    ItemType Dequeue();
private:
    Node *front;
    Node *rear; 
};

QueType::QueType()
: front(NULL), rear(NULL)
{}


bool QueType::IsEmpty() const {
    return (front == NULL);
}

bool QueType::IsFull() const {
    Node *tempPtr;
    try {
        tempPtr = new Node;
        delete tempPtr;
        return false;
    } catch(std::bad_alloc &exception) {
        return true;
    }
}

void QueType::Enqueue(ItemType newItem)
{
    if (IsFull()) 
        throw FullQueue();
    
    Node *newNode;
    newNode = new Node;
    newNode->info = newItem;
    newNode->next = NULL;

    if (rear == NULL) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }

}

ItemType QueType::Dequeue()
{
    if (IsEmpty())
        throw EmptyQueue();

    Node *tempPtr;
    ItemType item;

    tempPtr = front;
    front = front->next;
    item = tempPtr->info;
    delete tempPtr;

    if (front == NULL)
        rear = NULL;

    return item;
}


void QueType::MakeEmpty()
{
    Node *tempPtr;

    while (front != NULL)
    {
        tempPtr = front;
        front = front->next;
        delete tempPtr;
    }

    front = rear = NULL;
}

QueType::~QueType()
{
    Node *tempPtr;

    while (front != NULL)
    {
        tempPtr = front;
        front = front->next;
        delete tempPtr;
    }
}

Big-O Comparison

Function	Dynamic Array	Linked-List
Class constructor	O(1)	O(1)
MakeEmpty	O(1)	O(N)
IsFull	O(1)	O(1)
IsEmpty	O(1)	O(1)
Enqueue	O(1)	O(1)
Dequeue	O(1)	O(1)
Destructor	O(1)	O(N)

• List: 오래 저장
  • 삭제하는 일이 빈번하지 않음
  • Linked List 유리
• Stack/Queue: 빈번한 삽입/삭제
  • 배열 기반 유리(동적 할당 배열)