数据结构——栈和队列的逻辑特性

张玉茹
张玉茹   编辑于 2018-09-27 09:01
阅读量: 144

       线性表是最常用且最简单的一种线性结构。

       线性结构的特点:

       (1) 存在唯一的一个被称作“第一个”的数据元素。

       (2) 存在唯一的一个被称作“最后一个”的数据元素。

       (3) 除第一个之外,集合中的每个数据元素均只有一个前驱。

       (4) 除最后一个之外,集合中每个数据元素均只有一个后继。

       栈和队列是两种重要的线性结构,也是特殊的线性结构。从数据的逻辑角度看,栈和队列是是线性表,从操作的角度来看,栈和队列的基本操作是线性表基本操作的子集,是操作受限制的线性表。

       栈的定义与理解:

       栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIF0结构。

       定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶,而不是栈底。它的特殊之处就在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。这也就使得:栈底是固定的,最先进栈的只能在栈底。栈的插入操作,叫作进栈,也称压栈、入栈。栈的删除操作,叫作出栈,也有的叫作弹栈。如图1所示为栈的进出示意图。

                                         

                                                                 图 1栈的示意图

       队列的定义与理解:   

       队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。假设队列是q = ( a1, a2,……, an),那么a1就是队头元素,而an是队尾元素。这样我们就可以删除时,总是从a1开始,而插入时,列在最后。这也比较符合我们通常生活中的习惯,排在第一个的优先出列,最后面来的当然排在队伍最后。图2是队列示意图。

                                                              图 2队列的示意图

       栈和队列的特点应用:

       栈是先进后出,若在进栈操作的同时允许出栈操作,则n个不同的元素进栈,能得到个不同的出栈序列。

       队列有“先进先出”的特点,所以队列的进队序列和出队序列是相同的。

 

 

       思考:

       1、一个栈的输入序列是1,2,3,...,n,输出序列的第一个元素是n,则第i个输出元素是( )。

       2、设栈S和队列Q的初始状态为空,元素abcdefg依次通过栈S,每个元素出栈后立即进队列,若6个元素的出队序列是bdcfeag,则栈S的容量至少应该是( )。

       3、有5个元素,其入栈次序为ABCDE,在各种可能的出栈次序中,第一个出栈元素为C,第二个出栈元素为D的出栈序列有哪些?

 

 

        解析:

       1、第n个元素先出栈,说明前n-1个元素都已经按顺序入栈,由“先进后出”的特点可知,此时的输出序列一定是输入序列的逆序,所以计算得出第i个输出的元素是n-i+1。   

       2、由于元素的出队顺序和入队顺序是一样的,所以元素的出栈顺序也就是b、d、c、f、e、a、g,栈的特点是先进后出,关于出入栈的详细信息如下表所示:

                        

                                                                表 1出入栈的详细信息

        经过表分析,可以得出,栈内的最大深度为3,故栈的容量最少为3。

       3、CD出栈后的状态如下图所指示:

                                                   

                                                                      图 3第3题图

       此时有如下三种操作:

       ①E进栈后出栈,则出栈序列为CDEBA

       ②B出栈,E进栈后出栈,出栈序列为CDBEA

       ③B出栈,A出栈,E进栈后出栈,出栈序列为CDBAE

       由栈的先进后出特点,我们可以知道,不管序列是怎样的,A比B 先进,则A一定在B的后边。

 

 

 

收藏 转发 评论