前面两节，我们分析了顺序表和链表。这一节我们分析两种特殊的线性表：栈和队列。
栈的定义：按照百度百科的介绍，栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
队列的定义：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
我们用图来描述一下或许更好理解：
栈.png
队列.png
说到栈和队列，我们生活中也有很常见的例子与它们相似。比如说穿衣服和脱衣服的过程更像是压栈和出栈，而排队买票的过程更像是队列的出入队列的过程。其实，我们的程序就是用来描述现实生活中的场景的，所以才会设计出很多符合现实生活的数据结构。
我们先来分析一下栈的数据结构，在Java中，有一个类叫做Stack,翻译过来就叫堆栈。
我们来看一下Stack的源码，
首先，它有5个独有方法：
1.empty（）判断是否为空，即size是不是为0
2.peek（）获取栈顶元素，但不移除它。
3.pop（）获取栈顶元素，并且移除它。
4.push（）向栈顶添加元素。
5.search（） 判断栈内是否存在该元素，若存在，则返回与栈顶的距离，若不存在则返回－1.
其次，它继承自Vector类。我们来看一下Vector的数据结构。通过源码我们可以看出，Vector的数据结构底层是由数据来存储的，也就不难发现，其可以通过index来对元素进行增删改查。这一点与顺序表相似。只不过它们数组扩容的方式不太一样。
简单看了Stack的源码，我们来想想它在Android当中的应用。最常用的我们应该想到的是Activity的启动模式。关于Android的四种启动模式，咱们在这就不展开了，后期在Android源码分析的时候再来分析。
关于堆栈的应用场景还有很多，比如计算机实现运算所使用的逆波兰表达式也是其中一种。对这块有兴趣的朋友可以看我另外一篇博客 数据结构之 栈和队列
在android中，队列的应用也是比较广泛的，如LinkedList，ArrayDeque，LinkedBlockingDeque等。还有我们最熟悉的Handler机制当中的MessageQueue。关于Handler机制，有兴趣的同学可以看我的另一篇文章：
Handler机制之源码解析。
栈和队列的实现原理其实很简单，但有一点我们要知道，它们的概念不是死的。比如说队列的基本概念是先进先出，但我们实际使用当中比如MessageQueue会给它加入一个时间优先级的概念，让后进的也可以先出。数据结构我们应该灵活应用来使其更符合我们的业务场景。
这一篇篇幅并不长，主要是觉得概念大家都懂，也容易理解，另外也引入了两篇博客进行补充。后期会在相关的案例当中更详细的去讲解到它们的应用。
下一节我们分析一下Hash表。
网友评论