[Data Structures] Queue | 큐 구조

Queue

 

큐 구조

 

 

 

- 한 쪽 끝에서 삽입이 일어나고 그 반대쪽 끝에서 삭제가 일어나는 Ordered List(순서 리스트)이다.

※ Stack: LIFO (Last In First Out)
※ Queue: FIFO (First In First Out)

 

- Queue는 Item 들을 도착한 순서대로 보관한다.
- \(\texttt{Queue는 보관할 수 있는 Item 수에 한계가 있다.
- Empty \(\texttt{Queue}\)를 생성할 수 있어야 한다.
- \(\texttt{Queue}\)가 비어 있는지 검사할 수 있어야 한다.
- \(\texttt{Queue}\)가가득차있는지검사할수있어야한다.
- \(\texttt{Queue}\)의 Rear 부분(꼬리 부분)에 항목을 추가할 수 있어야 한다.
- \(\texttt{Queue}\)의 Front 부분(머리 부분)에 항목을 삭제할 수 있어야 한다.
- \(\texttt{Queue}\)가 현재 갖고 있는 총 Item의 개수를 알 수 있어야 한다.

- \(\texttt{Queue}\)의 내부에 저장되는 데이터로는 전후 데이터가 서로 연결되어 있는 Linked List가 적합하다.
- Head에서 Dequeuing이 일어나고, Tail에서 Enqueuing이 일어나야 하는 Queue 구조의 구현 수단으로써
  Array는 적합하지 않다. Array로의 구현을 위해서는 Array를 원형으로 다루는 추가적인 세부 구현이 필요하다.

---

\(\texttt{Queue}\) Class Interface

// Queue.h

#ifndef QUEUE_H_
#define QUEUE_H_

struct Node {             // Singly Linked List
    Item item;
    struct Node* next;
};

class Queue {
private:
    enum {Q_SIZE = 10};
private:
    Node* Front;
    Node* Rear;
    int items;
    const int qSize;
public:
    Queue(int qs = Q_SIZE);
    ~Queue();
    bool isEmpty() const;
    bool isFull() const;
    int queueCount() const;
    bool enQueue(const Item& item);    // Insertion Operation at Front
    bool deQueue(Item& item);          // Delete Operation at Rear
};

#endif

Performance (성능)