目錄
棧（Stack）棧頂（top）棧底（bottom）空棧（不含任何元素）
創建棧?
入棧操作
出棧操作
銷毀一個棧
計算棧的當前容量
實例分析
棧的插入操作叫做進棧（Push），或者稱為壓棧、入棧。
棧的刪除操作叫做出棧（Pop），或者稱為彈棧。
棧又稱為先進后出（last in first out）的后進先出原則，稱為后進先出的線性表（LIFO）。?
棧的本質上也是一個線性表，線性表有兩種存儲形式，那么棧也有分為棧的順序存儲結構和棧的鏈式存儲結構。
最開始棧中不含有任何數據，叫做空棧，此時棧定就是棧底。然后數據從棧頂進入，棧頂棧底分離，整個棧的當前容量變大。數據出棧時，從棧頂移出，棧頂下一，整個棧的當前容量變小。
棧的順序存儲結構：
typedef struct
{ElemType *base;ElemType *top;int stacksize;}sqStack;?這里定義了一個順序存儲的棧，它包含了三個元素：base，top，stacksize。其中base是指向棧底的指針變量，top是指向棧頂的指針變量，stacksize指示棧的當前可使用的最大容量。
創建棧?
#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;} 入棧操作
#include <stdlib.h>
#define STACKINCREMENT 10Push(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++; } 出棧操作
出棧操作就是在棧頂取出數據，棧頂指針隨之下移的操作。
每當從棧內彈出一個數據，棧的當前容量就-1.
Pop(sqStack *s,ElemType *e)
{if(s->top==s->base)//棧已空return;*e=*--(s->top);
}銷毀一個棧
DestrogStack(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;
}計算棧的當前容量
計算棧的當前容量也就是計算棧中元素的個數，因此只要返回s.top-s.base 即可。
棧的最大容量是指該棧占據內存空間的大小，其值是s.stackSzie，它與棧的當前容量不是一個概念。
int StackLen(sqStack s)
{return (s.top-s.base+1);
}實例分析
利用棧的數據結構特點，將二進制轉換為十進制數。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10typedef 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;
}void 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)=e;s->top++;} void Pop(sqStack *s,ElemType *e)
{if(s->top==s->base){return;}*e = *--(s->top);
}int StackLen(sqStack s)
{return (s.top- s.base);
}int main(void)
{ElemType c;sqStack s;int len ,i,sum=0;InitStack(&s);printf("請輸入二進制數，輸入#符號表示結束!");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",sum);return 0;
}
)
