CSDN的uu们，大家好呀！ 这里是C语言数据结构初阶的第五讲，我们要学习的内容是：栈。 ✈
基础概念
栈(Stack)是限定仅在表尾进行插入和删除操作的线性表。
允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称为LIFO结构。
栈的插入操作，叫做进栈，也称压栈，入栈。
栈的删除操作，叫做出栈，有的也叫做弹栈。如同弹夹中的子弹出夹。
这里就有一个问题啦？这个最先进栈的元素，是不是就只能是最先出栈呢？答案是不一定，要分析具体的情况。栈只对线性表插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素就行。
这里有一道小小的练习题可以尝试着做一下！
若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
这里分析了选项A，其他的选项也是同样分析，假设要按照选项这么出栈，分析需要怎样进栈即可！
正确答案：C
2. 顺序存储OR链式存储
大家很可能马上就会想到栈的顺序存储吧！用一个数组来充当栈这种数据结构！显然是将下标为0的一端作为栈底比较好，因为首元素都存储在栈底，变化最小，所以让他做栈底！
但是栈可不可以用链式存储嘞—-用链表来存储！显然是可以的。那么我们是用单链表还是双链表呢？有人可能会想：单链表的话，我定义一个tail指针指向链表的尾节点，tail指向的节点充当栈顶的元素。实现压栈过程的时间复杂度就是O(1)，但是要实现弹栈的话就必须遍历找到尾节点的前一个节点，这样的话时间复杂度就是O(N)了。这样不行，咱得用双链表，我就能在O(1)的时间复杂度实现压栈和弹栈的过程了！
其实用单链表也行哦！我们把单链表的头节点当作栈顶的元素，我们知道单链表的头插和头删都是O(1)的时间复杂度，这样就能很方便的实现压栈和弹栈了。
有关单链表的知识：
http://t.csdn.cn/emItq 有关双链表的知识：
http://t.csdn.cn/07jSN
由于双向链表的逻辑更加复杂，所以我们放弃选用双链表。那到底是选用数组还是单链表呢？
这里就得简单谈谈内存命中率的概念了。内存命中率是指计算机在进行数据操作时，需要访问内存的次数与总访问次数之比。我们知道CPU的读写速度是非常快的，相比于CPU内存的读写速度要慢很多！这个时候有个叫缓存的东东，可以理解为第三者，用来协调 CPU和内存读写的速度差。缓存要比内存小很多，但其读写速度介于两者之间！CPU对数据的操作需要先加载到缓存中。至于一次从内存中加载多少个字节不同的硬件大不相同。
CPU操作数据时，会先看数据是否在缓存中，不在的话则需要从内存中加载，由于顺序表是基于连续的内存块来实现的，每从内存中加载一次数据到缓存，则会加载多个数据，内存命中率就比较高。
相比之下，链表的每个节点的物理地址并不一定是连续的，从内存中加载一次，可能只会加载一个数据，内存的命中率比较低。并且加载到缓存中的数据还可能有一部分是没有用的，导致缓存污染的问题！
综上所述，我们会选择栈的顺序存储。
3. 函数接口一览
#include#include#include#include//数组时动态的，初始的大小为4#define INIT_STACK_SIZE 4//栈的数据类型typedef int STDataType;//栈的结构体，类比顺序表typedef struct Stack{ STDataType* a; //栈的顺序存储的数组 int top; //栈的top元素 int capacity; //数组的容量} ST;//初始化栈void StackInit(ST* st);//栈的销毁void StackDestory(ST* st);//压栈void StackPush(ST* st, STDataType x);//弹栈void StackPop(ST* st);//栈的大小int StackSize(ST* st);//栈是否为空bool StackEmpty(ST* st);//查看栈顶元素STDataType StackTop(ST* st);4.函数接口的实现
4.1 void StackInit(ST* st) 的实现
初始化栈需要我们先开辟一定空间的数组！并将更新capacity的值。因为此时栈中并没有任何元素，我们将top初始化为0，我们这里的top指向的是栈顶元素的下一个下标。当然你也可以将top初始化为-1，甚至是1，等等。只要你保证后续函数的实现能够符合栈的特性就行。
void StackInit(ST* st){ //断言防止出现空指针的解引用 assert(st); //用定义好的标识符初始化数组的大小 st->a = (STDataType*)malloc(sizeof(STDataType) * INIT_STACK_SIZE); if (!st->a) { //如果开辟空间失败，结束程序 perror("StackInit::malloc"); exit(-1); } //初始化capacity和top st->capacity = INIT_STACK_SIZE; st->top = 0;}4.2 void StackDestory(ST* st)的实现
栈的销毁只需要释放结构体里面的数组就行了！
void StackDestory(ST* st){ //断言，防止空指针 assert(st); //释放，置空 free(st->a); st->a = NULL; st->capacity = 0; st->top = 0;}4.3 void StackPush(ST* st, STDataType x) 的实现
因为我们的top指向的是栈顶元素的下一个下标，因此我们只需要令下标是top的位置的值为X，然后让top加一就行啦！但是还有一种特殊情况：当数组的容量capacity等于top时代表栈被填满了。这个时候我们需要对数组进行扩容！扩容我们选择扩充到原来的两倍！
void StackPush(ST* st, STDataType x){ //断言，防止出现空指针的解引用 assert(st); //如果栈是满的，扩容 if (st->top == st->capacity) { //扩充到原来的两倍大小 STDataType* new = (STDataType*)realloc(st->a, sizeof(STDataType) * st->capacity * 2); if (!new) { //如果返回空指针，说明扩容失败，结束程序 perror("StackPush::malloc"); exit(-1); } else { //扩容成功 st->a = new; //更新capacity st->capacity *= 2; } } //压栈 st->a[st->top] = x; //更新top st->top++;}4.4 void StackPop(ST* st)的实现
和顺序表的尾删类似，弹栈也是对数组进行逻辑上的删除。即让top减一即可！当然当栈中没有数据是不允许删除的！
void StackPop(ST* st){ //防止空指针的解引用 assert(st); //栈为空不允许删除数据 assert(st->top); //逻辑上的删除数据 st->top--;}4.5 int StackSize(ST* st)
不难发现，top就是栈中元素的个数！
int StackSize(ST* st){ assert(st); return st->top;}4.6 bool StackEmpty(ST* st)的实现
这个函数我们只需要判断top是否为0即可！
bool StackEmpty(ST* st){ assert(st); return st->top == 0;}4.7 STDataType StackTop(ST* st)
很显然，top-1指向的元素就是栈顶元素。当然栈中没有数据的话，是不允许访问栈顶元素的。
STDataType StackTop(ST* st){ assert(st); assert(st->top); return st->a[st->top - 1];}4.8 栈的“遍历”
为了维持栈这种数据结构的特性，我们是不能遍历存储栈中元素的数组的！想要遍历栈中的所有元素，我们需要访问栈顶元素一次，弹栈一次，直到栈为空！
int main(){ //建立一个栈 ST st; //栈的初始化 StackInit(&st); //压栈 StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); StackPush(&st, 6); //遍历栈中的数据，栈不为空，继续遍历 while (!StackEmpty(&st)) { //访问栈顶元素打印数据 printf("%d ", StackTop(&st)); //弹栈 StackPop(&st); } //销毁栈 StackDestory(&st); return 0;} 