37_队列的概念及实现（下）

关键词：队列的链式存储实现、链式队列的设计要点、队列链式存储实现的优化、LinkQueue.h

0. 队列的链式存储实现

链式队列的原理图

1. 链式队列的设计要点

• 类模板，抽象父类Queue的直接子类
• 在内部使用链式结构实现元素的存储
• 只在链表的头部和尾部进行操作
  链式队列的继承层次结构图

LinkQueue.h

#ifndef LINKQUEUE_H
#define LINKQUEUE_H

#include "queue"
#include "LinkList.h"
#include "Exception.h"

namespace DTLib
{

template < typename T >
class LinkQueue : public LinkList<T>
{
protected:
    LinkList<T> m_list;
public:
    LinkQueue();            // O(1)
    void add(const T& e);   // O(n)
    void remove();          // O(1)
    T front() const;        // O(1)
    void clear();           // O(n)
    int length() const;     // O(1)
};

template < typename T >
LinkQueue<T>::LinkQueue()
{
}

template < typename T >
void LinkQueue<T>::add(const T& e)
{
    m_list.insert(e);
}

template < typename T >
void LinkQueue<T>::remove()
{
    if( m_list.length() > 0)
    {
        m_list.remove(0);
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No element in current list queue ...");
    }
}

template < typename T >
T LinkQueue<T>::front() const
{
    if( m_list.length() > 0)
    {
        return m_list.get(0);
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No element in current list queue ...");
    }
}

template < typename T >
void LinkQueue<T>::clear()
{
    m_list.clear();
}

template < typename T >
int LinkQueue<T>::length() const
{
    return m_list.length();
}

}

#endif // LINKQUEUE_H

2. 使用LinkList类实现链式队列是否合适？是否有更好的方案？

使用LinkList类实现链式队列时，插入操作的时间复杂度为O(n)，大大影响了链式队列的性能。

3. 队列链式存储实现的优化

优化示意图

• 将LinkQueue依赖于LinuxList循环链表
  

4. 基于Linux内核链表的队列

LinkQueue.h

#ifndef LINKQUEUE_H
#define LINKQUEUE_H

#include "Queue.h"
#include "LinuxList.h"
#include "Exception.h"

namespace DTLib
{

template < typename T >
class LinkQueue : public Queue<T>
{
protected:
    struct Node : public Object
    {
        list_head head;
        T value;
    };

    list_head m_header;
    int m_length;

public:
    LinkQueue();            // O(1)
    void add(const T& e);   // O(1)
    void remove();          // O(1)
    T front() const;        // O(1)
    void clear();           // O(n)
    int length() const;     // O(1)
    ~LinkQueue();           // O(n)
};

template < typename T >
LinkQueue<T>::LinkQueue()
{
    INIT_LIST_HEAD(&m_header);
    m_length = 0;
}

template < typename T >
void LinkQueue<T>::add(const T& e)
{
    Node* node = new Node();

    if( node != NULL)
    {
        node->value = e;
        list_add_tail(&(node->head), &m_header);
        ++m_length;
    }
    else
    {
        THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to add new element in LinkQueue...");
    }
}

template < typename T >
void LinkQueue<T>::remove()
{
    if( m_length > 0)
    {
        list_head* toDel = m_header.next;
        list_del(toDel);
        --m_length;
        delete list_entry(toDel, Node, head);
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No element in current list queue ...");
    }
}

template < typename T >
T LinkQueue<T>::front() const
{
    if( m_length > 0)
    {
        return list_entry(m_header.next, Node, head)->value;
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No element in current list queue ...");
    }
}

template < typename T >
void LinkQueue<T>::clear()
{
    while( m_length > 0)
    {
        remove();
    }
}

template < typename T >
int LinkQueue<T>::length() const
{
    return m_length;
}

template < typename T >
LinkQueue<T>::~LinkQueue()
{
    clear();
}

}

#endif // LINKQUEUE_H

5.小结

• StaticQueue在初始化时可能多次调用元素类型的构造函数
• LinkList的组合使用能够实现队列的功能，但效率不高
• LinkQueue的最终实现组合使用了Linux内核链表
• LinkQueue中入队和出队操作可以在常量时间完成

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4