第三章栈和队列_数据结构.doc

文档介绍：第三章  栈和队列
 
一、内容提要
 
 ,栈和队列也是线性表,其操作是线性表操作的子集,属操作受限的线性表。但从数据类型的角度看,它们是和线性表大不相同的重要抽象数据类型。
。栈是只准在一端进行插入和删除操作的线性表,该端称为栈的顶端。
,及在这两种结构下实现栈的操作。
:表达式求值,递归过程及消除递归。
,队列的删除在一端(尾),而插入则在队列的另一端(头)。因此在两种存储结构中,都需要队头和队尾两个指针。
,而循环队列满的条件的判定,则有队尾加1等于
队头和设标记两种方法。
 
二、学习重点
 
。
、后缀表达式并求值。
:定义是递归的,数据结构是递归的,及问题的解法是递归的,
掌握典型问题的算法。
4.  链队列删除时为空的处理(令队尾指针指向队头)。特别是仅设尾指针的循环链队
列的各种操作的实现。
5.  循环队列队空定义为队头指针等于队尾指针,队满则可用一个单元(教材中所示)
及设标记办法(下面例题)。这里特别注意取模运算。
6.  在后续章节中要注意栈和队列的应用,如串中心对称的判定,二叉树遍历的递归
和非递归算法,图的深度优先遍历等都用到栈,而树的层次遍历、图的宽度优先遍
历等则用到队列。
 
三、例题解析
 
,编写入栈和出栈算法。
TYPE
TwoWayStack=RECORD{双栈共享一向量空间}
elem:ARRAY[1..m] OF elemtype;
top:ARRAY[0..1] OF 0..m+1;{两个栈顶指针}
END;
#define m 1000
Typedef struct
{elemtype elem[m];
int top[2];
}*TwoWayStack;
inistack(TwoWayStack tws){初始化}
//初始化双向栈tws为空
{tws->top[0]=-1;{ 左端栈指针}
tws->top[1]=m;{ 右端栈指针}
}{inistack}
 
PUSH(TwoWayStack tws,int I,elemtype x,intofw)
{若双向栈tws不满,则将x插入到i端,成功时ofw为true,失败为false}
{IF((tws->top[1]-[0])!=1)
//栈未满
Swith i
{case0:tws->top[0]=tws->top[0]+1;tws->elem[tws->top[0]]=x;ofw=1;
case1:tws->top[1]=tws->top[1]-1;tws->elem[tws->top[1]]=x;ofw=1
}
ELSE ofw=0;// 栈满
}// end push
int POP(TwoWayStack tws,int I,elemtype &x,int underflow)
//若双向栈tws非空,则将i端退栈,栈空时underflow为true
{switch i
{case 0:IF (tws->top[0]==-1)//栈空
{underflow=1;return(underflow);}
ELSE {tws->top[0]=[0]-1;
x=tws->elem[tws->top[0]+1;
} //弹出元素
}
case 1:IF (tws->top[1]==m)//栈空
{underflow=1;return(underflow);}
ELSE {tws->top[1]=tws->top[1]+1;
x=tws->elem[[1]-1];//弹出元素
}
}
} // end pop
【讨论】上面算法中用0和1代表两端,且按操作在哪端来分两种情况进行讨论,逻辑清楚。也可用一个公式表示插入(进栈)和删除(退栈)指针位置。例如,插入时top=top+1-2*i,删除时top=top-1+2*i。表达简洁,但不如上面清楚易读。
 
,并进行表达式求值。
String trnssufix(string exp1)
//本算法将中缀表达式exp1转为后缀表达式exp2,使用运算符栈s
//算法基本思想是依次从中缀表达式读入字符w: 若w是变量,直接送入结果表达式,若w是运算符,则与栈顶运算符比较,若级别高,则进栈; 若低,则栈顶元素退栈,并送入结果