栈的定义
栈是一个后进先出（Last In Fist Out, LIFO）的线性表，它要求只在表尾进行删除和插入操作。
所谓的栈，其实就是一个特殊的线性表（顺序表、链表），但是它在操作上有一些特殊的要求和限制：
-
栈的元素必须“后进先出” -
栈的操作只能在这个线性表的表尾进行。 -
对于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。
栈的插入和删除操作
栈的插入操作（Push），叫做进栈，也称为压栈，入栈。
栈的删除操作（Pop），叫做出栈，也称为弹栈。
02.
栈的顺序存储结构
因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也分为栈的顺序存储结构和栈的连式存储结构。
最开始栈中不包含任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。
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;
}入栈操作
-
入栈操作又叫压栈操作，就是向栈中存放数据。
-
入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1，直到栈满为止
#define SATCKINCREMENT 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++;
}出栈操作
-
出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作。
-
每当从栈内弹出一个数据，栈的当前容量就-1
Pop(sqStack *s, ElemType *e)
{
if( s->top == s->base ) // 栈已空空是也
return;
*e = *--(s->top);
}清空一个栈
-
所谓清空一个栈，就是将栈中的元素全部作废，但栈本身物理空间并不发生改变（不是销毁）。
-
因此我们只要将s->top的内容赋值为s->base即可，这样s->base等于s->top，也就表明这个栈是空的了。这个原理跟高级格式化只是但单纯地清空文件列表而没有覆盖硬盘的原理是一样的。其实就是说栈所在磁盘空间的数据并未清除，只是逻辑上清空了一个栈。
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;
}计算栈的当前容量
-
计算栈的当前容量也就是计算栈中元素的个数，因此只要返回s.top-s.base即可。
-
注意，栈的最大容量是指该栈占据内存空间的大小，其值是s->stackSize，它与栈的当前容量不是一个概念哦。
int StackLen(sqStack s)
{
return(s.top – s.base); // 初学者需要重点讲解
}例题：
题目：利用栈的数据结构特点，将二进制转换为十进制数。
{
Pop(&s, &c);
sum = sum + (c-48) * pow(2, i);
}
二进制转十进制操作
题目：利用栈的数据结构特点，将二进制转换为八进制数。
{
for( j=0; j < 3; j++ )
{
Pop( &s1, &c ); // 取出栈顶元素
sum = sum + (c-48) * pow(2, j);
if( s1.base == s1.top )
{
break;
}
}
Push( &s2, sum+48 );
sum = 0;
}
题目：利用栈的数据结构特点，将二进制转换为十六进制数。
{
for( j=0; j < 4; j++ )
{
Pop( &s1, &c ); // 取出栈顶元素
sum = sum + (c-48) * pow(2, j);
if( s1.base == s1.top )
{
break;
}
}
switch( sum )
{
case 10: sum = ‘A’; break;
case 11: sum = ‘B’; break;
case 12: sum = ‘C’; break;
case 13: sum = ‘D’; break;
case 14: sum = ‘E’; break;
case 15: sum = ‘F’; break;
default: sum += 48;
}
Push( &s2, sum );
sum = 0;
}
03.
栈的链式存储结构
teypedef struct StackNode
{
ElemType data; // 存放栈的数据
struct StackNode *next;
} StackNode, *LinkStackPtr;
teypedef struct LinkStack
{
LinkStackPrt top; // top指针
int count; // 栈元素计数器
}进栈操作
对于栈链的Push操作，假设元素值为e的新结点是s，top为栈顶指针，我们得到如下代码：
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;
}
出栈操作
至于链栈的出栈Pop操作，假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。
Status Pop(LinkStack *s, ElemType *e)
{
LinkStackPtr p;
if( StackEmpty(*s) ) // 判断是否为空栈
return ERROR;
*e = s->top->data;
p = s->top;
s->top = s->top->next;
free(p);
s->count--;
return OK;
}逆波兰表达式
逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法 。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。
我们人对于这种后缀表达式并不习惯，但只要以后你学习了编译原理这门课，你就会知道计算机是多么的爱后缀表达式。
int main()
{
sqStack s;
char c;
double d, e;
char str[MAXBUFFER];
int i = 0;
InitStack(&s);
printf("Please input:");
scanf("%c", &c);
while(c != '#')
{
while( isdigit(c))
{
str[i++] = c;
//''一般放在字符串的结束处，表示字符串的结束，其是ascii值为0的字符的转义。
str[i] = '';
if(i >= 10)
{
printf("ERROR: The data entered is too large!n");
}
scanf("%c", &c);
if( c == ' ')
{
d = atof(str);
Push(&s, d);
i = 0;
break;
}
}
switch(c)
{
case '+':
Pop(&s, &e);
Pop(&s, &d);
Push(&s, d+e);
break;
case '-':
Pop(&s, &e);
Pop(&s, &d);
Push(&s, d-e);
break;
case '*':
Pop(&s, &e);
Pop(&s, &d);
Push(&s,d*e);
break;
case '/':
Pop(&s, &e);
Pop(&s, &d);
if(e != 0){
Push(&s, d/e);
}
else{
printf("nERROR: Divisor is zero !n");
}
break;
}
scanf("%c", &c);
}
Pop(&s, &d);
printf("n The result is :%fn", d);
return 0;
}
推荐阅读 END
