计算机二级公共基础——栈的基本运算

栈(stack)又名堆栈,它是一种的线性表。它的特点是仅允许在表的一端(栈顶)进行插入和删除运算,也就是先进后出、后进先出。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。注:这里主要讲的是顺序栈,有关链栈的知识点后期再讲。

什么是栈

栈(stack)是一种特殊的线性表,仅能在线性表的一端(栈顶)操作,栈顶允许操作,栈底不允许操作,也就是先进后出,后进先出,例如下图中汉诺塔,就可以视为栈。

在我们使用电脑时,栈这种数据结构是非常普遍的,例如浏览网页时的后退/前进和点击链接的操作,也就是出栈和进栈的操作,同时,在编辑文档时,撤销操作也可以视为出栈。栈的基本运算有:入栈、出栈、读取栈顶元素

入栈(Pop)

栈的插入操作,叫作进栈,也称压栈、入栈。类似子弹入弹夹,如下图所示。

出栈(push)

栈的删除操作,叫作出栈,也有的叫作弹栈。如同弹夹中的子弹出夹,如下图所示。

数据出栈后,栈顶会发生变化。

读取栈顶元素(GetTop)

读栈顶元素是指将栈顶元素赋一个指定变量,也就是在题目中,经过一系列操作后,求出top的值,如果top=0,那么就是空栈,如果top=m,那么就是栈满。

栈顶和栈底指针

栈顶指针:top,栈底指针:bottom。例如我们将栈底bottom设为0,栈有3个元素,那么top就为3,例如我们将D入栈,此时栈顶就会有变化,那么栈顶指针就会+1。

在出入栈操作过程中,栈底指针均是固定不变的。另外,栈底指针并不是必须要从0开始,可以自由的定义栈底的位置,但是在出入栈操作时,就不能更改栈底位置了,我们可以将3作为栈底,或者是把栈倒过来,将10作为栈底,如图所示。

栈的顺序存储与运算

我们使用数组S(1:m)作为栈的存储空间,m为栈的最大容量,栈底为数组起始的状态,例如图中的栈,容量为10,初始状态top=6,然后图二为进入了X和Y,图三为Y出栈。

在栈的顺序存储空间S(1:m)中,bottom通常为栈底,top为栈顶,top=0表示栈空,top=m表示栈满。

入栈运算:

1.首先判断栈顶指针是否已经在存储空间的最后一个位置,如果是,说明栈满。不可以再进行入栈操作。

2.如果栈未满,将栈顶指针+1(top+1)

3.最后将新元素查到栈顶指针top指向的位置。

出栈运算:

1.首先判断栈顶指针是否为0,如果是,说明栈空。不可以再进行出栈操作。

2.如果栈未空,然后出栈。

3.最后将栈顶指针-1(top-1)

读栈顶元素:

1.首先判断栈顶指针是否为0,如果是,那么就是空栈,不可以读取栈顶元素。

2.然后将栈顶元素赋值给指定变量y。

解题知识点(重点)

为了解决大家难理解题目的问题,我们研究出了一些通用的解题方法,上面看不懂没关系,如果你只是为了做题,看了这个,配合练习题的讲解,你一定就理解了。

1.如果题目是这样的:设栈的顺序存储空间为S(1:m),初始状态为top=m+1,那么请将这个图套入这个题,能解决大多数有关于栈的问题,因为初始状态的时候,一定为空栈。初始状态在m+1时,地址通常是倒过来的,也就是1在出口,m在栈底。

本图专门针对初始状态为top=m+1题型设计,让你更加容易理解这个题。

2.计算栈中元素的方法,用初始状态的top减去运算后的top,即可获得当前栈中的元素个数。

练习题

1.设栈的顺序存储空间为S(1:m),初始状态为top=m+1,则栈中的数据元素个数为(    )。

A.m+1-top

B.top-m+1

C.m-top

D.top-m

点击查看解析
根据解题知识点2,初始状态减去运算后的top,选择A

2.设栈的顺序存储空间为S(1:m),初始状态为top=m+1。现经过一系列入栈与退栈运算后,top=20,则当前栈中的元素个数为(  )。

A.30

B.20

C.m-19

D.m-20

点击查看解析
根据解题知识点2,用初始状态的top减去运算后的top,那就是m+1-20,所以选择C

3.设栈的存储空间为S(1:m),初始状态为top=m+1。经过一系列入栈与退栈操作后,top=1。现又要将一个元素进栈,栈顶指针top值变为(  )。

A. m

B. 发生栈满的错误

C.2

D.0

点击查看解析
根据解题知识点1,当top=1时,此时栈已经满了,无法再放入数据,所以就会发生栈满的错误。所以选择B

4.设栈的存储空间为 S(1:50),初始状态为 top=51。现经过一系列正常的入栈与退栈操作后,top=20,则栈中的元素个数为(  )。

A.21

B.20

C.30

D.31

点击查看解析
根据解题知识点2,用初始状态的top减去运算后的top,那就是51-20,所以选择D

5.设栈的存储空间为 S(1:50),初始状态为 top=0。现经过一系列正常的入栈与退栈操作后,top=51,则栈中的元素个数为(  )。

A.50

B.不可能

C.1

D.0

点击查看解析
根据解题知识点2,用初始状态的top减去运算后的top,那就是51-0=51,由于存储空间只有50,无法装入51个数据,所以选B

6.设栈的存储空间为 S(1:50),初始状态为 top=51。现经过一系列正常的入栈与退栈操作后,top=20,则栈中的元素个数为(  )。

A.21

B.20

C.30

D.31

点击查看解析
根据解题知识点2,用初始状态的top减去运算后的top,那就是51-20=31,所以选D
本文仅用于学习、研究和交流目的,欢迎非商业性质转载。 文章涉及到的软件来源于互联网,仅供个人下载使用,请勿用于商业用途,版权归软件开发者所有,下载后请于24小时内删除,商业用途请支持正版!因下载本站任何资源造成的损失,全部责任由使用者本人承担!如有侵权、不妥之处,请联系站长删除。敬请谅解!
4S工作室 » 计算机二级公共基础——栈的基本运算
订阅
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
评论x
()
x