1. 请问“多个栈共存时,最好用链式存储空间作为存储结构”，这是为什么啊
如果只有两个栈，则可以将一个放在数组的低空间，一个放在高空间，两者从两头向中间扩展，这样没有空间浪费
如果多于两个栈时，还是采用顺序存储，则一个满了另外栈空间虽然有空，但是必须要移动栈中元素才能使用别的浪费的空间，这样算法的效率就不高了，此时不如直接采用链接存储好了
2. 栈与队列
队列 ：只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
栈 ：是限定仅在表尾进行插入和删除操作的线表。
两栈共享 ：只针对两个具有相同类型的栈的一个设计，一个栈增长，一个栈缩短，（相当于一个栈的栈底为数组的始端，下标为0处，另一个栈的栈底为末端，两个栈如果增加元素，就是两端点向中间延伸）否则会因栈满而溢出。这样让两个栈共享数据，可以最大化地利用数据空间。
栈的链式存储结构： 对于链栈，基本不存在栈满的情况，除非内存已经没有可以使用的空间。此时计算机面临死机崩溃问题。
链栈的空其实就是top=NULL
**顺序栈与链栈的区别：
**
递归函数： 一个直接调用自己或通过一系列的调用语句间接的调用自己的函数。
迭代 使用循环结构，递归使用选择结构
**栈的四则运算表达式求值
**
中缀表达式----->后缀表达式：
3. 两栈共享空间
1.如果有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能 一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空间 。
2.所以我们可以使用 一个数组来存储两个栈 。
3.具体做法如下：数组有两个端点，两个栈有两个栈底，让 一个栈的栈底为数组的始端，即下标为0处 ， 另一个栈为数组的末端，即下标为数组长度n-1处
这样，两个栈如果增加元素，就是 两端点向中间延伸
与上一遍顺序栈的程序不同的是，此处采用下标记录栈顶位置，而非指针，且并没有指向栈顶的下一个存储空间
如下图所示：
测试：
4. 设有两个堆栈S1，S2都采用顺序栈方式，并且共享一个存储区，采用栈顶相向、迎面增长的存贮方式，
1
s1空：S1的栈顶等于栈底
s2空：s2的栈顶等于栈底
2
s1满：S1的栈顶等于S2的栈顶
s2满：S2的栈顶等于S1的栈顶
#include
#define
TYPE_S1
1
#define
TYPE_S2
-1
#define
STACK_SIZE
20
void
StackPush(int
**stackTop,
int
elmnt,
int
type)
{
**stackTop
=
elmnt;
*stackTop
+=
type;
}
void
main()
{
int
stack[STACK_SIZE]
=
{0};
int
*S1Top
=
&stack[0],
*S2Top
=
&stack[STACK_SIZE
-
1];
int
i,
input
=0;
for
(i
=
0;
i
<
20;
i++)
{
printf("请输入一个整数：");
scanf("%d",
&input);
if(input
%
2
==0)
{
StackPush(&S1Top,
input,
TYPE_S1);
}
else
{
StackPush(&S2Top,
input,
TYPE_S2);
}
if(S1Top
==
S2Top)
{
printf("堆栈已满\n");
break;
}
}
return;
}
5. 单共享栈
栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性数据结构。应用广，作用大。
一、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
-
6. 简述栈和队列的顺序存储结构和链式存储结构的优缺点
顺序栈--入栈操作受数组上界的约束有可能发生栈上溢，且需要地址连续的存储单元。
链栈--无须地址连续，便于多个栈共享存储单元，且不存在栈满上溢情况。
顺序队列--需地址连续且有假上溢现象（需改为循环队列才可解决假上溢）
链式队列--特别适合于数据元素变动比较大的情况，且不存在队列满而产生的溢出问题。
7. 线性表，栈，队列的优缺点，异同
三者都是逻辑结构，各有特性，但无所谓优缺点。线性表是一个含有n个元素的有序序列，形成线性结构。这种结构只有一个“第一个元素”和一个“最后一个元素”，除“第一个元素”之外每个元素都有一个前驱，除“最后一个元素”之外每个元素都有一个后继。对线性表附加存取限制可以得到栈和队列。栈只允许在栈顶进行存取，有“后进先出”的特性。队列只允许在队尾存，在队首取，有先进先出的特性。三种结构有不同的应用。
8. 若栈采用顺序存储方式存储,现两栈共享空间
晕.这么简单的问题也拿出来问
1 2 3 .m
| |
那么当他们满的时候,两个指针相邻
那就是
top[1]+1=top[2]
top[1]在top[2]左边相邻了
9. 给出用数组描述的栈的存储结构，以及操作
数据结构复习重点归纳[适于清华严版教材]
一、数据结构的章节结构及重点构成
数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。
对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。
按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：
概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。
线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。
栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。
串 ：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。
多维数组及广义表
：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。
树和二叉树
：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。
图 ：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。
查找
：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。
排序
：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。
二、数据结构各章节重点勾划：
第0章 概述
本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。本章考点不多，只要稍加注意理解即可。
第一章 线性表
作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。
总体来说，线性表一章可供考查的重要考点有以下几个方面：
1.线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。
2.线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。
3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。
4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。
在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大家注意。
5.线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。
第二章 栈与队列
栈与队列，是很多学习DS的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向DS高手的一条必由之路，。
学习此章前，你可以问一下自己是不是已经知道了以下几点：
1.栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。
2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。
3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。
4.循环队列中判队空、队满条件，循环队列中入队与出队算法。
如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。
第三章 串
经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。
串，在概念上是比较少的一个章节，也是最容易自学的章节之一，但正如每个过来人所了解的，KMP算法是这一章的重要关隘，突破此关隘后，走过去又是一马平川的大好DS山河了，呵呵。
串一章需要攻破的主要堡垒有：
1.串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件
2.串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。
3.顺序串与链串及块链串的区别和联系，实现方式。
4.KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足，明确next数组需要改进之外。其中，理解算法是核心，会求数组是得分点。不用我多说，这一节内容是本章的重中之重。可能进行的考查方式是：求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。
第四章 数组与广义表
学过程序语言的朋友，数组的概念我们已经不是第一次见到了，应该已经“一回生，二回熟”了，所以，在概念上，不会存在太大障碍。但作为考研课程来说，本章的考查重点可能与大学里的程序语言所关注的不太一样，下面会作介绍。
广义表的概念，是数据结构里第一次出现的。它是线性表或表元素的有限序列，构成该结构的每个子表或元素也是线性结构的，所以，这一章也归入线性结构中。
本章的考查重点有：
1.多维数组中某数组元素的position求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。
2.明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1中类型的题。
3.将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。
4.广义表的概念，特别应该明确表头与表尾的定义。这一点，是理解整个广义表一节算法的基础。近来，在一些学校中，出现了这样一种题目类型：给出对某个广义表L若干个求了若干次的取头和取尾操作后的串值，要求求出原广义表L。大家要留意。
5.与广义表有关的递归算法。由于广义表的定义就是递归的，所以，与广义表有关的算法也常是递归形式的。比如：求表深度，复制广义表等。这种题目，可以根据不同角度广义表的表现形式运用两种不同的方式解答：一是把一个广义表看作是表头和表尾两部分，分别对表头和表尾进行操作；二是把一个广义表看作是若干个子表，分别对每个子表进行操作。
第五章 树与二叉树
从对线性结构的研究过度到对树形结构的研究，是数据结构课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一切，将最终影响你的专业课总分。所以，树这一章的重要性，已经不说自明了。
总体来说，树一章的知识点包括：
二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。
下面我们来看考试中对以上知识的主要考查方法：
1.二叉树的概念、性质和存储结构
考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：第i层的最多结点数，深度为k的二叉树的最多结点数，n0=n2+1的性质，n个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系（左为：2*i，右为：2*i+1）。
二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。
2.二叉树的三种遍历算法
这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。我会在另一篇系列文章（）里给出三种遍历的递归和非递归算法的背记版，到时请大家一定熟记。
3.可在三种遍历算法的基础上改造完成的其它二叉树算法：
求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。
4.线索二叉树：
线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。
5.最优二叉树（哈夫曼树）：
最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。
6.树与森林：
二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通的双分支树而言，不具有这种性质。
树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根（对于森林而言称作：先序与后序遍历）。在难度比较大的考试中，也有基于此二种算法的基础上再进行扩展要求你利用这两种算法设计其它算法的，但一般院校很少有这种考法，最多只是要求你根据先根或后根写出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。这一点成为很多学校的考点，考查的方式不一而足，有的直接考此句话，有的是先让你求解遍历序列然后回答这个问题。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。
树一章，处处是重点，道道是考题，大家务必个个过关。
第六章 图
如果说，从线性结构向树形结构研究的转变，是数据结构学科对数据组织形式研究的一次升华，那么从树形结构的研究转到图形结构的研究，则进一步让我们看到了数据结构对于解决实际问题的重大推动作用。
图这一章的特点是：概念繁多，与离散数学中图的概念联系紧密，算法复杂，极易被考到，且容易出大题，尤其是名校，作为考研课程，如果不考查树与图两章的知识，几乎是不可想象的。
下面我们看一下图这一章的主要考点以及这些考点的考查方式：
1.考查有关图的基本概念问题：
这些概念是进行图一章学习的基础，这一章的概念包括：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。与这些概念相联系的相关计算题也应该掌握。
2.考查图的几种存储形式：
图的存储形式包括：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。
3.考查图的两种遍历算法：深度遍历和广度遍历
深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。
4.生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法。
考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。
5.拓扑排序问题：
拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。
6.关键路径问题：
这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述求解的过程和步骤。
在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。
7.最短路径问题：
与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法。注意区分。
第七章 查找
在不少数据结构的教材中，是把查找与排序放入高级数据结构中的。应该说，查找和排序两章是前面我们所学的知识的综合运用，用到了树、也用到了链表等知识，对这些数据结构某一方面的运用就构成了查找和排序。
现实生活中，search几乎无处不在，特别是现在的网络时代，万事离不开search，小到文档内文字的搜索，大到INTERNET上的搜索，search占据了我们上网的大部分时间。
在复习这一章的知识时，你需要先弄清楚以下几个概念：
关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，应该记住。
在DS的教材中，一般将search分为三类：1st，在顺序表上的查找；2nd，在树表上的查找；3rd，在哈希表上的查找。下面详细介绍其考查知识点及考查方式：
1.线性表上的查找：
主要分为三种线性结构：顺序表，有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较。对于及有序顺序表我们采用二分查找法。对于第三种索引结构，我们采用索引查找算法。考生需要注意这三种表下的ASL值以及三种算法的实现。其中，二分查找还要特别注意适用条件以及其递归实现方法。
2.树表上的查找：
这是本章的重点和难点。由于这一节介绍的内容是使用树表进行的查找，所以很容易与树一间的某些概念相混淆。本节内容与树一章的内容有联系，但也有很多不同，应注意规纳。树表主要分为以下几种：二叉排序树，平衡二叉树，B树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考B树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密，二叉树一章学好了，这里也就不难了。
二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，所以应该掌握平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。
B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。除B树的查找算法外，应该特别注意一下B树的插入和删除算法。因为这两种算法涉及到B树结点的分裂和合并，是一个难点。B树是报考名校的同学应该关注的焦点之一。
键树也称字符树，特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。
3.基本哈希表的查找算法：
哈希一词，是外来词，译自“hash”一词，意为：散列或杂凑的意思。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。
第八章 内部排序
内排是DS课程中最后一个重要的章节，建立在此章之上的考题可以有多种类型：填空，选择，判断乃至大型算法题。但是，归结到一点，就是考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标（时间复杂度）能否了如指掌。
这一章，我们对重点的规纳将跟以上各章不同。我们将从以下几个侧面来对排序一章进行不同的规纳，以期能更全面的理解排序一章的总体结构及各种算法。
从排序算法的种类来分，本章主要阐述了以下几种排序方法：插入、选择、交换、归并、计数等五种排序方法。
其中，在插入排序中又可分为：直接插入、折半插入、2路插入、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。
交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。
选择排序，相对于前面几种排序算法来说，难度大一点。具体来说，它可以分为：简单选择、树选择、堆排。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数；树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，最终选出最小（大）数；而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。树选择排序，也曾经在一些学校中的大型算法题中出现，请大家注意。
归并排序，故名思义，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。
基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。
本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的，学习时要多注意规纳、总结、对比。此外，对于教材中的10.7节，要求必须熟记，在理解的基础上记忆，这一节几乎成为很多学校每年的必考点。
至此，数据结构所有章节的章节重点问题，我们已经规纳完毕，使用清华严版教材的同学，在复习的同时，可以参照本贴给出的重点进行复习。但是，由于作者本人水平有限，可能有很多考点没有规纳出来，也可能有些考点规纳有误，在此，作者本人诚恳希望诸位朋友直面提出，我会不断完善和发布新的关于数据结构复习的总结以及笔记
严蔚敏数据结构为主的笔记二
第二章：线性表(包括习题与答案及要点)
--------------------------------------------------------------------------------
本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。
要求达到<识记>层次的内容有:线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。
要求达到<综合应用>层次的内容有：顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析，解决简单应用问题。
链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。
要求达到<领会>层次的内容就是顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。
--------------------------------------------------------------------------------
线性表的逻辑结构特征是很容易理解的，如其名，它的逻辑结构特征就好象是一条线，上面打了一个个结，很形象的，如果这条线上面有结，那么它就是非空表，只能有一个开始结点，有且只能有一个终端结点，其它的结前后所相邻的也只能是一个结点(直接前趋和直接后继)。
关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。
--------------------------------------------------------------------------------
线性表的逻辑结构和存储结构之间的关系。在计算机中，如何把线性表的结点存放到存储单元中，就有许多方法，最简单的方法就是按顺序存储。就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。
在顺序表中实现的基本运算主要讨论了插入和删除两种运算。相关的算法我们通过练习掌握。对于顺序表的插入和删除运算，其平均时间复杂度均为O(n)。
--------------------------------------------------------------------------------
线性表的链式存储结构。它与顺序表不同，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。所以为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即
10. 栈的共享存储单元是什么
有时，一个程序设计中，需要使用多个同一类型的栈，这时候，可能会产生一个栈空间过小，发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。
1.双栈为两个栈共同开辟一个存储空间，让一个栈的栈底为该空间的始端，另一栈的栈底为该空间的末端，当元素进栈时，都从两端向中间“增长”，这样能够使剩余的空间为任意一个栈所使用，即当一个栈的深度不足整个空间的一半时，另一个栈的深度可超过其一半，从而提高了存储空间的利用率。可以使用一个数组同时存两个栈，让一个栈的栈底为数组的始端，另一个栈的栈底为数组的末端，每个栈从各自的端点向中间延伸，双栈示意如图1所示。其中，MAXSTACKSIZE为整个数组空间的长度，栈1的底端固定在下标为0的一端，栈2的底端固定在下标为MAXSTACKSIZE－1的一端。top1和top2分别为栈1和栈2的栈顶指针，并约定栈顶指针指向当前元素，即栈1空的条件是top1＝－1，栈1满的条件是top1＝＝top2－1，栈2空的条件是top2＝MAXSTACKSIZE，栈2满的条件是top2＝＝top1＋1。
图1两相栈共享存储单元示意