seqQueue.hh

Go to the documentation of this file.

/****************************************************
 * @file seqQueue.hh
 * @author Guorui Wei (313017602@qq.com)
 * @brief 循环队列的定义和实现
 * @version 0.1
 * @date 2020-04-05
 * 
 * @copyright Copyright (c) 2020
 * 
 * See the file LICENSE in the top directory of this distribution for
 * more information.
 * 
 ****************************************************/
 
#ifndef __SEQQUEUE_HH__
#define __SEQQUEUE_HH__
 
#include "Queue.h"
#include <utility>
 
namespace Queue
{
 
template <typename T>
class seqQueue : public Queue<T>
{
public:
    typedef T value_type;                      
    typedef value_type &reference;             
    typedef const value_type &const_reference; 
    typedef size_t size_type;                  
 
private:
    value_type *_elem;
 
    size_type _maxSize;
 
    size_type _front, _rear;
 
    void doubleSpace();
 
public:
    seqQueue(size_type initSize = 10);
 
    virtual ~seqQueue();
 
    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>
seqQueue<T>::seqQueue(size_type initSize)
    : _elem(new value_type[initSize]), _maxSize(initSize), _front(0), _rear(0)
{
}
 
template <class T>
seqQueue<T>::~seqQueue()
{
    delete[] _elem;
}
 
template <class T>
bool seqQueue<T>::empty() const
{
    return _front == _rear;
}
 
template <class T>
typename seqQueue<T>::size_type seqQueue<T>::size() const
{
    return ((_rear >= _front) ? _rear - _front : _maxSize + _rear - _front);
}
 
template <class T>
typename seqQueue<T>::reference &seqQueue<T>::front()
{
    return _elem[(_front + 1) % _maxSize];
}
 
template <class T>
typename seqQueue<T>::const_reference &seqQueue<T>::front() const
{
    return _elem[(_front + 1) % _maxSize];
}
 
template <class T>
typename seqQueue<T>::reference &seqQueue<T>::back()
{
    return _elem[_rear];
}
 
template <class T>
typename seqQueue<T>::const_reference &seqQueue<T>::back() const
{
    return _elem[_rear];
}
 
template <class T>
void seqQueue<T>::push(const value_type &val)
{
    if (size() == _maxSize - 1) 
        doubleSpace();
 
    _elem[_rear = (_rear + 1) % _maxSize] = val;
}
 
template <class T>
void seqQueue<T>::push(value_type &&val)
{
    if (size() == _maxSize - 1) 
        doubleSpace();
 
    _elem[_rear = (_rear + 1) % _maxSize] = std::move(val);
}
 
template <class T>
void seqQueue<T>::pop()
{
    _front = (_front + 1) % _maxSize;
}
 
template <class T>
void seqQueue<T>::doubleSpace()
{
    value_type *old = _elem;
    _elem = new value_type[2 * _maxSize + 1];
 
    for (size_type i = 1; i <= size(); ++i)
        _elem[i] = old[(_front + i) % _maxSize];
    delete[] old;
 
    _front = 0;
    _rear = size();
    _maxSize = 2 * _maxSize + 1;
}
 
} // namespace Queue
 
#endif