LinkQueue

文章目录

1 链式队列的概念1.1 队列的链式存储实现1.2 链式队列的设计要点 2 使用LinkList实现链式队列2.1 继承关系图2.2 代码实现 3 使用LinuxList实现LinkQueue3.1 队列链式存储实现的优化3.2 代码实现 4 小结

1 链式队列的概念

对于StaticQueue，当数据元素为类类型时，StaticQueue的对象在创建时，会多次调用元素类型的构造函数，影响效率。我们需要链式队列来解决这个问题。

1.1 队列的链式存储实现

1.2 链式队列的设计要点

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

---

2 使用LinkList实现链式队列

2.1 继承关系图

2.2 代码实现

LinkQueue.h：

#ifndef LINKQUEUE_H #define LINKQUEUE_H #include "Queue.h" #include "LinkList.h" #include "Exception.h" namespace LemonLib { template <typename T> class LinkQueue : public Queue<T> { protected: LinkList<T> m_list; public: void add(const T &e) { m_list.insert(e); } void remove() { if (m_list.length() > 0) { m_list.remove(0); } else { THROW_EXCEPTION(InvalidOperationException, "remove error, link queue is empty"); } } T front() const { if (m_list.length() > 0) { return m_list.get(0); } else { THROW_EXCEPTION(InvalidOperationException, "front error, link queue is empty"); } } void clear() { m_list.clear(); } int size() const { return m_list.length(); } }; } #endif // LINKQUEUE_H

---

3 使用LinuxList实现LinkQueue

我们可以发现使用LinkList实现链式队列，在入队时时间复杂度为O(n)，这显然是可以优化的。

3.1 队列链式存储实现的优化

类的继承关系图如下：

3.2 代码实现

LinkQueue.h：

#ifndef LINKQUEUE_H #define LINKQUEUE_H #include "Queue.h" #include "LinuxList.h" #include "Exception.h" namespace LemonLib { template <typename T> class LinkQueue : public Queue<T> { protected: struct Node : public Object { list_head head; T e; }; list_head m_header; int m_length; public: LinkQueue() { m_length = 0; INIT_LIST_HEAD(&m_header); } void add(const T &e) { Node* node = new Node(); if (node != NULL) { node->e = e; list_add_tail(&node->head, &m_header); m_length++; } else { THROW_EXCEPTION(NoEnoughMemoryException, "linkqueue add error, no enough memory"); } } void 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(InvalidOperationException, "remove error, link queue is empty"); } } T front() const { if (m_length > 0) { return list_entry(m_header.next, Node, head)->e; } else { THROW_EXCEPTION(InvalidOperationException, "front error, link queue is empty"); } } void clear() { while (m_length > 0) { remove(); } } int size() const { return m_length; } // 不要忘记提供析构函数 ~LinkQueue() { clear(); } }; } #endif // LINKQUEUE_H

---

4 小结

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