顺序栈的基本操作_数据结构(一)栈结构

数

结

STRUCTURE

  DATA

据

构

栈/结/构 S/T/A/C/K

前言

在计算机中存储数据需要用到各种数据结构&＃xff0c;一起来了解下栈结构吧。

栈结构介绍

    在计算机的世界里经常会接触到各种数据结构&＃xff0c;例如栈、队列、链表等等。这篇文章就带大家了解一下其中之一的栈结构。

    栈结构的宗旨就是先进后出(FILO, First in Last out)&＃xff0c;即先进入栈中的元素会在最后才能弹出。栈结构用图形来表达的话就是这样&＃xff1a;

栈结构的操作

    栈的操作有两个&＃xff1a;“压入”和“弹出”。压入栈和弹出栈就是对应添加数据和删除数据&＃xff0c;上一节中的栈结构的介绍即是栈的压入操作。至于为什么这样叫呢&＃xff1f;相信你看了下面的“弹出”就会理解了。

    看起来就像是从栈中弹出了有木有&＃xff1f;“熊二”在从栈中弹出后&＃xff0c;栈中就只剩下了“喜羊羊”。细心的小可爱可能已经发现了&＃xff1a;栈的压入顺序是喜羊羊先进来&＃xff0c;其次才是熊二。但是弹出的顺序是熊二先弹出。为什么喜羊羊不能先弹出&＃xff1f;因为熊二压在它的上面&＃xff0c;它想要弹出栈必须先把熊二弹出&＃xff0c;如果上面有更多的元素的话&＃xff0c;依次类推。

    这个原理就叫做“先进后出”&＃xff0c;先进入栈的元素会被压在最下面&＃xff0c;必须等到上面的一个个元素都弹出了&＃xff0c;它才能弹出。

压入、弹出操作的练习

    给大家出个题&＃xff1a;依次向栈中压入1、2、3、4、5五个元素&＃xff0c;然后依次弹出&＃xff0c;弹出的顺序是什么呢&＃xff1f;

    给大家五秒钟的时间考虑一下&＃xff1a;

    答案&＃xff1a;依先进后出原则&＃xff0c;答案应该是&＃xff1a;5、4、3、2、1。

    假如我们限制入栈顺序是5、4、3、2、1&＃xff0c;那么下列哪种不是一个合法的出栈序列&＃xff1f;

    A. 45123

    B. 34125

    C. 52314

    D. 12435

    大家要知道&＃xff0c;栈并不是统一入栈&＃xff0c;全部入完后才能出栈&＃xff0c;而是入栈出栈的时机都可以是自定义的&＃xff0c;只要你想&＃xff0c;可以随时入栈和出栈。

    我们来看选项A&＃xff1a;

    我们知道&＃xff0c;入栈顺序是5、4、3、2、1&＃xff0c;但是A的第一个弹出是4&＃xff0c;那么就代表我们要在栈顶是4时进行弹出&＃xff0c;那么前两次入栈大概是这样&＃xff1a;

    此时按题目要求&＃xff0c;我们下此压入就该压入“3”了&＃xff0c;但是选项A要求的出栈顺序是45123&＃xff0c;第一个要弹出的元素是“4”&＃xff0c;所以我们不能继续入栈了&＃xff0c;要将元素“4”弹出&＃xff0c;就像这样&＃xff1a;

    此时45123第一个元素4已经实现&＃xff0c;接下来需要弹出的元素是“5”&＃xff0c;我们发现栈顶(指在栈的顶部&＃xff0c;随时可能被弹出的元素)正好是5&＃xff0c;所以我们先不入栈&＃xff0c;直接出栈&＃xff0c;像这样&＃xff1a;

    OK&＃xff0c;那么接下来前两步就完成了&＃xff0c;现在栈中已没有了数据&＃xff0c;接下来再向栈中压入吧。

    我们需要的下一个弹出元素是1&＃xff0c;但是栈顶现在是3。所以继续压入吧。

   直到压入最后一个元素1后&＃xff0c;才可以满足45123的1的弹出。我们已经没有其他元素可以压入了&＃xff0c;所以直接弹出&＃xff1a;

    OK&＃xff0c;此时栈中元素已全部弹出了&＃xff0c;我们来看我们的弹出顺序&＃xff1a;4、5、1、2、3。

   滑上去看下选项A的弹出顺序&＃xff0c;是不是一样呢&＃xff1f;

    这样就说明A选项的弹出顺序是可行的&＃xff0c;只要按照我们的入栈出栈步骤就行&＃xff0c;那么选项A符合条件。

    接下来请大家画图并思考B、C、D是否合法&＃xff0c;并选出正确答案。

    栈结构的基本操作就讲到这了&＃xff0c;有同学可能就要问了&＃xff1a;这种结构限制性这么强&＃xff0c;只能以这种方式进行元素的加入、删除&＃xff0c;它到底有什么作用呢&＃xff1f;敬请听下回分解(十进制转二进制的运算)。

~ THE END ~