linkQueue.hh

Go to the documentation of this file.

/****************************************************
 * @file linkQueue.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 INCLUDE_LINKQUEUE_HH_
#define INCLUDE_LINKQUEUE_HH_
 
#include "Queue.h"
#include <utility>
 
namespace Queue
{
 
template <typename T>
class linkQueue : Queue<T>
{
public:
    typedef T value_type;                      
    typedef value_type &reference;             
    typedef const value_type &const_reference; 
    typedef size_t size_type;                  
 
private:
    struct node
    {
        value_type _data;
 
        node *_next;
 
        node(const value_type &data = value_type(), node *next = nullptr)
            : _data(data), _next(next) {}
 
        node(value_type &&data, node *next = nullptr)
            : _data(std::move(data)), _next(next) {}
 
        ~node() = default;
    };
 
    node *_front;
 
    node *_rear;
 
    size_type _size;
 
public:
    linkQueue();
 
    virtual ~linkQueue();
 
    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>
linkQueue<T>::linkQueue()
    : _front(nullptr), _rear(nullptr), _size(0)
{
}
 
template <class T>
linkQueue<T>::~linkQueue()
{
    node *delPtr = _front;
    while (_front)
    {
        delPtr = _front;
        _front = _front->_next;
        delete delPtr;
    }
}
 
template <class T>
bool linkQueue<T>::empty() const
{
    return _front == nullptr;
}
 
template <class T>
typename linkQueue<T>::size_type linkQueue<T>::size() const
{
    return _size;
}
 
template <class T>
typename linkQueue<T>::reference &linkQueue<T>::front()
{
    return _front->_data;
}
 
template <class T>
typename linkQueue<T>::const_reference &linkQueue<T>::front() const
{
    return _front->_data;
}
 
template <class T>
typename linkQueue<T>::reference &linkQueue<T>::back()
{
    return _rear->_data;
}
 
template <class T>
typename linkQueue<T>::const_reference &linkQueue<T>::back() const
{
    return _rear->_data;
}
 
template <class T>
void linkQueue<T>::push(const value_type &val)
{
    // 向空队列入队
    if (!_front)
        _rear = _front = new node(val);
    else
        _rear = _rear->_next = new node(val);
    ++_size;
}
 
template <class T>
void linkQueue<T>::push(value_type &&val)
{
    // 向空队列入队
    if (!_front)
        _rear = _front = new node(std::move(val));
    else
        _rear = _rear->_next = new node(std::move(val));
    ++_size;
}
 
template <class T>
void linkQueue<T>::pop()
{
    node *delPtr = _front;
    _front = _front->_next;
    delete delPtr;
    --_size;
 
    // 最后一个元素出队
    if (!_front)
        _rear = nullptr;
}
 
} // namespace Queue
 
#endif /* INCLUDE_LINKQUEUE_HH_ */