前面一个专题讲了线性表、单链表以及静态、循环、双向链表等。从这一个专题开始,我们进入另外一个数据结构的学习:栈和队列。
栈是限定仅在表尾进行插入和删除操作的线性表。
-
喔~原来栈也是线性表,那就应该好理解了。
在我们软件应用中,栈这种后进先出数据结构的应用是非常普遍的。比如你用浏览器上网时,不管什么浏览器都有一个“后退”键,你点击后可以按访问顺序的逆序加载浏览过的网页。比如你本来看着新闻好好的,突然看到一个链接说,有个可以让你年薪100万的工作,你毫不犹豫点击它,跳转进去一看,这都是啥呀,具体内容我也就不说了,骗人骗得一点水平都没有。此时你还想回去继续看新闻,就可以点击左上角的后退键。即使你从一个网页开始,连续点了几十个链接跳转,你点“后退” 时,还是可以像历史倒退一样,回到之前浏览过的某个页面。
很多类似的软件,比如Word、Photoshop等文档或图像编辑软件中,都有撤销(undo)的操作,也是用栈这种方式来实现的,当然不同的软件具体实现代码会有很大差异,不过原理其实都是一样的。
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的找称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIF0结构。
-
理解桟的定义需要注意:首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。
定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指找顶,而不是栈底。它的特殊之处就在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。这也就使得:栈底是固定的,最先进栈的只能在栈底。
栈的插入操作,叫作进栈,也称压栈、入栈。栈的删除操作,叫作出找,也有的叫作弹栈。

延伸阅读
此文章所在专题列表如下:
- 栈的定义与大概理解
- 栈的抽象数据类型ADT
- 顺序栈:栈的顺序存储结构
- 顺序栈的进栈操作
- 顺序栈的出栈操作
- 获取顺序栈的栈顶元素
- 链栈:栈的链式存储结构
- 链栈的进栈操作
- 链栈的初始化与遍历
- 链栈的出栈操作
- 链栈的置空操作与判断链栈是否为空
- 为什么要使用栈这种数据结构
- 递归,栈的重要应用之一
- 栈是如何实现递归的
- 接触后缀表达式(逆波兰表示法)
- 图解后缀表达式的计算过程
- 将中缀表达式转化为后缀表达式
- 开始学习队列这个数据结构
- 队列的抽象数据类型ADT
- 顺序队列:队列的顺序存储结构
- 顺序队列的入队操作
- 顺序队列的出队操作
- 顺序队列置空与判断操作
- 队列顺序存储结构的不足
- 关于循环队列的一些讲解
- 链队列:队列的链式存储结构
- 链队列的初始化操作
- 链队列的入队操作
- 链队列的出队操作
- 补完链队列的其它常见操作
- 循环队列与链队列的优劣势
本文地址:http://www.nowamagic.net/librarys/veda/detail/2269,欢迎访问原出处。