Question

数据结构中栈和队列为什么要用指针

Answer 1

线性表一般包括链表和顺序表，即顺序储存结构和链式储存结构。

2：栈的基本组成

为什么适合采用顺序表作为链表？
1：栈的操作一般只在栈顶插入与删除相当于顺序表的尾插尾删，而顺序表对于尾插尾删十分方便，时间复杂度为 O(1)。

3：栈的分布操作及对应代码

栈的初始化：

在尝试写栈的初始化中，我们很容易将ps->a写成STDataType a;这将会导致扩容时指针a发生异常；在扩容时也没有真正的改变栈里面的指针a;

栈的摧毁：

 栈的销毁是直接销毁malloc所指向的内存，然而对于队列的销毁而言，队列是一个个销毁它们创建队列malloc的结点。

入栈：

 入栈时我们首先要判断的便是栈满的情况，当top与capacity相等时就要进行扩容，扩容时要记得先改变的是capacity,方便计算realloc开辟所需的内存空间；

入栈完成后对应栈里面的capacity，top的大小要进行改变，a指向的内存要进行更新；

如果没进行扩容的话，则直接进行栈的插入，size+1；

出栈：

 对于出栈而言，首先便是要考虑栈是否为空。对于栈的出栈可直接将top减去即可（在完成一系列出栈后我们可以通过StackDestroy进行销毁);

size减一后，对于后来的出栈也少一了一次循环机会。

判断栈为空与求栈顶元素：

它们和队列相似，求栈顶的元素或者是队列的元素，都要判断里面的元素是否为空。

但是相比队列，栈只有指向top位置的指针，因此通常只求栈的栈顶元素，而队列因为含有tail，head两个指向队尾队头的指针，因此可以更加方便的求队列的队头队尾元素。

栈的基本操作声明：

 二：队列

1：队列的基本组成

为什么队列适合链表？

对于队列而言，我们可以考虑采用链表或者是顺序表来实现。但对于顺序表而言，实现队列的头删时复杂度为O(n),显得更加麻烦，况且顺序表malloc也会造成内存性能的浪费。所以此时而言采用链表方式更为合适，但是我们要用head和tail记录头尾指针，对于多指针可以包装成一个结构体，也可防止二级指针的使用。

 队列的插入QueuePush

 由于在队列整个函数之中，只有当队列满时插入才需要创建结点，所以对于队列的插入而言，可将结点的创造于插入并入QueuePush代码中。

 对于队列的删除来说，首先考虑的便是队列不能为空。

还要考虑队列的删除有多种情况：

1：对于普通的队列删除，先创建新节点保留head之后的结点地址，然后再free，最后再将head移到新的对头当中。

2：对于内存的消除，尤其可能会造成野指针的情况，此时对于平常做题而言应当多注意边界情况。当删除到最后一个元素时，head等于NULL，然而tail却还是指向已经消除的内存了，有可能会造成野指针问题；

队头，队尾，判断为空：

 求队头，队尾元素要注意判断此队列为不为空！

队列的销毁：

1： 队列的销毁我们是采用循环的方式一个一个删除的，当队列删为空时，记得要将他们置为空！

队列的基本操作声明： 

三：栈与队列的声明总结：

1：栈和队列，本质上就是链表和顺序表的衍生操作，大部分都符合链表和顺序表的基本操作。但值得注意的时，栈和队列的基本组成构成形式却大为不同，我们写时可以先大概画出它们的基本构成元素再进一步展开。

2：再写队列的基本代码时，我们还认识了通过结构体将两个指针包装，再通过指向结构体的指针来改变结构体内的指针这一巧妙方式解决了二级指针的复杂应用。

3：写代码时一定要根据情况画图（定好变量的初始位置，基本过程，各种情况（含边界情况））。