C语言中的Stack源码分析

[梦断畅通]

  栈又名堆栈，是一种操作受限的线性表，仅能在表尾进行插入和删除操作。

  栈最大的特点是先进后出，就好比我们往桶里面放盘子，放的时候都是从下往上一个一个放，此时就相当于入栈，取的时候只能从上往下一个一个取，此时就好比出栈，这个比喻并非十分恰当，比如拿盘子的时候只是习惯从上面开始拿，也可以从中间拿，而栈的话是只能操作最上面的元素，这样比喻只是为了便于了解。

  当某个数据集合只涉及在一端插入和删除数据，并且满足先进后出的特性时，我们就应该首选“栈”这种数据结构。

  栈的实现：栈的实现方式有两种，一种是基于数组实现的顺序栈，另一种是基于链表实现的链式栈。它的主要操作也就两个，即入栈和出栈。


  顺序栈：基于数组实现，就面临着数组大小固定、扩容成本大的问题。空间复杂度是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

  链式栈：链式栈也是一种数据存储结构，它能够通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。