本文原创

用动态数组实现了一个非常简陋但却比较实用的循环队列模板，提供的接口和 STL 的基本一样。

#ifndef __CIRCULAR_QUEUE_HPP__
#define __CIRCULAR_QUEUE_HPP__

#include <assert.h>

namespace std {

template <typename T>
class CircularQueue
{
public:
    CircularQueue(size_t size) : _front(1), _rear(0), _size(size) { _array = new T[_size]; }
    ~CircularQueue() { delete []_array; }

    void clear()
    {
        _front = 1;
        _rear = 0;
    }
    size_t size()
    {
        return (_rear + 1 + _size - _front) % _size;
    }

    bool is_full() { return (_rear + 2) % _size == _front; }
    bool is_empty() { return (_rear + 1) % _size == _front; }

    void push(T value)
    {
        assert( is_full() == false );
        _rear = (_rear + 1) % _size;
        _array[_rear] = value;
    }
    void pop()
    {
        assert( is_empty() == false );
        _front = (_front + 1) % _size;
    }

    T front()
    {
        assert( is_empty() == false );
        return _array[_front];
    }
    T back()
    {
        assert( is_empty() == false );
        return _array[_rear];
    }
private:
    size_t _front;
    size_t _rear;
    size_t _size;
    T *_array;
};

}
#endif

用单链表实现了一个链式队列模板，提供的接口和 STL 的基本一样。