# DS Queue

{%hackmd theme-dark %}

## 佇列

:::info
* FIFO
* 只能從**頂端**取/刪資料
* 只能從**尾端**加資料
:::

## 實作

### Array-based

class Queue{
  private:
    int *arr;
    int front, rear;
    int capacity;
  public:
    Array_based_queue(int size){
      arr = new int[size];
      capacity = size;
      front = rear = -1;
    }
    void enqueue(int x){
      if(rear == capacity - 1){
        cout << "Queue is full" << endl;
        return;
      }
      if(front == -1){
        front = 0;
      }
      rear++;
      arr[rear] = x;
    }
    void dequeue(){
      if(front == -1){
        cout << "Queue is empty" << endl;
        return;
      }
      front++;
      if(front > rear){
        front = rear = -1;
      }
    }
    int peek(){
      if(front == -1){
        cout << "Queue is empty" << endl;
        return -1;
      }
      return arr[front];
    }
    bool isEmpty(){
      if(front == -1){
        return true;
      }
      return false;
    }
    void print(){
      if(front == -1){
        cout << "Queue is empty" << endl;
        return;
      }
      for(int i = front; i <= rear; i++){
        cout << arr[i] << " ";
      }
      cout << endl;
    }
};

### Pointer-based

template <class T>
class Queue {
    struct Node { // circular doubly linked lists
        T data;
        Node *next;
        Node *prev;
        Node(const T &d) : data(d), next(nullptr), prev(nullptr) {}
    };
    Node *head;
    Node *tail;
    int size;

   public:
    Queue() : head(nullptr), tail(nullptr), size(0) {}
    void PrintAll() {
        Node *temp = head;
        for (int i = 0; i < size; ++i) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
    int length() const { return size; }

    bool isEmpty() const { return size == 0; }

    bool isFull() const { return length() >= queueMax; }

    void push(const T &input) {
        Node **h = &head;
        Node **t = &tail;
        Node *newNode = new Node(input);
        if (isEmpty()) {
            *h = newNode;
            *t = newNode;
            newNode->next = newNode;
            newNode->prev = newNode;
        } else {
            (*t)->next = newNode;
            newNode->prev = *t;
            newNode->next = *h;
            (*h)->prev = newNode;
            *t = newNode;
        }
        size++;
    }
    T &getFront() {
        if (head == nullptr) {
            cerr << "Queue is empty!" << endl;
        }
        return head->data;
    }
    void getFront(T &first) {
        if (head == nullptr) {
            cerr << "Queue is empty!" << endl;
        }
        first = head->data;
    }

    void pop() {
        Node **h = &head;
        Node **t = &tail;
        if (isEmpty()) {
            cerr << "Queue is empty!" << endl;
        } else if (length() == 1) {
            delete *h;
            *h = nullptr;
            *t = nullptr;
        } else {
            Node *temp = *h;
            *h = (*h)->next;
            (*h)->prev = *t;
            (*t)->next = *h;
            delete temp;
        }
        size--;
    }

    void clear() { // clean up
        while (!isEmpty()) {
            pop();
        }
    }
    ~Queue() { // destructor
        clear();
    }

}; // end Queue

## 例題

### UVA 10935

#### 題目：

每筆測資為一個數字 n，會有一個 1 ~ n 的紙牌堆，要求丟掉最上面的牌，然後把目前最上面的那張牌放到牌堆的最下面。

### UVA 12100

#### 題目：
每個工作都有優先度，對於第 i 個工作如果輪到他時，若這個工作優先度最高則可直接執行

如果有人比他高，他會被踢到隊尾重新排隊，問花多少時間能完成全部工作

### 排程問題

#### 題目：
每個工作都有到達時間、截止時間與執行時間，如果接到新工作但你在忙就把新工作丟去排隊，

隊伍長度限制為 3 個工作，要加入新工作隊伍卻滿了就直接取消，如果過了截止時間也取消，問哪些工作能被完成、什麼時候完成、等了多久，以及哪些工作無法完成、等了多久。