关键词：队列的链式存储实现、链式队列的设计要点、队列链式存储实现的优化、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内核链表的队列
#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
