vecQueue.hh

Go to the documentation of this file.

/****************************************************
 * @file vecQueue.hh
 * @author Guorui Wei (313017602@qq.com)
 * @brief 队头位置固定的顺序队列的定义和实现
 * @version 0.1
 * @date 2020-04-06
 * 
 * @copyright Copyright (c) 2020
 * 
 * See the file LICENSE in the top directory of this distribution for
 * more information.
 * 
 ****************************************************/
 
#ifndef INCLUDE_VECQUEUE_HH_
#define INCLUDE_VECQUEUE_HH_
 
#include "Queue.h"
#include <utility>
 
namespace Queue
{
 
template <typename T>
class vecQueue : public Queue<T>
{
public:
    typedef T value_type;                      
    typedef value_type &reference;             
    typedef const value_type &const_reference; 
    typedef size_t size_type;                  
private:
    size_type _maxSize;
 
    value_type *_data;
 
    size_type _rear;
 
    void doubleSpace();
 
public:
    vecQueue(size_type initSize = 10);
 
    virtual ~vecQueue();
 
    virtual bool isEmpty() const
    {
        return empty();
    }
 
    virtual void enQueue(const_reference &x)
    {
        push(x);
    }
 
    virtual value_type deQueue()
    {
        value_type retVal = front();
        pop();
        return retVal;
    }
 
    virtual value_type getHead() const
    {
        return front();
    }
 
    bool empty() const;
 
    size_type size() const;
 
    reference &front();
 
    const_reference &front() const;
 
    reference &back();
 
    const_reference &back() const;
 
    void push(const value_type &val);
 
    void push(value_type &&val);
 
    void pop();
};
 
template <class T>
vecQueue<T>::vecQueue(size_type initSize)
    : _maxSize(initSize), _data(new value_type[initSize]), _rear(0)
{
}
 
template <class T>
vecQueue<T>::~vecQueue()
{
    delete[] _data;
}
 
template <class T>
bool vecQueue<T>::empty() const
{
    return !_rear;
}
 
template <class T>
typename vecQueue<T>::size_type vecQueue<T>::size() const
{
    return _rear;
}
 
template <class T>
typename vecQueue<T>::reference &vecQueue<T>::front()
{
    return _data[0];
}
 
template <class T>
typename vecQueue<T>::const_reference &vecQueue<T>::front() const
{
    return _data[0];
}
 
template <class T>
typename vecQueue<T>::reference &vecQueue<T>::back()
{
    return _data[_rear - 1];
}
 
template <class T>
typename vecQueue<T>::const_reference &vecQueue<T>::back() const
{
    return _data[_rear - 1];
}
 
template <class T>
void vecQueue<T>::push(const value_type &val)
{
    if (_rear == _maxSize)
        doubleSpace();
 
    _data[_rear++] = val;
}
 
template <class T>
void vecQueue<T>::push(value_type &&val)
{
    if (_rear == _maxSize)
        doubleSpace();
 
    _data[_rear++] = std::move(val);
}
 
template <class T>
void vecQueue<T>::pop()
{
    --_rear;
    for (size_type i = 0; i < _rear; ++i)
        _data[i] = _data[i + 1];
}
 
template <class T>
void vecQueue<T>::doubleSpace()
{
    value_type *old = _data;
    _data = new value_type[_maxSize = 2 * _maxSize + 1];
    for (size_type i = 0; i < _rear; ++i)
        _data[i] = old[i];
    delete[] old;
}
 
} // namespace Queue
 
#endif /* INCLUDE_VECQUEUE_HH_ */