04栈和队列（特殊的线性表）

1.栈

1.栈

栈：栈是限定仅在表尾进行插入和删除操作的特殊的线性表。线性表按照存储结构分有顺序存储结构实现的顺序表和链式存储结构实现的链表。因此栈也有顺序存储结构实现的栈和链式存储结构实现的栈。

2.栈的顺序存储结构及实现

可扩容栈的顺序存储结构及其简单实现：

#pragma once
#ifndef _SQSTACK_H
#define _SQSTACK_H

#include <cassert>  //for assert()

/*
*   @brief a brief stack is implemented 
*   @param _Tp the type of element
*/
template<typename _Tp>
class SqStack
{
private:
    typedef _Tp value_type;
    typedef const value_type& const_reference;
    typedef value_type& reference;
    typedef value_type* pointer;

private:
    //获取容量
    inline size_t getCapacity()const
    {
        return defaultSpace;
    }
    //扩容
    void addSpace();
    typedef struct stack
    {
    public:
        pointer _data ;     //指向存放数据元素的数组的指针
        size_t _size = 0;   //当前栈的有效元素
        int top = -1;       //指示栈顶元素的指针

        stack();
    }stack;

    stack _stack;
    static size_t defaultSpace ;    //静态成员可以当作数组下标
    //const static size_t defaultSpace = 4;

public:

    SqStack();
    ~SqStack();
    bool push(const value_type& elem);  //压栈
    bool pop(reference elem);       //弹栈
    const_reference getTop()const;      //获取栈顶元素
    bool isFull();                      //判断栈满
    bool isEmpty();                     //判断栈空

    //栈的容量
    inline size_t capacity()const
    {
        return getCapacity();
    }

    //当前栈的有效元素个数
    inline size_t size()const
    {
        return this->_stack._size;
    }
};

//对于类外面定义类常量
template<typename _Tp>
size_t SqStack<_Tp>::defaultSpace = 4;


template<typename _Tp>
SqStack<_Tp>::stack::stack()
{
    this->_data = new value_type[defaultSpace];
    //static_assert(this->_data != nullptr, "the memory is not allocated rightly");
    assert(this->_data);
}
template<typename _Tp>
void SqStack<_Tp>::addSpace()
{
    
    //下面这个temp变量不能为static的，如果是一个静态变量则
    //它的内存会在程序结束时才释放。并且第二次扩容时赋值失败
    //调试了好久才发现
    //记录下先前数组的默认容量
    size_t temp = this->defaultSpace;
    this->defaultSpace = defaultSpace * 2;
    std::cout << defaultSpace << std::endl;
    //分配一块是原来两倍的内存
    pointer _newData = new value_type[defaultSpace];
    assert(_newData != nullptr);
    //初始化一块数据
    memset(_newData,0,sizeof(value_type) * defaultSpace);
    //拷贝原来的数据
    memcpy(_newData,this->_stack._data,temp * sizeof(value_type));
    //释放旧的内存
    delete[]this->_stack._data;
    //将数据存储的新地址赋给_data
    this->_stack._data = _newData;
    _newData = nullptr;

}
template<typename _Tp>
SqStack<_Tp>::SqStack()
{

}

template<typename _Tp>
SqStack<_Tp>::~SqStack()
{
    if (_stack._data)
    {
        delete[]_stack._data;
        _stack._data = nullptr;
    }
    std::cout << "end" << std::endl;
}

template<typename _Tp>
bool SqStack<_Tp>::push(const value_type& elem)
{
    //如果栈已满则扩容
    if (isFull())
    {
        addSpace();
    }
    _stack._data[++ (this->_stack.top)] = elem;
    this->_stack._size++;
    return true;
}

template<typename _Tp>
bool SqStack<_Tp>::pop(reference elem)
{
    if (isEmpty())
    {
        return false;
    }
    elem = this->_stack._data[_stack.top--];
    this->_stack._size--;
    return true;
}

template<typename _Tp>
const _Tp & SqStack<_Tp>::getTop()const
{
    size_t index = _stack.top;
    return _stack._data[index];
}

template<typename _Tp>
bool SqStack<_Tp>::isFull()
{
    return size() == capacity();
}

template<typename _Tp>
bool SqStack<_Tp>::isEmpty()
{
    return  size() == 0;
}

#endif  //!_SQSTACK_H

这里只测试基础类型，如需测试用户自定义类型则需在头文件中再实现一些基础功能。测试程序如下：

#include <iostream>
#include "SqStack.h"

int main()
{
    SqStack<int>obj;

    //压栈
    obj.push(100);
    obj.push(200);
    obj.push(300);
    obj.push(400);
    obj.push(500);  //扩容成功
    obj.push(600);
    obj.push(700);
    obj.push(800);
    obj.push(900);

    //获取栈顶元素
    std::cout << obj.getTop() << std::endl;

    //获取有效元素个数
    size_t size = obj.size();
    std::cout << "size:" << size << std::endl;

    //出栈
    for (size_t i = 0 ; i < size ; ++ i)
    {
        int temp = 0;
        obj.pop(temp);
        std::cout << temp << std::endl;
    }

    return 0;
}

//运行结果
//8
//16
//900
//size:9
//900
//800
//700
//600
//500
//400
//300
//200
//100
//end

3.共享栈

共享栈：用一个数组来两个相同数据类型的栈。做法即为：一个数组有两个端点，让一个栈的栈底为数组的开始端即数组下标为0处，另一个栈底为数组的末端即数组下标为数组长度n-1处。这样如果两个栈增加元素就是两端点向中间延申。
共享栈的使用场景：通常当两个相同数据类型的栈的空间需求有相反关系时，即一个栈在增长另一个栈在缩短。这样使用两栈共享空间存储才有意义，不然两个栈都在不停的增长很快，很快栈满溢出了。
共享栈简单实现：
在SharedStack.h中

#pragma warning( disable : 4290 )
#pragma once
#ifndef _SHAREDSTACK_H
#define _SHAREDSTACK_H 1

#include <iostream> //for cerr and endl
#include <cassert>  //for assert()

/*
*   @brief a briefly shared stack is implemented
*   @param _Tp the type of element
*/
template<typename _Tp>
class SqStack
{
private:
    typedef _Tp value_type;
    typedef const value_type& const_reference;
    typedef value_type& reference;
    typedef value_type* pointer;

private:
    //获取容量
    inline size_t getCapacity()const
    {
        return defaultSpace;
    }

    const static size_t defaultSpace = 4;   //数组的容量

    typedef struct stack
    {
    public:
        pointer _data;      //指向存放数据元素的数组的指针
        size_t _size = 0;   //当前栈的有效元素
        int top1 = -1;      //指示栈1栈顶元素的指针
        int top2 = defaultSpace;        //指示栈2栈顶元素的指针

        stack();
    }stack;

    stack _stack;

public:

    SqStack();
    ~SqStack();
    bool push(const value_type& elem,int stackNumber  = 1); //压栈
    bool pop(reference elem,int stackNumber = 1);           //弹栈
    const_reference getTop(int stackNumber = 1)const throw(const char*);        //获取栈顶元素
    bool isFull();                      //判断栈满
    bool isEmpty();                     //判断栈空

    //栈的容量
    inline size_t capacity()const
    {
        return getCapacity();
    }

    //当前栈的有效元素个数
    inline size_t size()const
    {
        return this->_stack._size;
    }
};

template<typename _Tp>
SqStack<_Tp>::stack::stack()
{
    this->_data = new value_type[defaultSpace];
    //static_assert(this->_data != nullptr, "the memory is not allocated rightly");
    assert(this->_data);
}

template<typename _Tp>
SqStack<_Tp>::SqStack()
{

}

template<typename _Tp>
SqStack<_Tp>::~SqStack()
{
    if (_stack._data)
    {
        delete[]_stack._data;
        _stack._data = nullptr;
    }
    std::cout << "end" << std::endl;
}

/*
*   @param elem the type of element
*   @param statckNumber mark that flag of stack ,1 mark that stack 1 and 2 mark that stack 2
*/
template<typename _Tp>
bool SqStack<_Tp>::push(const value_type & elem,int stackNumber)
{
    //如果栈已满则提示
    if (isFull())
    {
        std::cerr << "The stack is full and curent size is:" << this->size() << std::endl;
        return false;
    }
    
    if (stackNumber == 1)
    {
        this->_stack._data[++_stack.top1] = elem;
    }
    else if (stackNumber == 2)
    {
        this->_stack._data[--_stack.top2] = elem;
    }
    _stack._size++;
    return true;
}

template<typename _Tp>
bool SqStack<_Tp>::pop(reference elem,int stackNumber)
{
    if (isEmpty())
    {
        return false;
    }
    if (stackNumber == 1)
    {
        if (_stack.top1 == -1)
        {
            std::cerr << "the stack 1 is empty" << std::endl;
            return false;
        }
        elem = this->_stack._data[_stack.top1--];
    }
    else if(stackNumber == 2)
    {
        if (_stack.top2 == defaultSpace)
        {
            std::cerr << "the stack 2 is empty" << std::endl;
            return false;
        }
        elem = this->_stack._data[_stack.top2++];
    }
    this->_stack._size--;
    return true;
}

template<typename _Tp>
const _Tp& SqStack<_Tp>::getTop(int stackNumber)const throw(const char *)
{
    if (stackNumber == 1)
    {
        size_t index = _stack.top1;
        return _stack._data[index];
    }
    else if (stackNumber == 2)
    {
        return _stack._data[_stack.top2];
    }
    else
    {
        throw "The stackNumber is invarid ";
    }
}

template<typename _Tp>
bool SqStack<_Tp>::isFull()
{
    return size() == capacity();
}

template<typename _Tp>
bool SqStack<_Tp>::isEmpty()
{
    return  size() == 0;
}

#endif  //!_SHAREDSTACK_H

测试程序如下：

#include <iostream>
#include "SharedStack.h"

int main()
{
    SqStack<int>obj;
    
    obj.push(100,1);
    obj.push(400,2 );
    obj.push(200, 1);
    obj.push(300, 2);
    obj.push(500, 2);//共享栈已满，元素插入失败

    //获取栈1栈顶元素
    std::cout << obj.getTop(1) << std::endl;

    //获取栈2栈顶元素
    std::cout << obj.getTop(2) << std::endl;

    //获取两个栈总的有效元素个数
    size_t size = obj.size();
    std::cout << "size:" << size << std::endl;

    //出栈1
    for (size_t i = 0; i < size; ++i)
    {
        int temp = 0;
        bool flag = obj.pop(temp,1);
        if (flag)
        {
            std::cout << temp << std::endl;
        }
        else
        {
            break;
        }
    }

    //获取两个栈总的有效元素个数
    size_t size1 = obj.size();
    std::cout << "size:" << size1 << std::endl;

    //出栈2
    for (size_t i = 0; i < size1; ++i)
    {
        int temp = 0;
        bool flag = obj.pop(temp, 2);
        if (flag)
        {
            std::cout << temp << std::endl;
        }
        else
        {
            break;
        }
    }
    return 0;
}
//运行结果如下：
//The stack is fulland curent size is : 4
//200
//300
//size : 4
//200
//100
//the stack 1 is empty
//size : 2
//300
//400
//end

4.栈的链式存储结构定义及实现(简称链栈)

链式栈实现思想：栈只是栈顶做插入和删除操作，（即在链表的一端进行插入和删除操作，我们该想想将链表的哪一端作为栈顶比较好，在链表的头部进行头删头插还是链表的尾部进行尾插尾删呢），那么单链表实现起来更方便并且节约空间。栈顶需要栈顶指针指示栈顶元素，单链表也有头指针（链表有头结点的时候头指针指向头结点，没有头结点的时候指向第一个数据结点）。另外在设计单链表的过程中，我们通常附设一个头结点，那是因为让单链表的删除和插入操作算法可以统一，可以更方便的设计删除插入算法。所以将单链表的头部作为栈顶，并且不涉及头结点，直接用头指针作为栈顶指针。
链式栈的优缺点：
优点：
1.链式栈的长度没有限制。而顺序栈需要事先确定栈的容量
缺点：
1.链式栈的每个结点还需有指针域，这增加了一些开销。
总而言之，如果在栈的使用过程中元素变化不可预料，有时大有时小，那么最好使用链栈。反之使用顺序栈较好。

链式栈的简单实现：
LinkListStack.h中

#pragma warning( disable : 4290 )
#pragma once
#ifndef _LINKLISTSTACK_H
#define _LINKLISTSTACK_H 1

#include <cassert>
#include <iostream> //for cerr and endl

/*
*   @brief stack
*   @param _Tp the type of element
*/
template<typename _Tp>
class Stack
{
private:

    typedef _Tp value_type;
    typedef value_type* pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;

private:

    typedef struct Node
    {
    public:
        struct Node* next;  //一个结点的指针域
        value_type * elem;  //一个结点的数据域

        Node():next(nullptr),elem(nullptr)
        {

        }

        ~Node()
        {
            /*std::cout << "Hi" << std::endl;*/
        }

    }Node;

    size_t _length = 0;         //链栈的存储元素的数量
    Node* top;                  //栈顶指针指向栈顶元素

public:
    Stack();
    ~Stack();
    bool push(const_reference elem);    //压栈
    bool pop(reference elem);           //弹栈
    const_reference getTop()const throw(const char*);       //获取栈顶元素

    //判断栈空
    inline bool isEmpty()const
    {
        return this->size() == 0;
    }

    //获取当前栈的存储元素大小
    inline size_t size()const
    {
        return this->_length;
    }

};

template<typename _Tp>
Stack<_Tp>::Stack()
{
    //给栈顶指针动态分配内存
    top = new Node [sizeof(Node)];
    assert(top != nullptr);
}

/*
*程序退出前将栈中还未pop的结点的内存释放,不释放的话会造成内存泄露
*/
template<typename _Tp>
Stack<_Tp>::~Stack()
{
    if (this)
    {
        size_t size = this->size();
        for (size_t i = 0 ; i < size ; i ++ )
        {
            Node* workNode = this->top;
            this->top = workNode->next;
            delete[]workNode;
            workNode = nullptr;

        }
    }
}

//不知为何这里模板函数的返回类型为const_reference会报错：未定义该标识符
template<typename _Tp>
const _Tp&  Stack<_Tp>::getTop()const throw(const char *)
{
    if (isEmpty())
    {
        throw "The curent stack is empty";
    }
    return *(this->top->elem);
}

template<typename _Tp>
bool Stack<_Tp>::push(const_reference elem)
{
    //分配一个新结点
    Node* newNode = new Node [sizeof(Node)];
    if (!newNode)
    {
        std::cerr << "function push() error!the element is falsely pushed" << std::endl;
        return false;
    }
    //将元素插入
    newNode->elem = &const_cast<reference>(elem);
    //新结点的next域指向原来的栈顶元素
    newNode->next = this->top;
    //新结点成为栈顶元素
    this->top = newNode;
    //栈的存储元素大小加一
    this->_length++;

    return true;
}

template<typename _Tp>
bool Stack<_Tp>::pop(reference elem)
{
    if (isEmpty())
    {
        std::cerr << "function pop() error!the stack is empty" << std::endl;
        return false;
    }
    elem = *(this->top->elem);
    //栈顶结点
    Node* workNode = this->top; 
    //让原栈顶结点的后继结点成为新栈顶结点
    this->top = workNode->next;
    //释放原来的栈顶结点指向的内存
    delete[]workNode;
    //避免成为野指针
    workNode = nullptr;
    //栈的存储元素大小减一
    this->_length--;

    return true;

}


#endif  //!_LINKLISTSTACK_H

测试程序如下：

#include <iostream>
#include "LinkListStack.h"

int main()
{
    Stack<int>obj;

    std::cout << "size:" << obj.size() << std::endl;

    obj.push(100);
    obj.push(200);
    obj.push(300);
    obj.push(400);
    obj.push(500);

    size_t size = obj.size();
    std::cout << "size:" << size << std::endl;

    int topElem = obj.getTop();
    std::cout << "topElement:" << topElem << std::endl;


    for (size_t i = 0 ; i < size ; i ++)
    {
        int temp = 0;
        obj.pop(temp);
        std::cout << temp << std::endl;
    }

    return 0;
}
//运行结果如下：
//size:0
//size : 5
//topElement : 500
//500
//400
//300
//200
//100

在实现链式栈的过程中发现涉及到指针很容易造成资源泄露，野指针的问题。所以我们可以引入智能指针进行改进。比如在LinkListStack.h中，可以这么做：

#include <memory>
#include <boost/smartptr.hpp>

template<typename _Tp>
class Stack
{
private:
    typedef struct Node
    {
    public:
        struct Node* next;  //一个结点的指针域
        value_type * elem;  //一个结点的数据域

        Node():next(nullptr),elem(nullptr)
        {

        }

        ~Node()
        {
            /*std::cout << "Hi" << std::endl;*/
        }

    }Node;

    boost::shared_array<Node>top;  //智能指针对象含有指向栈顶元素的栈顶指针
    size_t size_t _length = 0;  //链栈的存储元素的数量
}

2.栈的应用

1.递归

递归函数：把一个直接调用自己或者通过一系列的调用语句间接的调用自己的函数称作递归函数。
例子：斐波那契数列实现的递归函数

//斐波那契数列的递归实现
int Fbi(int i)
{
    if (i < 2)
    {
        return i == 0 ? 0 : 1;
    }
    return Fbi(i - 1) + Fbi(i - 2);
}

在函数调用的前行阶段，对于每一层递归，函数的局部变量，参数值，返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量，参数值，返回地址都被弹出，恢复调用的状态。

2.四则表达运算式求值

后缀表达式：所有的符号都是要在运算数字的后面出现。我们把它也称为逆波兰表示（不需要括号的后缀表达法）。计算机是应用后缀表达式来计算结果的。计算规则：从左往右遍历表达式的每个符号和数字，遇到数字就进栈，遇到符号就将栈中的两个数字出栈进行运算，运算结果再次进栈，直到获得结果。

中缀表达式：我们平时所用的标准四则表达运算式就叫做中缀表达式。所有的运算符号都在数字的中间。既然计算机是应用后缀表达式来计算四则运算表达式的结果的，那么该如何将中缀表达式转化为后缀表达式就成为了重点。

中缀表达式转后缀表达式规则：从左到右遍历中缀表达式的每个符号和数字，如果是数字就输出，即成为后缀表达式的一部分。如果是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号则栈顶元素依次出栈输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
简单实现案例如下:

3.队列

1.队列的定义

队列(queue)：只允许在一端进行插入操作，在另一端进行删除操作的线性表。队列作为特殊的线性表，同样分顺序存储结构的顺序队列和链式存储结构的链式队列。

2.队列的顺序存储结构实现

我们先引入几个概念：
front指针：指向对头元素
rear指针：指向队尾元素
第一步考虑：预先分配一段连续存储空间的数组，数组下标为0的一端对头。入队操作就是在队尾追加元素，因不需要移动元素，所以时间复杂度为O(1)。但是出队操作是在对头，对头后的元素都得向前移动，来保证数组下标为0的位置不空。此时时间复杂度为O(n)，对于队列元素过多，这么做性能也是不高的。因此我们不用这种。

第二步考虑：为啥一定要将对头保持在数组下标为0的位置呢？这样每次出队，对头后的元素将要向前移动，效率明显是不高的。因此当有元素出队时，front指针也向后移动。但是问题又来了，当有元素在出队有元素在入对，rear指针已经到达数组尾部，这是却不能继续入队了。但数组下标为0的位置却可能还没满，造成“假溢出”的情况。

第三步考虑：当有元素在出队有元素在入对，rear指针已经到达数组尾部，再继续入队时，如果对头不满，则rear指针指向数组下标为0的位置。这也是要说的循环队列。

循环队列：头尾相接的顺序存储结构。循环队列来实现顺序队列是可行的，但是问题又来了，判断这种队列对空的条件是 rear指针 = front指针，对满的条件却也是rear指针 = front指针容易混淆。第一种解决办法是：设置一个变量标志位flag，对空时flag = 0，对满时flag = 1.第二种解决方法：队列空时条件是front = flag,队列为满时我们保留一个元素的空间，也就是说队列满时，数组中还有一个空闲单元。
在第二种方法下可以推导出两个公式：队列满的条件为（rear + 1） % QueueSize(预先分配的队列容量) = front;计算队列的长度：(rear - front + QueueSize) % QueueSize;

第二种解决方法下的循环队列的简单实现：

#pragma once
#ifndef _CIRCLEQUEUE_H
#define _CIRCLEQUEUE_H
 
#include <cassert>  //for assert()
#include <iostream> //for cerr
/*
*   @brief 循环队列的简单实现
*   @_Tp 元素类型
*/
template<typename _Tp>
class SqQueue
{
private:

    typedef _Tp value_type;
    typedef value_type* pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;

private:
    typedef struct Queue
    {
        pointer data;               //指向数据的指针
        size_t front = 0;           //队头指针
        size_t rear = 0;            //队尾指针
        size_t _size = 0;           //队列里的元素数量

        Queue()
        {
            data = new value_type[sizeof(value_type) * defaultSpace];
            assert(data != nullptr);
        }

        ~Queue()
        {
            if (data)
            {
                delete[]data;
                data = nullptr;
            }
        }
    }Queue;

    static size_t defaultSpace; //队列的默认容量
    Queue _queue;

public:
    SqQueue();
    ~SqQueue();


    //获取队列元素大小
    inline size_t size()const
    {
        return this->_queue._size;
    }

    //获取队列容量
    inline size_t capacity()const
    {
        return defaultSpace;
    }

    //判断对满
    inline bool isFull()const
    {
        return (this->_queue.rear + 1) % defaultSpace == _queue.front;
    }

    //判断对空
    inline bool isEmpty()const
    {
        return size() == 0;
        //return this->_queue.rear == _queue.front;
    }
    bool inQueue(const_reference elem); //入队
    bool outQueue(reference elem);      //出队
    const_reference getFront();         //获取对头元素

};

template<typename _Tp>
size_t SqQueue<_Tp>::defaultSpace = 4;

template<typename _Tp>
SqQueue<_Tp>::SqQueue()
{

}

template<typename _Tp>
SqQueue<_Tp>::~SqQueue()
{

}

template<typename _Tp>
const _Tp& SqQueue<_Tp>::getFront()
{
    if (isEmpty())
    {
        throw "The curent queue is empty";
    }

    return this->_queue.data[_queue.front];
}

template<typename _Tp>
bool SqQueue<_Tp>::inQueue(const_reference elem)
{
    if (isFull())
    {
        std::cerr << "The curent queue is full" << std::endl;
        return false;
    }
    //元素入队
    this->_queue.data[_queue.rear] = const_cast<reference>(elem);
    //队尾往后移，如果队尾到了最后则转到数组下标为0的位置
    _queue.rear = (_queue.rear + 1) % defaultSpace;
    //队列元素加一
    _queue._size++;
    
    return true;
}

template<typename _Tp>
bool SqQueue<_Tp>::outQueue(reference elem)
{
    if (isEmpty())
    {
        std::cerr << "The curent queue is empty" << std::endl;
        return false;
    }
    elem = this->_queue.data[_queue.front];
    _queue.front = (_queue.front + 1) % defaultSpace;

    //队列元素减一
    _queue._size--;

    return true;
}
#endif  //!_CIRCLEQUEUE_H

当然上述案例中如果顺序栈已满，也是可以扩容的。测试程序如下：

#include <iostream>
#include "CircleQueue.h"

int main()
{
    SqQueue<int>queue;

    std::cout << "capacity:" << queue.capacity() << "size:" << queue.size() << std::endl;
    
    queue.inQueue(100);
    queue.inQueue(200);
    queue.inQueue(300);
    queue.inQueue(400); //未插入成功，表示保留了一个元素的空间
    
    size_t size = queue.size();
    std::cout << "size:" << size <<  std::endl;

    std::cout << "frontElement:" << queue.getFront() << std::endl;

    for (size_t i = 0 ; i < size ; i ++)
    {
        int temp = 0;
        queue.outQueue(temp);
        std::cout << temp << std::endl;
    }
    return 0;
}

//运行程序如下：
//capacity:4size:0
//The curent queue is full
//size : 3
//frontElement : 100
//100
//200
//300

循环队列的优缺点：
缺点：预先分配的内存不够存储进栈的元素
优点：相比于链队，实现更简单。在确定队列长度最大值的情况下建议用循环队列。

3.队列的链式存储结构及其实现

队列的链式存储结构：其实就是线性表的单链表，只不过在单链表的尾部插入在单链表的头部删除而已。简称为链队列。为了操作方便（空队时，头尾指针都指向头结点），我们将对头指针指向头结点，队尾指针指向终端结点。

链式队列的简单实现：

#pragma once
#ifndef _LINKQUEUE_H
#define _LINKQUEUE_H

#include <cassert>
#include <iostream>

/*
*   @brief 链队列的简单实现
*   @param _Tp 元素类型
*/

template<typename _Tp>
class LinkQueue
{
private:

    typedef _Tp value_type;
    typedef value_type* pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;

    typedef struct LinkNode
    {
    public:
        pointer _data = nullptr;                //一个结点的数据域
        struct LinkNode* _next = nullptr;       //一个结点的指针域

        LinkNode()
        {

        }
        ~LinkNode()
        {
    
        }
    }LinkNode;

    size_t _size = 0;               //链队列的元素大小
    LinkNode* _front;               //对头指针
    LinkNode* _rear;                //队尾指针

public:

    //链队列的元素大小
    inline size_t size()const
    {
        return _size;
    }

    //判断队空
    inline bool isEmpty()
    {
        return size() == 0;
    }

    LinkQueue();
    ~LinkQueue();
    bool inQueue(const_reference elem); //入队
    bool outQueue(reference elem);      //出队
    const_reference getFront()throw(const char*);           //获取对头元素

};

template<typename _Tp>
LinkQueue<_Tp>::LinkQueue()
{
    //为头结点分配内存,并且头指针指向头结点
    _front = new LinkNode[sizeof(LinkNode)];
    assert(_front != nullptr);
    //头指针与尾指针相等表示空链队列
    _rear = _front;
}

/*
*   释放资源包括头结点
*
*/
template<typename _Tp>
LinkQueue<_Tp>::~LinkQueue()
{
    if (this)
    {
        size_t lenght = this->size();

        for (size_t i = 0 ; i <= lenght; i ++)
        {
            LinkNode* temp = this->_front;
            this->_front = temp->_next;
            delete[]temp;
            temp = nullptr;
        }
    }
}

template<typename _Tp>
bool LinkQueue<_Tp>::inQueue(const_reference elem)
{
    LinkNode* newNode = new LinkNode[sizeof(LinkNode)];
    if (!newNode)
    {
        std::cerr << "The space are falsely allocated" << std::endl;
        return false;
    }
    //给新结点的两个域赋值
    newNode->_data = &const_cast<reference>(elem);
    newNode->_next = nullptr;
    //将新结点赋值给尾结点的后继
    this->_rear->_next = newNode;
    //新结点成为尾结点
    this->_rear = newNode;
    //链队元素加一
    this->_size++;

    return true;
}

template<typename _Tp>
bool LinkQueue<_Tp>::outQueue(reference elem)
{
    if (isEmpty())
    {
        std::cerr << "The queue is empty" << std::endl;
        return false;
    }
    //保存第一个结点的位置
    LinkNode* workNode = this->_front->_next;
    //将第一个结点的后继赋给第一个结点
    this->_front->_next = workNode->_next;
    elem = *workNode->_data;
    //如果待删除的第一个结点也是尾结点，则在删除后将尾结点指向头结点
    if (workNode == this->_rear)
    {
         _rear = this->_front;
    }
    //删除第一个结点
    delete[]workNode;
    workNode = nullptr;

    //链队元素减一
    this->_size--;

    return true;
}

template<typename _Tp>
const _Tp& LinkQueue<_Tp>::getFront()throw(const char*)
{
    if (isEmpty())
    {
        throw "The queue is empty";
    }
    //第一个数据结点的数据
    return *(this->_front->_next->_data);

}

#endif  //!_LINKQUEUE_H 

测试程序如下：

#include <iostream>
#include "LinkQueue.h"

int main()
{
    LinkQueue<int>queue;
        
    queue.inQueue(100);
    queue.inQueue(200);
    queue.inQueue(300);
    queue.inQueue(400);
    queue.inQueue(500);
    queue.inQueue(600);
        
    size_t size = queue.size();
    std::cout << "size:" << size <<  std::endl;
    
    std::cout << "frontElement:" << queue.getFront() << std::endl;
    
    for (size_t i = 0 ; i < size - 1 ; i ++)
    {
        int temp = 0;
        queue.outQueue(temp);
        std::cout << temp << std::endl;
    }
    return 0;
}

//运行结果如下：
//size:6
//frontElement : 100
//100
//200
//300
//400
//500

链队的优缺点：
优点：只要堆内存足够，链队的长度没有限制。相比于循环队列，可以不用预先分配一段连续内存的空间。
缺点：链队列的每个节点除数据域外还有一个指针域，会产生一些空间上的开销。虽然链队长度没有限制但是每次申请和释放结点也存在一些时间开销。
4.队列的应用
比如说依次点击window系统上的应用程序图标，window系统会更具点击顺序依次加载应用程序。队列的应用还有好多。

5.总结

这一节我们讲的是一种特殊的线性表（仅对插入和删除操作做了一些限制）：栈和队列。他们都可以利用线性表的顺序存储结构和链式存储结构来实现。
在利用顺序存储结构实现线性表时都有一个弊端：预先分配好的连续的空间不足够存储数据元素。因此如何最大化的利用预先分配好的空间成了问题。对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端做栈底的方法来让两个栈共享空间，这样可以最大化的利用数组空间。对于队列来说，引入循环队列将原本删除算法的时间复杂度为O(n)变为O(1)，并且解决假溢出的问题，也最大化的利用数组空间。
在利用链式存储结构实现线性表时应当合理选择单链表还是双链表或者循环链表，双向循环链表来实现。