栈与队列(一)进出栈(含二转十进制栈应用)

一、栈相关定义（栈的顺序存储结构（最常用））

官方定义：栈是一个后进先出的线性表，它要求只在表尾进行删除插入操作（特殊线性表，只能在表尾操作）

空栈：栈中不含任何数据，此时栈顶就是栈底，然后数据从栈顶进入，顶底分离，栈容量变大。数据出栈时从栈顶弹出，栈顶下移，栈容量减小

二、（一幅图理解栈顶指针和栈底指针分别指向的位置（当然这个指向只是我这里使用的方法））

typedef struct{  ElemType *base; //栈底指针  ElemType *top;  //栈顶指针  int maxsize;  //当前可使用最大容量}sqStack;
三、创建一个栈
#define stacksize 100 //初始化栈是100个空间initStack(sqStack *s){  s->base=(ElemType *)malloc(stacksize * sizeof(ElemType));//申请空间  if(!s->base) //看是否申请成功     exit(0);  s->top=s->base; //最开始栈顶就是栈底  s->maxsize=stacksize;//可用空间100}
四、入栈操作（向栈中存放数据）（在栈顶进行，每次向栈中压入一个数据，top指针+1,直到栈满）
void Push(sqStack *s,ElemType e){  if(s->top-s->base>=s->maxsize){//判断是否栈大小大于最大容量      return;  }  *(s->top)=e;//放入数据  s->top++; //栈顶容量增加}
五、出栈操作（栈顶取出数据，栈顶指针下移，容量减1）
void Pop(sqStack *s,ElemType *e){  if(s->top==s->base){//栈已空了    return;  }  *e=*--(s->top); //先将指针s->top减1（位置的变化）后再取出具体数据内容,再赋值给e。。。因为top指针指的位置是栈顶(可以想象本来栈顶和栈底指向同一位置，然后一个元素进入顶底分离，栈顶指向的位置是没有元素的，因为最后一步总要s->top++，所以这里要取最后一个元素，首先得让栈顶top指向这个元素，所以向前移动以为即--)}
五、清空一个栈（就是将元素全部报废，不是销毁）（只要将s->top的内容赋值为s->base即可s->top等于s->base就表明栈空了）
ClearStack(sqStack *s)(这个操作其实里面数据还是存在，只是我们看不到了，因为我们改变了指针的指向){  s->top=s->base;}
六、销毁一个栈
DestroyStack(sqStack *s){  int i,len;  len=s->maxsize;//先得到这个栈的容量  for(i=0;i<len;i++){ //迭代一个一个释放掉内存，free用到stdlib.h头文件   free(s->base);   s->base++;  }  s->base=s->top=NULL;  s->maxsize=0;}七、计算栈的当前容量（就是计算栈中元素的个数，因此只要返回s.top-s.base即可）（注意：S.top-s.base（不是指针指针是->）两个地址相减就是中间元素的个数，但不能相加）（注意：栈的最大空间s.maxsize是该栈占据内存空间的大小，与栈的当前容量（当前存放了多少数据）不是一个概念）
int StackLen(sqStack s){  return(s.top-s.base);}
八、实例：二进制转化为十进制（栈的思想，后进先出）
/*************************************************************************    > File Name: 栈.c    > Author: geeker    > Mail: 932834897@QQ.com    > Created Time: 2017年02月04日 星期六 20时16分15秒 ************************************************************************/#include<stdio.h>#include <stdlib.h>#include "math.h"#define stacksize 20typedef char ElemType;//如果int就会把输入的数据当成整型，char可以以ASCII存在typedef struct{    ElemType *base;    ElemType *top;    int maxsize;}sqStack;void InitStack(sqStack *s)//初始化{    s->base=(ElemType *)malloc(stacksize * sizeof(ElemType));    if(!s->base)        exit(0);    s->top=s->base;    s->maxsize=stacksize;}void Push(sqStack *s,ElemType e)//压栈{    if(s->top-s->base>=s->maxsize)        return;    *(s->top)=e;    s->top++;}void Pop(sqStack *s,ElemType *e)//出栈{    if(s->top==s->base)        return;    *e=*--(s->top);}int StackLen(sqStack s)//(看清s不是指针),计算当前容量{    return(s.top-s.base);//点是结构不是指针}int main(){    ElemType c;    sqStack s;    int len,i,sum=0;    InitStack(&s);    PRintf("请输入二进制数，输入#符号表示结束!/n");    scanf("%c",&c);    while(c!='#'){//遇见#停止        Push(&s,c);//函数Push中s是指针，所以这里传地址        scanf("%c",&c);    }    getchar();//把‘/n’从缓冲区去掉    len=StackLen(s);    printf("栈的当前容量是%d/n",len);    for(i=0;i<len;i++){        Pop(&s,&c);//Pop函数中元素形参用指针，所以我们这里c传地址给Pop        sum+=(c-48)*pow(2,i);    }    printf("转化为十进制数是：%d/n",sum);    return 0;}