36_队列的概念及实现（上）

关键词：队列的定义、队列的特性、队列的操作、队列的继承、StaticQueue

0. 队列的定义

• 队列是一种特殊的线性表
• 队列仅能在线性表的两端进行操作
  队头（Front）：取出数据元素的一端
  队尾（Rear）：插入数据元素的一端

1. 队列的特性

先进先出（First In First Out）

队列的特征示意图

2. 队列的操作

• 创建队列(Queue())
• 销毁队列(~Queue())
• 清空队列(clear())
• 进队列(add())
• 出队列(remove())
• 获取队头元素(front())
• 获取队列的长度(length())

3. 队列的继承

队列的继承关系图
Queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include "Object.h"

namespace DTLib
{

template < typename T >
class Queue : public Object
{
public:
    virtual void add(const T& e) = 0;
    virtual void remove() = 0;
    virtual T front() const = 0;
    virtual void clear() = 0;
    virtual int length() const = 0;
};

}

#endif // QUEUE_H

4. 队列的顺序实现

StaticQueue示意图

• StaticQueue设计要点：
  • 类模板
  • 使用原生数组作为队列的存储空间
  • 使用模板参数决定队列的最大容量
• StaticQueue实现要点：
  • 关键操作：
    进队列：
    m_space[m_rear] = e;
m_rear = (m_rear + 1) % N;
    出队列：
    m_front = (m_front + 1) % N;
  • 队列的状态：
    队空：(m_length == 0) && (m_front == m_rear)
    队满：(m_length == N) && (m_front == m_rear)

StaticQueue.h

#ifndef STATICQUEUE_H
#define STATICQUEUE_H

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

namespace DTLib
{

template < typename T, int N >
class StaticQueue : public Queue<T>
{
protected:
    T m_space[N];
    int m_front;
    int m_rear;
    int m_length;
public:
    StaticQueue();
    void add(const T& e);
    void remove();
    T front() const;
    void clear();
    int length() const;
    int capacity() const;
};

template <typename T, int N >
StaticQueue<T, N>::StaticQueue()
{
    m_rear = 0;
    m_front = 0;
    m_length = 0;
}

template <typename T, int N >
void StaticQueue<T, N>::add(const T& e)
{
    if( m_length < N )
    {
        m_space[m_rear] = e;
        m_rear = ( m_rear + 1 ) % N;
        ++m_length;
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "Not space add queue...");
    }
}

template <typename T, int N >
void StaticQueue<T, N>::remove()
{
    if( m_length > 0 )
    {
        m_front = (m_front + 1) % N;
        --m_length;
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "Not element remove queue...");
    }
}

template <typename T, int N >
T StaticQueue<T, N>::front() const
{
    if( m_length > 0 )
    {
        return m_space[m_front];
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "Not element remove queue...");
    }
}

template <typename T, int N >
void StaticQueue<T, N>::clear()
{
    m_rear = 0;
    m_front = 0;
    m_length = 0;
}

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

template <typename T, int N >
int StaticQueue<T, N>::capacity() const
{
    return N;
}


}

#endif // STATICQUEUE_H

5. 小结

• 队列是一种特殊的线性表，具有先进先出的特征
• 队列只允许在线性表的两端进行操作，一端进，一端出
• StaticQueue使用原生数组作为内部存储空间
• StaticQueue的最大容量由模板参数决定
• StaticQueue采用循环计数法提高队列操作的效率

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