三：栈和队列.ppt

第三章栈和队列
3.1.1顺序栈
由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来表示当前栈顶的位置，通常称top为栈顶指针。因为数组是由下标0开始存放的，所以通常用top=-1表示空栈。
设S是SqStack类型的指针变量。若栈底位置在向量的低端，即s–>data[0]是栈底元素，那么栈顶指针s–>top是正向增加的，即进栈时需将s–>top加1，退栈时需将s–>top减1。
因此，s–>top==-1表示空栈，
s–>top==stacksize-1表示栈满。
当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。

练习题：
当用长度为n的数组顺序存储一个栈时，假定用top==n表示栈空，则表示栈满的条件是（）。

1、置空栈
voidinitstack(seqstack*s)
{
s–>top=-1;
}
2、判断栈空
intstackempty(seqstack*s)
{
return(s–>top==-1);
}
3、判断栈满
intstackfull(seqstack*s)
{
return(s–>top==stacksize-1);
}
4、进栈
voidpush(seqstack*s，datatypex)
{
if(stackfull(s))
error(“stackoverflow”);
s–>data[++s–>top]=x;
}

5、退栈
datatypepop(seqstack*s)
{
if(stackempty(s))
error(“stackunderflow”);
x=s–>data[top];
s–>top--;
return(x)

}

6、取栈顶元素
Datatypestacktop(seqstack*s)
{
if(stackempty(s)
error(“stackisenpty”);
returns–>data[s–>top];
}
Typedefstruct{
Elemtype*base;//栈底指针
Elemtype*top;//栈顶指针
intstacksize;
}SqStack;

判空条件：top==base
栈不存在：base==NULL
这样在非空栈中，栈顶指针始终在栈顶元素的一个位置上。
2.在作进栈运算时,应先判别栈是否(①),在作退栈运算时应先判别栈是否(②)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③)。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的(④)分别设在这片内存空间的两端,这样,当(⑤)时，才产生上溢。
①,②:A.空B.满C.上溢D.下溢
③:A.n-1B.nC.n+1D.n/2
④:A.长度B.深度C.栈顶D.栈底
⑤:A.两个栈的栈顶同时到达栈空间的中心点.
B.其中一个栈的栈顶到达栈空间的中心点.
C.两个栈的栈顶在栈空间的某一位置相遇.
D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.
行编辑程序：遇到#则表示前一字符无效；遇到@表示整行无效表达式求值后缀表达式求值步骤：
1、读入表达式一个字符
2、若是操作数，压入栈，转4
3、若是运算符，从栈中弹出2个数，将运算结果再压入栈
4、若表达式输入完毕，栈顶即表达式值；
若表达式未输入完，转1
通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止
如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道

栈的应用
过程的嵌套调用例递归的执行情况分析递归调用执行情况如下：3.2队列
队列的定义及特点
定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表
队尾(rear)——允许插入的一端
队头(front)——允许删除的一端
队列特点：先进先出(FIFO)链队列
结点定义StatusEnQueue(LinkQueue&Q,ElemTypee)
{
//插入元素e为Q的新的队尾元素
p=(QueuePtr)malloc(sizeof(Qnode));
if(!p)exit(OVERFLOW);//存储分配失败
p->data=e;p->next=NULL