全国计算机等级考试三级数据库考点分析之数据结构与算法(6)

文章作者 100test 发表时间 2007:03:10 18:27:41
来源 100Test.Com百考试题网

考点6　栈

　　栈又称为堆栈，它是一种运算受限的特殊的线性表，仅允许在表的一端进行插人和删除运算，可进行运算的一端为栈顶( top)，另一端为栈底( bottom)。表中无任何元素的栈称为空栈。由于栈的插人和删除运算仅在栈顶进行，后进栈的元素必定先被删除，所以又把栈称为“后进先出”（LIFO）表。
　　栈的基本操作有：
　　（1） push(S,X)。往栈S中插人（或称推人）一个新的栈顶元素x，即进栈。
　　（2）pop（S）。从栈S中删除（或称弹出）栈顶元素，即出栈。
　　（3）lop(S，X)：把栈S的栈顶元素读到变量x中，栈保持不变。
　　（４）empty（S）。判断栈S是否为空栈，是则返回值为真。
　　（5）makempty。（S）将栈S设置为空。
　　栈既然是一种线性表，所以线性表的存储结构同样也适用于栈。栈通常用顺序存储方式来存储，分配一块连续的存储区域存放栈中元素，用一个变量来指向当前栈顶。

考点7　队列
　　队列简称为队，它也是一种运算受限的线性表，队列的限定是仅允许在表的一端进行插入，而在另一端进行删除。进行删除操作的一端称做队列的头，进行插人操作的一端称为队列的尾.
　　队列的基本操作有：
（1) enq（Q, X)。往队列口中插人一个新的队尾元素x，即人队。
（2）deq（口）从队列Q中删除队头元素，即出队。
（3 ) front口,x)将队列口的队头元素值读到变量x中，队列保持不变。
（4）empty ( Q )．判断队歹，l口是否为空，是则返回值为真。
（5）makempty（口）将队列口置为空队列。
和线性表一样、队列的存储方式也有顺序存储和链式存储两种。顺序队列在进行人队操作时，会产生假溢出现象解决的办法是让队列首尾相连，构成一个循环队列。