A. 栈的存储结构
栈同顺序表和链表一样，栈也是用来存储逻辑关系为 "一对一" 数据的线性存储结构。
栈的具体实现
栈是一种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种方式：
顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
链栈：采用链式存储结构实现栈结构；
栈存储结构与之前所学的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：
栈只能从表的一端存取数据，另一端是封闭的；
在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素。
B. 栈的链式存储结构
int initstack(stack &s) 建堆栈
{
s.base=(char *)malloc(100*sizeof(char));
if(!s.base) exit(0);
s.top=s.base;
s.stacksize=100;
return 1;
}
int push(stack &s,char e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(char *)realloc(s.base,(s.stacksize+10)*sizeof(char));
if(!s.base) exit(0);
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*s.top++=e;
}
int pop(stack &s,char &e)
{
if(s.top==s.base) exit(0);
e=*--s.top;
return 1;
}
参考下
C. 分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。
顺序存储结构
#include<iostream>
typedef char ElemType;
#define MaxSize 100
using namespace std;
typedef struct
{
ElemType data[MaxSize];
int top;
}sqStack;
void InitStack(sqStack *&s);//初始化栈
void ClearStack(sqStack *&s);//摧毁栈
int StackLength(sqStack *s);//返回栈的长度
bool StackEmpty(sqStack *s);//判断栈是否为空
int Push(sqStack *&s,ElemType e);//进栈
int Pop(sqStack *&s,ElemType &e);//出栈
int GetTop(sqStack *s,ElemType &e);//取栈顶元素
void DispStack(sqStack *s);//显示栈中元素值
int main()
{
return 0;
}
void InitStack(sqStack *&s)//初始化栈
{
s=new sqStack;
s->top=-1;
}
void ClearStack(sqStack *&s)//摧毁栈
{
delete s;
}
int StackLength(sqStack *s)//返回栈的长度
{
return (s->top+1);
}
bool StackEmpty(sqStack *s)//判断栈是否为空
{
return (s->top==-1);
}
int Push(sqStack *&s,ElemType e)//进栈
{
if(s->top==MaxSize-1)
return 0;
s->top++;
s->data[s->top]=e;
return 1;
}
int Pop(sqStack *&s,ElemType &e)//出栈
{
if(s->top==-1)
return 0;
e=s->data[s->top];
s->top--;
return 1;
}
int GetTop(sqStack *s,ElemType &e)//取栈顶元素
{
if(s->top==-1)
return 0;
e=s->data[s->top];
return 1;
}
void DispStack(sqStack *s)//显示栈中元素值
{
for(int i=s->top;i>=0;i--)
cout<<s->data[i]<<" ";
cout<<endl;
}
链式存储结构
typedef char ElemType;
typedef struct linknode
{
ElemType data;
struct linknode *next;
}LiStack;
void InitStack(LiStack *&s);//初始化栈
void ClearStack(LiStack *&s);//摧毁栈
int StackLength(LiStack *s);//返回栈的长度
bool StackEmpty(LiStack *s);//判断栈是否为空
void Push(LiStack *&s,ElemType e);//进栈
int Pop(LiStack *&s,ElemType &e);//出栈
int GetTop(LiStack *s,ElemType &e);//取栈顶元素
void DispStack(LiStack *s);//显示栈中元素值
int main()
{
return 0;
}
void InitStack(LiStack *&s)//初始化栈
{
s=new LiStack;
s->next=NULL;
}
void ClearStack(LiStack *&s)//摧毁栈
{
for(LiStack *p=s->next;p;p=p->next)
{
delete s;
s=p;
p=p->next;
}
delete s;
}
int StackLength(LiStack *s)//返回栈的长度
{
int i=0;
for(LiStack *p=s->next;p;p=p->next)
i++;
return i;
}
bool StackEmpty(LiStack *s)//判断栈是否为空
{
return (s->next==NULL);
}
void Push(LiStack *&s,ElemType e)//进栈
{
LiStack *p=new LiStack;
p->data=e;
p->next=s->next;
s->next=p;
}
int Pop(LiStack *&s,ElemType &e)//出栈
{
LiStack *p;
if(s->next==NULL)
return 0;
p=s->next;
e=p->data;
s->next=p->next;
delete p;
return 1;
}
int GetTop(LiStack *s,ElemType &e)//取栈顶元素
{
if(s->next==NULL)
return 0;
e=s->next->data;
return 1;
}
void DispStack(LiStack *s)//显示栈中元素值
{
LiStack *p=s->next;
for(;p;p=p->next)
cout<<p->data<<" ";
cout<<endl;
}
D. 栈的基本操作
栈的基本操作如下：
（1）初始化一个栈：InitStack
（2）销毁一个栈：DestroyStack
（3）清空一个栈：ClearStack
（4）判断一个栈是否为空：StackIsEmpty
（5）返回栈中元素个数，即栈的长度：StackLength
（6）入栈，把一个元素加入到栈中：Push
（7）出栈，把栈顶元素给干掉：Pop
（8）燃毁搭返回栈顶元素，但不出栈：GetTop
对于栈这一数据结构，皮拿我首先写一下它的基本概念。
一.基本概念：
栈(stack)是仅限定在表尾进行插入和删除操作的线性表。
栈就是一个线性表，只不过，栈的Insert 和 delete只能在表尾。
普通的线性表，在表中的任意位置都可以进行insert和delete操作。
LIFO: Last In First Out 后进先出，先进后出。
栈顶(Top): 进行插入和删除操作的一端。
栈底(Bottom)
栈其实我们计算机科学中，更多的一种余陪思想，“先进后出的思想”。在很多算法或应用中，需要用到“先进后出的思想”，我们可以考虑用栈来实现。
二.存储结构：
顺序结构： 用一组地址连续的空间来存储数据元素。
链式结构：用地址不连续的空间来存储数据元素，可能需要额外开辟一些空间，来存储“数据元素之间的逻辑关系"。
E. 单共享栈
栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性数据结构。应用广，作用大。
一、1、 栈的定义：限定仅在表尾进行插入或删除操作的线性表，因此，对栈来说，表尾端有其特殊含义，表尾—栈顶(top) ，表头—栈底(bottom) ，不含元素的空表称空栈。
例4：计算机系2001年考研题（程序设计基础）
设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：
A）a，b，c，d B）c，d，a，b
C）b，c，d，a D）a，c，d，b
A、D可以（ B、C不行）。
答：
例5、习题集P22 3.4
status algo1(stack s)
{int i,n,a[255];
n=0;
While(!stackempty(s))
{n++;
pop (s,a[n]);}
For(i=1;i<=n;i++) push (s,a[i]);
}
5、补充公式：
若输入的序列为1、2、3 ….n，则可能出现的输出序列符合卡塔南数列：
验证：
二、 栈的表示和实现：
顺序存贮结构__顺序栈；
链式存贮结构__链栈；
（一） 顺序栈
利用一组地址连续的存贮单元依次自栈底到栈顶存放栈的数据元素.
栈底元素是最先进入的，实际上是线性表的第一个元素
数组（静态数组）：空间固定
动态数组：动态申请空间（用指针表示）
表示容量；
表示数据元素个数；
// 顺序栈的C表示
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置；base表示栈底指针；
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{ SElemType *Base; // 栈底指针
SElemType *Top; // 栈顶指针
int StackSize;//当前已分配的存储空间，以元素为 单位。
}SqStack
空栈
A
A进栈
top
base
top
base
s.top=0 或s.top=s.base 表示空栈；
s.base=NULL表示栈不存在；
当插入新的栈顶元素时，指针s.top++；
删除栈顶元素时，指针s.top--；
当s.top-s.base>=stacksize时，栈满，溢出
顺序栈初始化
SqStack s;
s.Base = NULL;
s.Top = NULL;
s.StackSize = 0;
base
stacksize
top
&s
s.base = s.top =
( SElemType *)malloc( STACK_INIT_SIZE * sizeof( SElemType ));
顺序栈的C图示
base
top
空栈：
base = top;
A
base
top
*top = A;
top ++;
E
C
B
A
D
base
top
B
A
base
top
出栈：
if( top != base )
{
top --;
e = *top;
}
入栈：
if( 没有空间 )
{
//realloc，调整top
}
顺序栈基本算法_InitStack
// 初始化顺序栈, 构造一个空栈
Status InitStack( SqStack &S )
{
s.base = (SElemType *)malloc(
STACK_INIT_SIZE * sizeof( SElemType));
if( !s.base )
{
return OVERFLOW;
}
s.top = s.base;
s.stacksize = STACK_INIT_SIZE;
return OK;
}// InitStack
顺序栈基本算法：GetTop
// 用e返回栈S的栈顶元素，若栈空，函数返回ERROR
Status GetTop( SqStack S, SElemType &e)
{
if( s.top != s.base ) // 栈空吗？
{
e = *( s.top – 1 );
return OK;
}
else
{
return ERROR;
}
}// GetTop
顺序栈基本算法：Push
//把元素e入栈
Status Push(SqStack &S, SElemType e )
{
// 若栈，追加存贮空间
if( s.top == s.base + s.stacksize )
{
p = (SElemType *)realloc( s.base,
(s.stacksize + STACKINCREMENT)*sizeof(SElemType));
if( !p )
{
return OVERFLOW;
}
s.base = p;
顺序栈基本算法：Push
s.top = s.base + s.stacksize;
s.stacksize += STACKINCREMENT;
}
*s.top = e;
s.top++;
return OK;
}// Push
顺序栈基本算法：Pop
// 出栈
Status Pop( SqStack &S, SElemType &e )
{
if( s.top == s.base ) // 空吗？
{
return ERROR;
}
s.top --;
e = *s.top;
return OK;
}// Pop
顺序栈基本算法：其他
// 取顺序栈长度
int StackLength( SqStack S )
{
return s.top – s.base;
}// StackLength
#define StackLength( S ) ((S).top – (S).base)
// 顺序栈空吗？
Status StackEmpty( SqStack S )
{
return s.top == s.base ? TRUE:FALSE;
}
#define StackEmpty( S ) (((S).top == (S).base )?TRUE:FALSE)
顺序栈基本算法：ClearStack
// 清空栈
Status ClearStack( SqStack S )
{
if( s.base )
{
s.top = s.base;
}
return OK;
}// ClearStack
顺序栈基本算法：DestroyStack
// 销毁栈
Status DestroyStack( SqStack &S )
{
if( s.base )
{
free( s.base );
s.stacksize = 0;
s.base = s.top = NULL;
}
}// DestroyStack
3.1.3 链栈
栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。
链栈的类型说明如下：
栈的链接存储结构
链栈的结点定义
typedef struct node
{ ElemType data;
struct node *next;
} LinkStack;
栈的链接表示 — 链式栈
链式栈无栈满问题，空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
链栈的进栈算法
LinkStack *PUSH (LinkStack *top, ElemType x)
{ LinkStack *p;
p＝malloc(sizeof(LinkStack));
p->data＝x; p->next＝top;top=p;
return top;
}
链栈的出栈算法
linkstack *POP (linkstack *top, ElemType *datap)
{ linkstack *p;
if (top==NULL)
{printf(“under flow\n”); return NULL;}
else
{ *datap＝top->data;
p＝top;
top＝top->next;
free(p);
return top;
}
}
栈的共享存储单元
有时，一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。 为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。
栈的应用---基本应用
void read_write()
{ stack S;
int n,x;
cout<<”Please input num int n”;
cin>>n; //输入元素个数
init_stack(S); //初始化栈
for (i=1; i<=n; i++)
{ cin>>x; //读入一个数
push_stack(S,x); //入栈
}
while (stack_empty(S)!=TRUE)
{stack_top(S,x); //取出栈顶元素
cout<<x; //输出
pop_stack(S); //退栈
}
}
读入一个有限大小的整数n，并读入n个整数，然后按输入次序的相反次序输出各元素的值。
3.2 栈的应用举例
一、 数制转换
二、 括号匹配的检验
三、 行编辑程序问题
四、 表达式求值
五、 迷宫求解
六、 实现递归
一、数制转换
十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:
N=(n div d)*d+n mod d
( 其中:div为整除运算,mod为求余运算)
例如 (1348)10=(2504)8，
其运算过程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
0
计算顺序
输出顺序
算法分析：
由十进制转换为其他进制的数的规则，可知，求得的余数的顺序为由低位到高位，而输出则是由高位到低位。
因此，这正好利用栈的特点，先将求得的余数依次入栈，输出时，再将栈中的数据出栈。
void conversion () {
InitStack(S); // 构造空栈
scanf ("%d",&N); //输入一个十进制数
while (N) {
Push(S, N % 8); // "余数"入栈
N = N/8; // 非零"商"继续运算
}
while (!StackEmpty(S)) {
Pop(S,&e);
//和"求余"所得相逆的顺序输出八进制的各位数
printf ( "%d", e );
}
} // conversion
二、 括号匹配的检验
假设在表达式中
(〔〕（））或〔（〔 〕〔 〕）〕
等为正确的格式，
（〔]（ ） 或（（）））或 〔（ 〕）均为不正确的格式。
则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。
算法的设计思想：
读入表达式
1）凡出现左括号，则进栈；
2）凡出现右括号，首先检查栈是否空
若栈空，则表明该“右括号”多余，
否则和栈顶元素比较，
若相匹配，则“左括号出栈” ，
否则表明不匹配。
3）表达式检验结束时，
若栈空，则表明表达式中匹配正确，
否则表明“左括号”有余。
Status matching(char exp[ ] ) {
while (i<=Length(exp)) {
switch exp[i] {
case '(‘ || '[' :{Push(S,exp[i]); i++; break;}
case ')' : {
if( ！StackEmpty(S)&& GetTop(S)= '(' ）
{Pop(S,e); i++;}
else return ERROR;
break; }
case ‘]' : {
if( ！StackEmpty(S)&& GetTop(S)= ‘[' ）
{Pop(S,e); i++;}
else return ERROR;
break; } }
if (StackEmpty(S)) return OK;
}
三、行编辑程序问题
“每接受一个字符即存入存储器” ?
并不恰当！
设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区,并假设“#”为退格符，“@”为退行符。
在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。
合理的作法是：
假设从终端接受了这样两行字符：
whli##ilr#e（s#*s)
outcha@putchar(*s=#++);
则实际有效的是下列两行：
while (*s)
putchar(*s++);
可设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符之后先作如下判断：
1、既不是退格也不是退行符，则将该字符压入栈顶；
2、如果是一个退格符，则从栈顶删去一个字符；
3、如果是一个退行符，则将字符栈清为空栈 。
while (ch != EOF && ch != '\n') {
switch (ch) {
case ‘#’ : Pop(S, c); break;//栈非空，退栈
case '@': ClearStack(S); break;// 重置S为空栈
default : Push(S, ch); break; //未考虑栈满
}
ch = getchar( ); // 从终端接收下一个字符
}
ClearStack(S); // 重置S为空栈
if (ch != EOF) ch = getchar( );
}
DestroyStack(S); }
Void LineEdit( ) {
InitStack(S);
ch=getchar();
while (ch != EOF) { //EOF为全文结束符
将从栈底到栈顶的字符传送至调用过程的数据区；
补充习题：
1、设计一个算法，用栈的基本运算，判定一个字符串是否为对称字符串，若是，则返回1，否则返回0。（abccba)
四、表达式求值
1、算术表达式的组成：
将表达式视为由操作数、运算符、界限符（称为单词）组成。
操作数：常数、变量或符号常量。
算符：运算符、界限符
表达式求值是程序设计语言编译的一个最基本的问题。它的实现是栈应用的又一典型例子。 仅以算术表达式为例
2、算术表达式的形式：
中缀(infix)表达式——表达式的运算符在操作数的中间。 <操作数> <操作符> <操作数>
例：A*B 例：5+9*7
后缀(postfix)算术表达式(逆波兰式)——将运算符置两个操作数后面的算术表达式。 <操作数> <操作数> <操作符>
例：AB* 例：5 9 7*+
前缀(prefix)表达式(波兰式)又称波兰式，与后缀表达式相反。把运算符放在两个运算数的前面， <操作符> <操作数> <操作数>
例：*AB 例：+5*9 7
3、介绍中缀算术表达式的求值
例如：3*（7 – 2 ）
（1）算术四则运算的规则：
a. 从左算到右
b. 先乘除，后加减
c. 先括号内，后括号外
由此，此表达式的计算顺序为：
3*（7 – 2 ）= 3 * 5 = 15
（2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符1和2 ，都要比较优先权关系。
一般任意两个相继出现的两个算符p1和p2之间的优先关系至多有下面三种之一：
p1<p2 p2的优先权高于p1
p1=p2 二者优先权相等
p1>p2 p2的优先权低于p1
算符优先法所依据的算符间的优先关系
见教材P53表3.1
θ1<θ2，表明不能进行θ1 的运算，θ2 入栈，读 下一字符。
θ1>θ2，表明可以进行θ1 的运算，θ1退栈，运算，运算结果入栈。
θ1=θ2，脱括号，读下一字符或表达式结束。
（3）算法思想：
设定两栈：操作符栈 OPTR ，操作数栈 OPND
栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 ‘#’；
依次读入字符：是操作数则入OPND栈，是操作符则要判断：
if 操作符 < 栈顶元素，则退栈、计算，结果压入OPND栈；
操作符 = 栈顶元素且不为‘#’，脱括号（弹出左括号）；
操作符 > 栈顶元素，压入OPTR栈。
扫描基本符号
是否操作数？
Y
栈顶运算符低
于当前运算符？
操作数
入栈
N
Y
N
运算符
入栈
取出S栈顶运算符和
O栈顶的两个操作数
运算，结果入栈O
定义运算符栈S
和操作数栈O
栈S为空？
Y
结束
Y
一般作为相同运算符，先出现的比后出现的优先级高；
先出现的运算符优先级低于“(”，高于“)”；
后出现的运算符优先级高于“(”，低于“)”；优先权相等的仅有“(”和“)”、“#”。
#：作为表达式结束符，通常在表达式之前加一“#”使之成对，当出现“#”=“#”时，表明表达式求值结束，“#”的优先级最低。
OPTR
OPND
INPUT
OPERATE
3*(7-2)#
Push(opnd,’3’)
#
*(7-2)#
3
#
Push(optr,’*’)
#,*
3
(7-2)#
Push(optr,’(’)
#,*,(
3
7-2)#
Push(opnd,’7’)
#,*,(
3,7
-2)#
Push(optr,’-’)
#,*,(,－
3,7
2)#
Push(opnd,’2’)
#,*,(,－
3,7,2
)#
Operate(7-2)
#,*,(
3,5
)#
Pop(optr)
#,*
3,5
#
Operate(3*5)
#
15
#
GetTop(opnd)
例：3*（7-2）
Status EvaluateExpression( OperandType &result) {
InitStack(OPND); InitStack(OPTR);
Push(OPTR ,’#’);c=getchar();
while((c!=‘#’)&&(GetTop(OPTR)!=‘#’))
{ if (!In(c,OP) { Push(OPND,c); c=getchar();}
else switch(compare(c,GetTop(OPTR)))
{case ‘>’ : Push(OPTR , c); c=getchar();break;
case ‘=’: Pop(OPTR);c=getchar();break;
case ‘<’ : temat=Pop(OPTR); b=Pop();a=Pop();
result= Operate(a,temat,b);Push(OPND,result);
c=getchar();break;
} //switch }//while
result=GetTop(OPND);}//EvaluateExpression
此函数在哪里？
4、计算后缀表达式
（1）为什么要把中缀表示法变为后缀表示法？
计算机计算表达式是机械执行，只能从左至右扫描。计算中缀表达式比较困难。
后缀表达式的求值过程是自左至右运算符出现的次序和真正的计算次序是完全一样的。
顺序扫描表达式的每一项，根据它的类型做如下相应操作：
若该项是操作数，则将其压栈；
若该项是操作符<op>，则连续从栈中退出两个操作数Y和X，形成运算指令X<op>Y，并将计算结果重新压栈。
当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计
算结果。
人们仍然使用中缀表达式 ，而让机器把它们转换成后缀表达式。
（2）后缀表达式求值实例：
A=B*C + D*(E-F)
ABC*DEF-*+=
ABC*—做 B*C=T1
AT1DEF- –—做E-F=T2
AT1DT2*—做D*T2=T3
AT1T3+—做T1+T3=T4
AT4=—做A=T4
后缀表达式“32422*+13*-^*5-”，栈中状态变化情况：
typedef char elemtype ;
double calcul_exp(char *A) /*本函数返回由后缀表达式A表示的表达式运算结果*/
{ Seq_Starck s ;
ch=*A++ ; Init_SeqStack(s) ;
while ( ch != ’#’ )
{ if (ch!=运算符) Push_SeqStack (s , ch) ;
else { Pop_SeqStack (s , &a) ;
Pop_SeqStack (s , &b) ; /*取出两个运算量*/
switch (ch).
{ case ch= =’+’： c=b+a ; break ;
case ch= =’-’： c=b-a ; break ;
case ch= =’*’： c=b*a ; break ;
case ch= =’/ ’： c=b/a ; break ;
case ch= =’%’： c=b%a ; break ; }
Push_SeqStack (s, c) ; }
ch=*A++ ;
}
Pop _SeqStack ( s , result ) ;
return result ;
}
（3）中缀表达式变后缀表达式
表达式中操作数次序不变,，运算符次序发生变化,运算符放在操作数的后面。同时去掉了圆括号 。
例：3+（7*8-9）
运算符的优先数表
5
4
3
2
1
0
优先数
^
*，/
＋，－
＝
）
（
操作
存储结构
W（I）存放表达式的第I个字符。
利用一个栈S（）。P为栈指针。
算法设计
Step1：输入是变量则输出它；
Step2：是左括号“（”，无条件地压入堆栈；
Step3：输入运算符优先数是2，3，4，5时，如果栈空，则进栈。如果栈不空，则将它与栈顶元进行比较。倘若优先数大于顶元，则进栈；小于顶元，则顶元退栈并输出之。然后再继续比较，直到大于顶元或栈空时它进栈；
Step4：若是右括号“）”，同时栈顶元又为左括号“（”，则退栈，并抹去“）”。否则按Step3处理；
Step5：输入完而栈非空，则将栈内内容逐一退栈，并输出之。
模拟算法执行过程
A=B*C+D*(E-F)
ABC*DEF-*+=
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
栈s （）:
top=0
A
变量,输出
输出:
说明:
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
栈s （）:
A
算符,栈空,入栈
=
输出:
说明:
top=0
top=0
top=1
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
=
栈s （）:
top=1
A
变量,输出
输出:
说明:
B
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
=
栈s （）:
AB
算符*,优先级等于4,大于栈顶元素=优先级,入栈
输出:
说明:
*
top=1
top=1
top=2
)
F
-
F. 栈的链式存储结构是什么
若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。由于栈的插入、删除操作只能在一端进行，而对于单链表来说，在首端插入、删除结点要比在尾端进行相对容易一些，所以将单链表的首端作为栈的顶端，即将单链表的头指针作为栈顶指针。链栈如图1所示。
图1链栈的存储示意
G. 栈的顺序存储是什么
由于栈是运算受限的线性表，因此线性表的存储结构对栈也适用，而线性表有顺序存储和链式存储两种，所以栈也有顺序存储和链式存储两种。
1.栈的顺序存储栈的顺序存储是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素，并附设指针top指示栈顶。
2.栈的顺序存储类型定义1）用内存动态分配方式定义栈的顺序存储（1）栈的顺序存储表示。
顺序栈本质上是顺序表的简化，由于栈底位置是固定不变的，所以可以将栈底位置设置在存储空间的基地址上，栈顶位置是随着进栈和退栈操作而变化的，故用top来指示当前栈顶元素的下一个位置，通常称top为栈顶指针。
H. 栈的链式存储
#include<stdio.h>
#include<stdlib.h>
凯扒蠢#define elemtype int
#define MAXSIZE 100
typedef struct stack{
elemtype elem;
struct stack *next;
}STACK;
//链盯陪式存储的栈结构，及其相应算法
void InitStack(STACK *top)
{//初始化空栈
top->next=NULL;
}
void DestroyStack(STACK *top)
{//销毁栈，将栈所占内存空间释放
STACK *p;
p=top->next;
while(p!=NULL){
top->next=p->next;
free(p);
p=top->next;
}
}
int EmptyStack(STACK *top)
{//判断是否栈空，为空则返回1，否则返回0
if(top->next==NULL){
return 1;
}
else{
return 0;
}
}
int push(STACK *top, elemtype x)
{//元素x进栈操作，成功返回1，否则返回0
STACK *p;
p=(STACK *)malloc(sizeof(STACK));
p->elem=x;
p->next=top->next;
top->next=p;
return 1;
}
elemtype pop(STACK *top)
{//出栈操作，返回出栈元素
if(EmptyStack(top)){
printf("栈为空");
return 0;
}
else{
elemtype x;
STACK *p;
p=top->next;
此弯x=p->elem;
top->next=p->next;
free(p);
p=top->next;
return x;
}
}
void Print(STACK *top)
{//依次输出栈顶到栈底的所有元素
STACK *h;
h=top->next;
while(h!=NULL){
printf("%4d",h->elem);
h=h->next;
}
}
int main(void)
{
STACK *top=NULL;
top=(STACK *)malloc(sizeof(STACK));
InitStack(top);
push(top,1);
push(top,2);
push(top,4);
Print(top);
push(top,5);
Print(top);
pop(top);
Print(top);
DestroyStack(top);
}
I. 链栈如何构造，链栈新结点如何进栈
链式栈就是用链式存储结构表示一个栈，也就是指针域。
根据栈的性质，知道栈是先进后出，所以只需要设置一个栈顶指针，还是说点C++吧
先构造一个结构模板
template<class
ElemType>
typedef
struct
Node
//建立
{
ElemType
data;//数据成员，用于存储
struct
Node*next;//指针成员，用于连接逻辑结构
}LNode;
1.构造一个空栈，只需要：
LNode*head;//定义栈顶指针
head=(LNode*)malloc(sizeof(LNode));//分配空间
head->next=NULL;//下一个为空
2.新节点：比如新节点数据位1
入栈操作：
LNode*p;
p->data=1;
p->next=head;
head=p;
总之有点类似C语言里的链表
还有什么不清楚的可以追问
希望对你有所帮助！！！
J. 简述栈和队列的顺序存储结构和链式存储结构的优缺点
顺序栈--入栈操作受数组上界的约束有可能发生栈上溢，且需要地址连续的存储单元。
链栈--无须地址连续，便于多个栈共享存储单元，且不存在栈满上溢情况。
顺序队列--需地址连续且有假上溢现象（需改为循环队列才可解决假上溢）
链式队列--特别适合于数据元素变动比较大的情况，且不存在队列满而产生的溢出问题。