字數：8598 字 ｜ 預估閱讀時間：43 分鐘

Second Attempt

D1 原本 2 TLE, 56 MLE，把 node_ 改成 tail，然後讓它指向 head 解決 TEL，但因為有循環實作上要小心一點（destructor 要先斷開循環），另外是當 a_超過 vector 大小的一半（vector 前半的東西都已經 dequeue 掉了）就把前面的東西清掉，解決 MLE

討論區上的推薦修正方向，感謝我的強大同學們。

LinkedQuene

將原本從頭開始的LinkedQuene，改成 Circular 的方式。
也就是將 node_ 指向Tail，並將 Tail 的 next 指向Head。

Copy Constructor 和 Destructor

前者（Copy Constructor）的重點是「取得原始列的Head」：

1. 取得原始列的Head
2. 繼續向後複製直到 Tail （直到發現 → next = head_）
3. 把 newTail->next = newHead，再將原本的 node_ = newTail

後者（Destructor）的重點是「如何拆開循環」：

1. 取得第一個元素位置
2. 把尾端指向Nullptr
3. 接著從頭開始刪除

Copy constructor 實作

//幫你貼心的把Struct放在這
/*
struct ListNode {
    ListNode(T val) : val{std::move(val)}, next{nullptr} {}
    T val;
    ListNode* next;
};
*/

// Copy constructor：複製另一個 circular linked list
template<typename T>
LinkedQueue<T>::LinkedQueue(const LinkedQueue& other) {
    if (other.node_ == nullptr) {
        node_ = nullptr;
    } else {
        // 取得原始隊列的 head (tail->next)
        ListNode<T>* origHead = other.node_->next;
        // 建立新鏈結的第一個節點 (newHead)
        ListNode<T>* newHead = new ListNode<T>(origHead->val);
        ListNode<T>* newTail = newHead;

        // 從原始 head 的下一個開始複製，直到回到 origHead
        for (ListNode<T>* current = origHead->next; current != origHead; current = current->next) {
            newTail->next = new ListNode<T>(current->val);
            newTail = newTail->next;
        }
        // 完成 circular 連結：newTail->next 指向 newHead
        newTail->next = newHead;
        // 將本物件的 tail 設為 newTail
        node_ = newTail;
    }
}

Destructor 實作

//新的Destructor
template<typename T>
LinkedQueue<T>::~LinkedQueue() {
    if (node_ != nullptr) {
        // 取得 head（佇列第一個元素）
        ListNode<T>* head = node_->next;
        // 斷開環狀連結，讓 tail->next = nullptr
        node_->next = nullptr;
        // 依序刪除所有節點
        while (head != nullptr) {
            ListNode<T>* temp = head;
            head = head->next;
            delete temp;
        }
    }
}

（看到這個註解有GPT的味，沒錯你想的是對的）

Enquene & Dequene

這兩個這我認為較為單純。

前者（Enquene）

1. val 創建一個新的 newnode_
2. 將 newnode_→next 指向 head（也就是目前node_（Tail）→ next），
3. node_->next = newnode
4. node_ = newnode

後者（Dequene）

1. 利用 tail_ → next取得 head_ 並存起來
2. tail_→ next = head_ → next
3. delete head_ 並回傳值

Enqueue 實作

//幫你貼心的把Struct放在這
/*
struct ListNode {
    ListNode(T val) : val{std::move(val)}, next{nullptr} {}
    T val;
    ListNode* next;
};
*/
// Enqueue：在 circular list 中插入新節點
template<typename T>
void LinkedQueue<T>::Enqueue(const T& val) {
    // 空隊列情形：建立一個新節點，讓其 next 指向自己
    if (node_ == nullptr) {
        node_ = new ListNode<T>(val);
        node_->next = node_;
        return;
    }
    // 非空：建立新節點，令新節點->next 指向原 head (即 node_->next)
    ListNode<T>* newNode = new ListNode<T>(val);
    newNode->next = node_->next;
    node_->next = newNode;
    // 更新 tail：newNode 成為新的 tail
    node_ = newNode;
}

Dequeue 實作

// Dequeue：取出 head 元素
template<typename T>
T LinkedQueue<T>::Dequeue() {
    assert(node_ != nullptr && "Dequeue called on empty queue.");
    // head 為 tail->next
    ListNode<T>* head = node_->next;
    T ans = head->val;
    // 若只有一個元素，刪除後設為空
    if (node_ == head) {
        delete head;
        node_ = nullptr;
    } else {
        node_->next = head->next;
        delete head;
    }
    return ans;
}

Reference: https://hackmd.io/@hank20010209/B1TkvWYO_

ArrayQuene

std::vector<T> data_; //存資料
int a_; //存開頭的位置
int b_; //陣列最大容量

原本那個方法不是不行，但會TLE（Time Limit Exceed），所以改了新方法

此部分則是比較單純，幾個原則：

1. 如果目前元素數量 > 陣列最大容量：將容量翻倍，並將原本的內容搬遷過去
2. 一樣用 a_ 指向第一個元素（Head_）

//幫你貼心的把Struct放在這
/*
std::vector<T> data_;
int a_;
int b_;
*/

template<typename T>
void ArrayQueue<T>::Enqueue(const T& val) {
    // 當陣列已滿，進行擴充（通常以容量翻倍）
    if (b_ == data_.size()) {
        std::vector<T> newData(data_.size() * 2);
        // 按照正確的順序搬移現有元素
        for (size_t i = 0; i < b_; i++) {
            newData[i] = data_[(a_ + i) % data_.size()];
        }
        data_ = std::move(newData);
        a_ = 0;
    }
    // 新元素插入的位置：(head_ + count_) mod capacity
    size_t tail = (a_ + b_) % data_.size();
    data_[tail] = val;
    b_++;
}

template<typename T>
T ArrayQueue<T>::Dequeue() {
    // 取出位於 head_ 的元素
    T ans = data_[a_];
    // 更新 head_ 指向下一個位置（模運算保證循環）
    a_ = (a_ + 1) % data_.size();
    b_--;
    return ans;
}

Outcome

Second Attempt: AC.