C语言中栈的实现及操作详细讲解

栈大家都知道是按照后进先出的规则处理数据的，其实栈的实现并不难，如果你了解基本数据结构中的线性表，那么栈对你来说已经很简单了，因为栈受限于线性表的基本操作，可以说栈的基本操作是线性表的子集，线性表分为顺序表与链表，因此栈也分为顺序栈与链栈，顺序顾名思义就是数据元素的物理地址都相邻，而链栈不连续，其实就相当于单链表，操作简单。下面就介绍两种栈的实现。
一、顺序栈。
看一下示意图：
顺序栈示意图
从示意图可以看出，它们数据物理地址在内存中是连续的，且栈顶指针始终指向栈顶，我们用一个结构体来定义栈，如下：
栈结构体定义
里面包含一个基址指针，还有一个用于指向栈顶的指针，基址指针在操作过程中始终指向栈底，栈底指针随着添加数据会变动。先来看一下顺序栈的初始化：
顺序栈的初始化
我们来看一下，初始化包含为栈分配初始内存空间，而后栈顶指针指向基址，表示没有添加任何数据，然后用size保存当前栈的长度。
我们知道栈的一般操作只有放入数据(push)与取出数据元素(pop)，所以相比一般顺序表的基本操作要简单的多，下面看一下数据进栈函数：
数据进栈
看这简短的代码，是不是很简单，里面只包含检测当前栈容量是否足够，不够那就重新分配，然后给栈顶指针重新赋值，因为重新分配后，基址可能变化，所以要重新赋值，然后增加当前栈容量size的值，下面就把新进栈的数据元素赋给栈顶指针，然后栈顶指针在加上1，重新指向新栈顶。
栈取出数据元素也很简单，下面看代码：
数据出栈函数
是不是更简单，主要代码就是检测当前栈是否为空，不为空的话，就取出元素，返回该元素，当然你也可以不这样，由于栈顶指针在栈顶，顾先向下移动一个单位，然后在取出该元素。
是不是很简单呢？
下面附上一个用顺序栈把十进制数化为二进制数的代码：
主函数
上面有个Empty_Stack函数，其实就是判断栈是否已空，代码如下：
判断栈是否已空
我们输入12，看看运行结果：
运行结果
上面就是顺序栈的介绍。
二、链栈：
链栈其实就是对单链表的操作，其实并不难，也很简单，跟顺序表比的话，就是不需要判断栈是否为满这种状态了，下面看一下链栈示意图：
链栈示意图
很容易看出，每一个结点都是结构体（跟单链表相同），为此我们先简单定义一个结构体，用于存放数据跟指向，如下：
链栈数据元素结点
其中ElemT是用#define定义的宏，可以是整型、字符型、结构体类型。指针next用于链接两个结点，用于遍历。
下面在定义链栈结构体：
                
                
链栈结构体
上面只有一个栈顶指针，当然你可以加上表示链表目前长度等成员，这里为方便就定义一个成员。
下面我们先看一下初始化函数：
初始
很简单，就一句，栈顶指针为空就行了。
进栈函数：
数据进栈函数
在这里，我们看到创建单链表时的大概操作，首先在内存中开辟一个内存空间，然后检查一下是否创建失败，当然你可以用返回值检查是否出错，然后我们结合一下上面示意图，首先新创建的结点必须先放入数据，然后在把新结点的指针指向上一个栈顶，实现连接，而后再把栈顶指针指向新开辟的结点。
出栈函数：
数据出栈函数
这里有一个问题，你之前数据进栈时用malloc函数申请了一片内存空间，在数据出栈时，应该将这片内存空间释放，所以先声明一个该结构体的局部指针变量，用于指向将要释放的内存空间，首先检测是否到栈底，到的话就返回1，下面我们将栈顶数据赋给*et，然后让目前栈顶指针赋给局部指针变量，然后让栈顶指针向下移动，指向下一个结点，最后用free函数释放不需要的结点空间，后返回0。
下面我们用链栈来把十进制数转换为二进制数，完整代码如下：
我们输入100，测试一下，运行结果如下：
运行结果
好了！关于栈的知识目前只介绍到这里，下面将继续介绍队列，数据结构堆等知识。