113-2 DSAP Hw3 D1

作者: /

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

HackMD好讀版點這裡

總結與回顧

This is my first time documenting the process of solving a homework problem.
The main reason I started this project is to push myself to complete coding exercises more thoroughly—without relying on AI assistance.
Although I wouldn’t call it a full success, this attempt has brought some positive changes: I’ve reduced my dependency on AI and started practicing how to express my thoughts and logic clearly.
This article may be a bit messy and casual, but to me, it’s a big step toward facing my weaknesses and actively making a change.
I’ll do my best to continue writing tech notes like this. One step at a time.

這是我第一次紀錄自己解題的過程。
我之所以想開始這個計畫，是為了督促自己更扎實地完成程式練習，而且不依賴 AI 協助。
雖然這次的嘗試稱不上完全成功，但它確實帶來了一些正面的改變：我開始減少對 AI 的依賴，也開始練習如何清楚地表達自己的思考與邏輯。
這篇文章也許有點零碎、風格偏隨性，但對我來說，這是一個重要的起點，是我面對自己弱點、試著改變的一小步。
我會繼續努力寫出更多像這樣的技術筆記！

題目敘述

工程師小金想比較不同的資料結構實作佇列 (Queue) 會有什麼差異，所以想請你幫忙實作具有 IQueue 介面的兩種不同的類別 LinkedQueue 與 ArrayQueue。請注意佇列是一種先入先出 (FIFO) 的資料集合，先加入 (Enqueue) 到佇列的元素會先從佇列被移除 (Dequeue)：

實作 LinkedQueue 的建構子、複製建構子、賦值運算、解構子

LinkedQueue();
LinkedQueue(const LinkedQueue&);
LinkedQueue& operator=(const LinkedQueue&);
~LinkedQueue();

實作 ArrayQueue 的建構子（不用實作複製建構子、賦值運算、解構子）

ArrayQueue();

實作 Empty 方法，回傳佇列是否為空

virtual bool Empty() const = 0;

實作 Enqueue 方法，將元素 val 插入到佇列中

  • 佇列是一種先入先出 (FIFO) 的資料集合，先加入 (Enqueue) 到佇列的元素會先從佇列被移除 (Dequeue)：
virtual void Enqueue(const T&) = 0;

實作 Dequeue 方法，將一個元素從佇列移除

  • 佇列是一種先入先出 (FIFO) 的資料集合，先加入 (Enqueue) 到佇列的元素會先從佇列被移除 (Dequeue)：
  • 當佇列為空時，為《未定義行為》
virtual T Dequeue() = 0;

實作 Peek 方法，回傳下一個會被移除的元素值

  • 當佇列為空時，為《未定義行為》
virtual const T& Peek() const = 0;

注意: T 不一定為 int，T 型態只保證提供預設建構與複製語意

題目給予的內容

#include <iostream>
#include <utility>
#include <vector>
#include <cassert>    // For Test
#include <random>     // For Test
#include <functional> // For Test

template<typename T>
struct IQueue {
    virtual ~IQueue() {}
    virtual bool Empty() const = 0;
    virtual void Enqueue(const T&) = 0;
    virtual T Dequeue() = 0;
    virtual const T& Peek() const = 0;
};

template<typename T>
struct ListNode {
    ListNode(T val) : val{std::move(val)}, next{nullptr} {}
    T val;
    ListNode* next;
};

template<typename T>
class LinkedQueue: public IQueue<T> {
    public:
        using ElemType = T;
        LinkedQueue();
        LinkedQueue(const LinkedQueue&);
        LinkedQueue& operator=(const LinkedQueue&);
        ~LinkedQueue();
        bool Empty() const;
        void Enqueue(const T&);
        T Dequeue();
        const T& Peek() const;
    private:
        ListNode<T>* node_;
};

template<typename T>
class ArrayQueue : public IQueue<T> {
    public:
        using ElemType = T;
        ArrayQueue();
        bool Empty() const;
        void Enqueue(const T&);
        T Dequeue();
        const T& Peek() const;
    private:
        std::vector<T> data_;
        int a_;
        int b_;
};

template<typename TQueue,
         typename = std::enable_if<
            std::is_base_of<
                IQueue<typename TQueue::ElemType>, TQueue>::value>>
std::ostream& operator<<(std::ostream& os, const TQueue& p) {
    TQueue q = p;
    bool isFirst = true;
    os << '[';
    while (!q.Empty()) {
        if (isFirst) {
            isFirst = false;
        } else {
            os << ", ";
        }
        os << q.Dequeue();
    }
    os << ']';
    return os;
}

void Test1(); // Sample1
void Test2(); // LinkedQueue
void Test3(); // LinkedQueue [Large Element]
void Test4(); // ArrayQueue
void Test5(); // ArrayQueue [Large Element]
void Test6(); // ArrayQueue and LinkedQueue

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int id;
    std::cin >> id;
    void (*f[])() = { Test1, Test2, Test3, Test4, Test5, Test6 };
    f[id-1]();
}

void Test1() {
    LinkedQueue<int> q1;
    std::cout << "01) " << q1 << std::endl;

    q1.Enqueue(3);
    std::cout << "02) " << q1 << std::endl;

    q1.Enqueue(5);
    std::cout << "03) " << q1 << std::endl;

    q1.Enqueue(7);
    std::cout << "04) " << q1 << std::endl;

    std::cout << "05) " << q1.Dequeue() << std::endl;

    std::cout << "06) " << q1.Peek() << std::endl;

    q1.Enqueue(9);
    std::cout << "07) " << q1 << std::endl;

    ArrayQueue<int> q2;
    std::cout << "08) " << q2 << std::endl;

    q2.Enqueue(3);
    std::cout << "09) " << q2 << std::endl;

    q2.Enqueue(5);
    std::cout << "10) " << q2 << std::endl;

    q2.Enqueue(7);
    std::cout << "11) " << q2 << std::endl;

    std::cout << "12) " << q2.Dequeue() << std::endl;

    std::cout << "13) " << q2.Peek() << std::endl;

    q2.Enqueue(9);
    std::cout << "14) " << q2 << std::endl;
}

namespace Feis {
}

void Test2() {
}
void Test3() {
}
void Test4() {
}
void Test5() {
}
void Test6() {
}

// [YOUR CODE WILL BE PLACED HERE]

實作紀錄

（以下有些雜亂但應該有些幫助）

First Attempt

2025/4/9下午2.~3.：

一開始忘記怎麼用Single Linked，找回記憶後就好了。

array的部分則沒太多問題，昨天上課有提到如何利用兩個位置標示a_、b_來表示陣列的前後，在實作的時候記得要根據動作調整這二者的位置即可。（到後面發現根本好像不是這樣用）

不過大概卡了十分鐘在q1.Enquene不知道為甚麼只能跑到 2) ，後來發現是我根本沒寫好 copy constructor，根本就在shallow copy（淺複製，意指只有複製指向開頭的指標）。改成Deep Copy（深複製，也就是完整的複製整組串列的內容）就解決了。

Deep Copy 實作（非 Circular）

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

// Deep Copy Implement
template<typename T>
LinkedQueue<T>::LinkedQueue(const LinkedQueue& other) {
    if (other.node_ == nullptr) {
        node_ = nullptr;
    } else {
        // 建立新的第一個節點
        node_ = new ListNode<T>(other.node_->val);
        ListNode<T>* currentSrc = other.node_->next;
        ListNode<T>* currentDst = node_;
        while (currentSrc != nullptr) { //接著不斷移動複製直到尾
            currentDst->next = new ListNode<T>(currentSrc->val);
            currentDst = currentDst->next;
            currentSrc = currentSrc->next;
        }
    }
}

//這個時候還沒改成 circular linked quene

Outcome

First Attempt: TLE(in 2 4 5 6) get 8 point.

WaynSpace 部落格 Logo，黑白風格，包含鍵盤、相機與羽毛筆

喜歡攝影、程式、生活隨筆？
訂閱 WaynSpace，新文章第一時間通知你📬
✨ 精選內容，無垃圾信，隨時可取消

We don’t spam! Read our privacy policy for more info.

頁次: 1 2

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

返回頂端