模版链队实现

Published at发布于:： 2013-10-05 | PV/UV: / | Reading阅读:： 3 min

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

//
//  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__) */

推荐订阅源

Posts on Changkun's Blog

模版链队实现