一、栈
数组是一种连续存储、随机访问的线性表，链表属于分散存储、连续访问的线性表。它们每个数据都有其相对位置，有至多一个直接前驱和之多一个直接后继。栈（Stack）和队列（Queue）也属于线性表，但它们都是运算受限的线性表，因此也称限定性线性表。栈限定数据只能在栈顶执行插入（入栈）和删除（出栈）操作。列队限定只能在队头执行删除操作（出队），在队尾执行插入操作（入队）。
栈的结构如图1所示。（遵循先入后出）
对栈进行运算的一端称为栈顶（top），栈顶的第一个元素称为栈顶元素。向一个栈中插入新元素，即把该元素放到栈顶元素的上面，使其称为新的栈顶元素，称为压入堆栈（Push）。从一个栈中删除元素，使原栈顶元素下方的的相邻元素成为新的栈顶元素，称为弹出堆栈（Pop）。栈的这种运算方式使其具有后进先出（Last Input First Output ，LIFO）的特性。
栈的一个典型应用是表达式求值。表达式求值是程序设计语言编译中的一个最基本的问题。
以二元算术运算符为例，算术表达式的一般形式为s1+op+s2,则op+s1+s2为前缀表示法（也成为波兰表达式），s1+op+s2为中缀表示法，s1+s2+op为后缀表示法（也成为逆波兰表达式）。例如，对于表达式a*b+（c-d/e）*f，则其前缀表达式+ * ab-c/def，中缀表达式为a*b+（c-d/e）*f，后缀表达式为ab*cde/-f*+。
用栈计算逆波兰表达式的基本思路是：按顺序遍历整个表达式，若遇到操作数（假设都是二元运算符），则入栈，若遇到操作符，则连续弹出两个操作数并执行相应的运算，然后将其运算结果入栈。重复以上过程，直到数组遍历完，栈内只剩下一个操作数时，那就是最终的运算结果，弹出打印即可。
例题1：用栈的顺序存储结构实现逆波兰表达式求值程序：
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#define INT 1
#define FLT 2
#define N 20
typedef struct node
{
int ival;
}Nodetype;
typedef struct stack
{
Nodetype data[N];
int top; //控制栈顶
}STACK; //栈的顺序存储
void push(STACK *stack,Nodetype data);
Nodetype pop(STACK *stack);
Nodetype opint(int d1,int d2,int op);
Nodetype opdata(Nodetype *d1,Nodetype *d2,int op);
int main(void)
{
char word[N];
Nodetype d1,d2,d3;
STACK stack;
stack.top=0; //初始化栈顶
//以空格为分隔符输入逆波兰表达式，以#结尾
while(scanf("%s",word)==1&&word[0]!='#')
{
if(isdigit(word[0])) //若为数字，则转换为整型后压入栈
{
d1.ival=atoi(word); //将word转为整型数据
push(&stack,d1);
}
else //否则弹出两个操作数，执行相应运算后再将结果压入栈
{
d2=pop(&stack);
d1=pop(&stack);
d3=opdata(&d1,&d2,word[0]); //执行运算
push(&stack,d3); //运算结果压入堆栈
}
}
d1 = pop(&stack); //弹出栈顶保存的最终计算结果
printf("%d\n",d1.ival);
return 0;
}
//函数功能：将数据data压入堆栈
void push(STACK *stack,Nodetype data)
{
memcpy(&stack->data[stack->top],&data,sizeof(Nodetype));
stack->top=stack->top+1;
}
//函数功能：弹出栈顶数据并返回
Nodetype pop(STACK *stack)
{
stack->top = stack->top-1; //改变栈顶指针
return stack->data[stack->top];
}
//函数功能：对整型的数据d1和d2执行执行运算op，并返回就算结果
Nodetype opint(int d1,int d2,int op)
{
Nodetype res;
switch(op)
{
case '+':
res.ival=d1+d2;
break;
case '-':
res.ival=d1-d2;
break;
case '*':
res.ival=d1*d2;
break;
case '/':
res.ival=d1/d2;
break;
}
return res;
}
//函数功能：对d1和d2执行运算op，并返回计算结果
Nodetype opdata(Nodetype *d1,Nodetype *d2,int op)
{
Nodetype res;
res = opint(d1->ival,d2->ival,op);
return res;
}
