大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

数据结构(07)_队列

1. .队列的概念和实现

1.1.队列的概念

队列是一种特殊的线性表,仅能在线性表的两端进行操作。

为灌南等地区用户提供了全套网页设计制作服务,及灌南网站建设行业解决方案。主营业务为做网站、成都网站制作、灌南网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!

  • -队头(front)取出数据元素的一端;
  • -队尾(rear)插入数据元素的一端。
    队列的特性:
    数据结构(07)_队列
    队列的常用操作:
    创建和销毁;出队和入队;清空队列;获取队首元素;获取队列长度
    数据结构(07)_队列
    队列声明(接口):
    template < typename T >
    class Queue
    {
    public:
    virtual void enqueue(const T& e) = 0;
    virtual void dequeue() = 0;
    virtual T front() const = 0;
    virtual void clear() = 0;
    virtual int length() const = 0;
    };

    1.2.StaticQueu

    顺序队列的实现:
    数据结构(07)_队列
    设计要点:
    类模板,使用原生数组作为队列 存储空间,使用模板参数决定队列的最大容量;

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

    注意事项:
    StaticQueue实现要点:(循环计数法) 提高队列操作的效率(本质上时循环队列)
    关键操作:

  • 入队: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最终实现:

    template < typename T, int N >
    class StaticQueue : public Queue
    {
    protected:
    T m_space[N];
    int m_front;
    int m_rear;
    int m_length;
    public:
    StaticQueue()   //O(1)
    {
        m_front = 0;
        m_rear = 0;
        m_length = 0;
    }
    
    void enqueue(const T& e)   //O(1)
    {
        if(m_length < N)
        {
            m_space[m_rear] = e;
            m_rear = (m_rear + 1) % N;
            m_length++;
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no space in current staticqueue...");
        }
    }
    
    void dequeue()   //O(1)
    {
        if(m_length > 0)
        {
            m_front = (m_front + 1) % N;
            m_length--;
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no element in current staticqueue...");
        }
    }
    
    T front() const   //O(1)
    {
        if(m_length > 0)
        {
            return m_space[m_front];
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no element in current staticqueue...");
        }
    }
    
    void clear()   //O(1)
    {
        m_front = 0;
        m_rear = 0;
        m_length = 0;
    }
    
    int length() const   //O(1)
    {
        return  m_length;
    }
    
    int capacity() const   //O(1)
    {
        return N;
    }
    
    bool is_empty()   //O(1)
    {
        return (m_length == 0) && (m_front == m_rear);
    }
    
    bool is_full()   //O(1)
    {
        return (m_length == N) && (m_front == m_rear);
    }
    };

    2.链式队列

    2.1.LinkQueue

    顺序队列的缺陷:当数据为类类型时,StaticQueue的对象在创建时,会多次调用元素类型的构造函数,影响效率。所以我们采用链式存储结构来实现队列。
    数据结构(07)_队列
    设计要点:
    1.类模板,继承自抽象父类Queue;
    2.在内部使用链式结构实现元素的存储
    3.只在链表的头部和尾部进行操作。
    数据结构(07)_队列
    LinkQueue声明:

    template 
    class LinkQueue : public Queue
    {
    protected:
    LinkList m_list;
    public:
    LinkQueue(){}
    void enqueue(const T& e)    //O(n)
    void dequeue()      //O(1)
    T front() const //O(1)
    void clear()        //O(n)
    int length() const  //O(1)
    };

    LinkQueue最终实现:

    template 
    class LinkQueue : public Queue
    {
    protected:
    LinkList m_list;
    public:
    LinkQueue(){}
    
    void enqueue(const T& e)    //O(n)
    {
        m_list.insert(e);
    }
    
    void dequeue()      //O(1)
    {
        if(m_list.length() > 0)
        {
            m_list.remove(0);
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no elemet in current LinkQueue...");
        }
    }
    
    T front() const //O(1)
    {
        if(m_list.length() > 0)
        {
            return m_list.get(0);
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "no elemet in current LinkQueue...");
        }
    }
    
    void clear()        //O(n)
    {
        while (m_list.length() > 0)
        {
            m_list.remove(0);
        }
    }
    
    int length() const  //O(1)
    {
        return m_list.length();
    }
    };

    LinkQueue中,入队操作由于只能操作队列的尾部(链表的最后位置),要进行遍历操作,所以时间复杂度为O(n),可以使用双向循环链表代替单链表来解决这个问题。


网站栏目:数据结构(07)_队列
路径分享:http://dzwzjz.com/article/ppcsde.html
在线咨询
服务热线
服务热线:028-86922220
TOP