欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列(c++实现)

程序员文章站 2024-02-11 23:24:34
...

  队列的特点是先进先出,跟栈的c++实现类似,队列的c++实现同样有两种方式:
队列(c++实现)
  Queue是一个接口类,封装了队列相关的所有操作:

//Queue.h
#ifndef __QUEUE_H__
#define __QUEUE_H__

#include <exception>

template<typename T>
class Queue
{
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__ */

  队列数据结构其实就是前面讲的环形缓冲区,核心是两个循环计数的指针分别表示读/写位置
  队列空间是静态分配的数组:

//StaticQueue.h
#ifndef __STATICQUEUE_H__
#define __STATICQUEUE_H__

#include "Queue.h"

template <typename T, int N>
class StaticQueue : public Queue<T>
{
protected:
    T m_space[N];
    int m_write;
    int m_read;
    int m_length;

public:
    StaticQueue() : m_write(0), m_read(0), m_length(0)
    {
    }

    int capacity() const
    {
        return N;
    }

    void add(const T& e)
    {
        if (m_length < N)
        {
            m_space[m_write] = e;
            m_write = (m_write + 1) % N;
            ++m_length;
        }
        else
            throw(std::runtime_error("No space in current queue"));
    }

    void remove()
    {
        if (m_length > 0)
        {
            m_read = (m_read + 1) % N;
            --m_length;
        }
        else
            throw(std::runtime_error("No element in current queue"));
    }

    T front() const
    {
        if (m_length > 0)
            return m_space[m_read];
        else
            throw(std::runtime_error("No element in current queue"));
    }

    void clear()
    {
        m_write = 0;
        m_read = 0;
        m_length = 0;
    }

    int length() const
    {
        return m_length;
    }
};

#endif /* __STATICQUEUE_H__ */

  测试:

//main.cpp
int main(void)
{
    StaticQueue<int, 6> queue;

    for (int i = 0; i < 6; ++i)
    {
        queue.add(i);
    }

    while (queue.length() > 0)
    {
        std::cout << queue.front() << std::endl;
        queue.remove();
    }

    getchar();
    return 0;
}

  用链表实现队列空间,这里采用Linux内核链表来实现:

//LinkQueue.h
#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__

#include "linux_list.h"
#include "Queue.h"

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

    list_head m_head;
    int m_length;

public:
    LinkQueue()
    {
        m_length = 0;
        INIT_LIST_HEAD(&m_head);
    }

    void add(const T& e)
    {
        Node_t *node = new Node_t();
        if (node)
        {
            node->value = e;
            list_add_tail(&node->head, &m_head);
            ++m_length;
        }
        else
            throw(std::runtime_error("No memory in create queue"));
    }

    void remove()
    {
        if (m_length > 0)
        {
            list_head* toDel = m_head.next;
            list_del(toDel);
            --m_length;
            delete list_entry(toDel, Node_t, head);
        }
        else
            throw(std::runtime_error("No element in current queue"));
    }

    T front() const
    {
        if (m_length > 0)
        {
            return list_entry(m_head.next, Node_t, head)->value;
        }
        else
            throw(std::runtime_error("No element in current queue"));
    }

    void clear()
    {
        while (m_length > 0)
            remove();
    }

    int length() const
    {
        return m_length;
    }

    ~LinkQueue()
    {
        clear();
    }

};

#endif /* __LINKQUEUE_H__ */