源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
template<typename ItemType>
class Queue
{
private:
    struct Node
    {
        Node* next;
        ItemType data;
        Node() : next(nullptr) {}
        explicit Node(const ItemType& item) : next(nullptr), data(item) {}
        explicit Node(ItemType&& item) : next(nullptr), data(std::move(item)) {}
    };
    Node* head;
    Node* tail;
    Queue(const Queue&) = delete;
    Queue& operator=(const Queue&) = delete;
public:
    Queue(){ head = tail = new Node(); }
    ~Queue(){
        while (head != nullptr)
        {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
    bool Pop(){
        if (IsEmpty()) return false;
        Node* temp = head->next;
        head->next = temp->next;
        delete temp;
        if (head->next == nullptr) {
            tail = head;
        }
        return true;
    }
    ItemType* Peek() const{
        if (tail->next == nullptr)
        {
            return nullptr;
        }
        return &tail->next->data;
    }
    void Empty(){
        while (!IsEmpty()) Pop();
    }
    bool IsEmpty() const{
        return head->next == nullptr;
    }
    bool Enqueue(const ItemType& item){
        Node* temp = new Node(item);
        if (temp == nullptr)
            return false;
        tail->next = temp;
        tail = temp;
        return true;
    }
    bool Enqueue(ItemType&& item){
        Node* temp = new Node(std::move(item));
        if (temp == nullptr)
		   return false;
        tail->next = temp;
        tail = temp;
        return true;
    }
    bool Dequeue(ItemType& item){
        if (IsEmpty()) return false;
        Node* temp = head->next;
        item = std::move(temp->data);
        head->next = temp->next;
        delete temp;
        if (head->next == nullptr) 
            tail = head;
        return true;
    }
    // 迭代器支持
    class Iterator
    {
    private:
        Node* current;
    public:
        Iterator(Node* node) : current(node) {}
        ItemType& operator*() { return current->data; }
        Iterator& operator++() { current = current->next; return *this; }
		bool operator!=(const Iterator& other) const { return current != other.current;}
	};
    Iterator begin() { return Iterator(head->next); }
    Iterator end() { return Iterator(nullptr); }
};
template<typename ItemType>
std::ostream& operator<<(std::ostream& os, Queue<ItemType>& queue) {
    os << "[";
    for (const auto& item : queue) {
        os << item;
        if (&item != &(*queue.end())) {
            os << ", ";
        }
    }
    os << "]";
    return os;
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Test Code
int main(){
    Queue<int> q;
    for (int i = 0; i < 20; i++)
    {
        q.Enqueue(i);
    }
    std::cout<< q << std::endl;
    for (int i = 0; i < 10; i++)
    {
        int temp;
        q.Dequeue(temp);
    }
    std::cout<< q << std::endl;
    for (int i = 0; i < 10; i++)
    {
        std::cout << q.Peek() << std::endl;
    }
    std::cout<< q << std::endl;
    q.Empty();
    std::cout<< q << std::endl;
    return 0;
}