文档介绍：数据结构栈和队列
【课前思考】 
1. 什么是线性结构？
简单地说，线性结构是一个数据元素的序列。
  2. 你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n 的次序往上叠的, 那么使用时候的次op==MaxSize-1){
Cout<<“ Stack is full!”;
return 0; }
S->top++;
S->data[S->top]=x;
return 1; }
*
*
出栈Pop(S,x)
int Pop(STACK *S,ElemType *x)
{ if(Empty(S)){
cout<<“Stack is free!”;
return 0;
}
*x=S->data[S->top];
S->top--;
return 1;
}
*
*
取栈顶元素GetTop(S,x)
int GetTop(STACK *S, ElemType *x)
{
if(Empty(S)){
cout<<“Stack is free!”;
retrn 0;
}
*x=S->data[S->top];
return
}
判栈空Empty(S)
int Empty(STACK *S)
{ return (S->top==-1?1:0);}
顺序栈的操作演示
*
*
3．栈的共享存储单元
两个栈共享大小为m的内存空间时，分配方法的示意图如下
两个栈的共享存储单元可用C++语言描述如下：
#define MaxSize <共享存储单元的最大长度>
typedef struct{
ElemType data[MaxSize];
int top[2];
}STACK;
两个共享存储单元顺序栈的操作演示
*
*
（1）两个栈共享存储单元的压栈算法
int Push(STACK *S,ElemType x,int k)
{ if(S->top[0]+1==S->top[1]){
cout<<“stack is full!”;
return 0;
}
if(k==0){ S->top[0]++;
S->data[S->top[0]]=x;}
else{
S->top[1]--;
S->data[S->top[1]]=x;
}
return 1;
}
*
*
（2）两个栈共享存储单元的出栈算法
int Pop(STACK *S,int k,ElemType *x)
{ if((k==0)&&(S->top[0]==-1)){
cout<<“stack is free!”;
return 0; }
if((k==1)&&(S->top[1]==MaxSize)){
cout<<“n stack is free!”; return 0; }
if(k==0){
*x=S->data[S->top[0]];S->top[0]--; }
else{
*x=S->data[S->top[1]];S->top[1]++;
}
return 1;
}
*
*
栈的链式存储结构及其基本运算的实现
栈的链式实现是以链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。栈的链式实现称为链栈
链栈的C++语言描述如下：
typedef struct snode { //定义链栈结点类型
ElemType data;
struct snode *next;
}LinkSTACK;
LinkSTACK *top;
链栈结构示意图
*
*
链栈的几种状态 :
*
*
2．基本运算在链式存储结构的实现
栈初始化
void InitStack(LinkSTACK **top)
{
*top=(LinkSTACK*)malloc(sizeof(LinkSTACK));
(*top)->next=NULL;
}
*
*
压栈运算
int Push(LinkSTACK **top,ElemType x)
{ LinkSTACK *s;
s=(LinkSTACK *)malloc(sizeof(LinkSTACK));
s->da