模版链队实现

队列作为允许在前段删除和后端插入得线性表，和栈类似，是一种操作受限制得线性。进行插入操作的端称之为队尾，进行删除操作的端称之为队头。队列中没有元素时，称之为空队列。尽管操作受到限制，但是仍然具有使用价值，如可以利用队列结构编写消息队列处理消息，利用队列结构编写内存池时可以将可用内存区块加入一个队列中等待使用，等等。这次实现的模版链队本质上仍是链表，这次的队列没有首节点，队列中全部元素均为队列中的成员。代码中注释了一个迭代器，是测试代码时候写的。 p.s.可以考虑重载[]来实现队列中的数据访问。。当然这是后话了。。

  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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184


//
//  Queue.h
//  链表
//
//  Created by 欧 长坤 on 13-10-5.
//  Copyright (c) 2013年 欧 长坤. All rights reserved.
//

#ifndef ______Queue__
#define ______Queue__

#include <iostream>

template <class T> class Queue;
//template <class T> class QueueIterator;

template <class T>
class QueueNode{
    friend class Queue<T>;
    //friend class QueueIterator<T>;
private:
    T data;
    QueueNode<T> *next;
};

template <class T>
class Queue{
    //friend class QueueIterator<T>;
private:
    QueueNode<T> *First;
    QueueNode<T> *Last;
    size_t Size;
public:
    Queue();
    ~Queue();
    void enqueue(T &value); // 入队
    bool dequeue(); // 出队
    T front();
    T back();
    bool isEmpty();
    size_t size();
    void clear();
    // 可以考虑重载[]
};

// 迭代器用于测试enqueue是否成功而写

// 链队迭代器
// 使用方法：
// int *x;
// QueueIterator<int> inter;
// x = inter.initialize(XXX); // XXX是队列
// while (inter) {
//      cout << *x << ' ';
//      x = inter.next();
// }
/*
template <class T>
class QueueIterator
{
private:

    QueueNode<T> *location;

public:

    T* initialize(const Queue<T>& queue)
    {
        location = queue.Last;
        if (location)
            return &location->data;
        return 0;
    }
    T* next()
    {
        if (!location)
            return &location->data;
        location = location->next;
        if (location) {
            return &location->data;
        }
        return 0;
    }

};
*/

template <class T>
Queue<T>::Queue()
{
    First = Last = new QueueNode<T>;
    if (NULL == First) {
        throw &quot;Out Of Memory!&quot;;
    } else {
        First->next = NULL;
    }
    Size = 0;
}

template <class T>
Queue<T>::~Queue()
{
    delete First;
    First = Last = NULL;
    Size = 0;
}

template <class T>
void Queue<T>::enqueue(T &value)
{
    QueueNode<T> *newQueueNode = new QueueNode<T>;
    if (NULL == newQueueNode) {
        throw &quot;Out Of Memory!&quot;;
    }
    newQueueNode->next = Last;
    newQueueNode->data = value;
    Last = newQueueNode;
    if (isEmpty()) {
        First = Last;
        First->next = NULL;
    }
    Size++;
}

template <class T>
bool Queue<T>::dequeue()
{
    if (isEmpty())
        return false;
    QueueNode<T> *p, *q;
    p = First;
    q = Last;
    while (q->next != p) {
        q = q->next;
    }
    First = q;
    First->next = NULL;
    delete p;
    Size--;
    return true;
}

template <class T>
T Queue<T>::front()
{
    return First->data;
}

template <class T>
T Queue<T>::back()
{
    return Last->data;
}

template <class T>
bool Queue<T>::isEmpty()
{
    if (Size == 0)
        return true;
    else
        return false;
}

template <class T>
size_t Queue<T>::size()
{
    return Size;
}

template <class T>
void Queue<T>::clear()
{
    QueueNode<T> *q = Last->next;
    while (NULL == q)
    {
        delete Last;
        Last = q;
        q = Last->next;
    }
    Last = First = NULL;
    Size = 0;
}

#endif /* defined(______Queue__) */