栈
定义
栈Stack是一种后进先出（LIFO) 的数据结构，是线性表的一种具体形式，要求只在表尾进行删除pop和插入push的操作。
插入操作：push，进栈。
删除操作：pop，出栈
顺序存储结构
顺序存储结构：最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。数据从栈顶进入，容量变大，数据出栈时从栈顶弹出，整个栈的容量变小。
栈的代码定义
typedef int ElemType;
typedef struct
{
ElemType *base; //指向栈底
ElemType *top; //指向栈顶
int stackSize;
}sqStack;
创建一个栈
#define STACK_INIT_SIZE 100
initStack(sqStack *s)
{
s->base = (Elemtype *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!s->base)
exit(0);
s->top = s->base;//最开始，栈顶=栈底
s-<stackSize = STACK_INIT_SIZE;
}
入栈操作
#define STACKINCREMENT 10
Push(sqStack *s, ElemType e)
{
//判断栈是否满，增加空间
if(s->top - s->base >= s->stackSize)
{
s->base = (Elemtype *)realloc(s->base,(s->stackSize = STACKINCREMENT) * sizeof(ElemType));
if(!s->base)
exit(0);
s->top= s->base +s->stackSize;//设置栈顶
s->stackSize = s->stackSize + STACKINCREMENT;//重新设置栈的最大容量
}
*(s->top) = e;
s->top ++;
}
出栈操作
在栈顶取出数据，栈顶指针随之下移，容量–
Pop(sqStack *s, ElemType e)
{
//判断是否为空栈
if(s->top == s->base )
return;
*e = * --(s->top);//先减一再取出内容
}
清空栈
将栈的元素作废，但是本身物理空间并不发生改变。
将s->top的内容赋值为s->basw，表明为空，类似于格式化只是单纯的清空文件列表但是没有覆盖硬盘的道理。
代码也十分简单
ClearStack(sqStack *s)
{
s->top = s->base;
}
销毁栈
释放掉栈占据的物理内存空间
DestroyStack(sqStack *s)
{
int i,len;
len = s->stackSize;
for( i =0; i <len; i++)
{
free(s->base);
s->base ++;
}
s->base = s->top = NULL;
s->stackSize = 0;
}
计算栈的当前容量
只需要计算元素的个数
注意：在这里，栈的当前容量与最大容量stackSize不同，并不是一个概念.
int StackLen(sqStack s)
{
//两个地址相减得到的是元素（要除以地址的大小）
return (s.top - s.base);
}
例题
利用栈的数据结构特点，将二进制转换为十进制数
提示：转换公式为
XnXn-1…X3X2X1 = X1 *20 + X2 *21 + … + Xn *2(n-1)
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;
void InitStack(sqStack *s)
{
s->base = (Elemtype *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!s->base)
exit(0);
s->top = s->base;//最开始，栈顶=栈底
s-<stackSize = STACK_INIT_SIZE;
}
Push(sqStack *s, ElemType e)
{
//判断栈是否满，增加空间
if(s->top - s->base >= s->stackSize)
{
s->base = (Elemtype *)realloc(s->base,(s->stackSize = STACKINCREMENT) * sizeof(ElemType));
if(!s->base)
exit(0);
s->top= s->base +s->stackSize;//设置栈顶
s->stackSize = s->stackSize + STACKINCREMENT;//重新设置栈的最大容量
}
*(s->top) = e;
s->top ++;
}
Pop(sqStack *s, ElemType e)
{
//判断是否为空栈
if(s->top == s->base )
return;
*e = * --(s->top);//先减一再取出内容
s->stackSize --;
}
int StackLen(sqStack s)
{
//两个地址相减得到的是元素（要除以地址的大小）
return (s.top - s.base);
}
int main()
{
ElemType c;
sqStack s;
int len, i ,sum = 0;
printf("请输入二进制数，（#结束）:\n");
scanf("%c",&c);
while( c!= '#')
{
Push( &s,c);
scanf("%c",&c);
}
getchar();
//把回车的字符接收一下
len = StackLen(s);
//显示一下容量
printf("栈的当前容量为：%d\n",len);
for( i = 0;i <len; i ++)
{
Pop(&s, & c);
sum = sum + (c - 48 )* pow(2,i);
}
printf("转换的十进制为：%d\n"，sum);
return 0;
}
链式存储结构
简称栈链。
代码如下
typedef struct StackNode
{
ElemType data;
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count; //栈元素计数器
};
进栈操作
Status Push(LinkStack * s, ElemType e)
{
LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
p->data =e;
p->next = s->top;
s->top = p;
s->count ++;
return OK;
}
出栈操作
Status Pop(LinkStack * s, ElemType e)
{
LinkStackPtr p;
if(StackEmpty(*s))
return false;
*e = s->top->data;
p = s->top;
s->top = s->top->next;
free(p);
s->count --;
return OK;
}
逆波兰表达式
中缀表达式 （1-2）×（4 + 5）
逆波兰表示法 1 2 - 4 5 + *
过程：数字1和2进栈，遇到-弹出，运算之后进去，变成-1。之后4和5进去，遇到+弹出来计算，变成9放进去。之后又是×，弹出-1和9，计算之后为-9。-9为最终计算结果。