【后缀表达式】
运算符号位于两个运算数之后，如，abc+de/- [a+bc-d/e]
求值策略：从左向右扫描，逐个处理运算数和运算符号。当碰到运算数的时候，记住；当碰到运算符号的时候，就把最近记住的两个数做运算。因此我们需要一种存储方法，能顺序存储运算数，并在需要时倒序输出，这就是堆栈。
【堆栈Stack】
具有一定操作约束的线性表。只能在一端（栈顶，TOP）做插入、删除；插入数据（入栈Push）；删除数据（出栈Pop）；先入后出（LIFO）
【抽象数据类型描述】
类型名称：堆栈
数据对象集：一个有0个或多个元素的有穷线性表
操作集：长度为MaxSize的堆栈S->Stack、堆栈元素item -> ElementType
【栈】
栈的数据结构通常是有一个一维数组和一个记录栈顶元素位置的变量组成。
/* 数组栈 */
#include<stdio.h>
#include<stdlib.h>
/* 栈定义 */
#define MaxSize 100
#define TopofStack -1
typedef int ElementType;
typedef struct SNode *Stack;
struct SNode{
ElementType Data[MaxSize];
int Top; //栈顶元素下标，对于空栈就是-1
};
Stack CreatSack(); //创建数组栈
void Push(Stack PtrS,ElementType item);//入栈,元素item压入栈
ElementType Pop(Stack PtrS);//出栈，栈顶元素弹出
ElementType IsEmpty(Stack PtrS); //判断栈是否为空
int main()
{
Stack S;
ElementType item;
int n=3;
S=CreatSack();
while(n--){
printf("Please enter the item:\n");
item=getchar();
while(getchar()!='\n')
continue;
Push(S,item);
}
Pop(S);
return 0;
}
Stack CreatSack()
{
Stack PtrS;
PtrS=(Stack)malloc(sizeof(struct SNode));
PtrS->Top=TopofStack;
return PtrS;
}
void Push(Stack PtrS,ElementType item)
{
if(PtrS->Top==MaxSize-1){
printf("the Stack is full\n");
}else{
PtrS->Data[++PtrS->Top]=item;
/*(PtrS->Top)++;
PtrS->Data[PtrS->Top]=item;*/
return;
}
}
ElementType IsEmpty(Stack PtrS)
{
return (PtrS->Top==TopofStack); //为空返回1
}
ElementType Pop(Stack PtrS)
{
if(!IsEmpty(PtrS)){
return PtrS->Data[(PtrS->Top)--];
}else{
printf("the Stack is empty\n");
return NULL;
}
}
