程序员必须知道的数据结构：队列与栈

老王说编程

关注

发布于: 2021 年 03 月 06 日

在数据结构中，队列与栈的产生主要是为了满足某些特殊的编程运算，数据结构最大的一个特点就是为算法提供基础，使用不用的数据结构甚至能直接影响算法的好坏，多数情况下，数据结构与算法是一种相辅相成的关系。

栈：和我们上节说到的一样，栈也是一种线性的存储结构。但是它限制了只能在线性表的尾部进行数据插入和删除操作，根据一张图示来进行形象说明。

栈的数据存放原则遵循先进后出的数据存放原则，因为它的数据出口只有一个，那就是栈顶，也就是上面所说的栈尾。如果一个栈里面没有数据元素的存放又被称之为空栈，这种数据结构比较常用的场景就是程序计算中关于后缀表达式的计算。

队列：同样队列也是线性存储结构，和栈的数据处理方式正好是相反的，它是在线性表的一端进行数据插入，另一端则进行删除操作，根据图示来进行说明。

队列的数据存放原则遵循先进先出的存放原则，因为它拥有两个出口，一个出口专门负责数据进入、另一个出口专门负责数据出去，数据进入对应的就是数据插入、数据出去对应的就是数据删除。

在 Java 语言中，同样有关于队列与栈的实例对象的实现。队列对应的接口对象是 Queue、栈对应的则是 Stack，下面来看一下其中的部分源码分析。


// stack 栈对应的 push() 与 pop() // 向栈添加数据元素public E push(E item) {        addElement(item);
        return item;    }// 删除栈底数据元素public synchronized E pop() {        E       obj;        int     len = size();
        obj = peek();        removeElementAt(len - 1);
        return obj;    }

复制代码

Stack（）有自己的实例化对象，Queue（）只定义了接口，它是在其他表的对象中实现的，我们选择使用 LinkedList<Object> 对 Queue（）的实例化源码来说明。


// LinkedList 实现了 Deque 接口public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{// Deque 接口又继承自 Queue 队列接口public interface Deque<E> extends Queue<E> {}// 那么相当于 LinkedList 实例实现了 Queue 队列

复制代码

根据源码分析，我们寻找到 LinkedList 实例实现了队列接口，那么我们来看一下它的入队方法是怎样的。


// Queue 队列的入队方法 offer()public boolean offer(E e) {        // 内部调用 add() 方法        return add(e);    }// 实际上这里复用了 LinkedList 的添加元素方法，因为这个操作他们都是同样向链表添加数据public boolean add(E e) {        linkLast(e);        return true;    }

复制代码

注意：线性表与链表通常也是一起使用的，所以说数据结构外部使用线性表、内部再使用链表是非常的常见的数据结构的组装形式。

更多精彩前往微信公众号【老王说编程】>>>

发布于: 2021 年 03 月 06 日阅读数: 14

原文链接:【http://xie.infoq.cn/article/8a4139f64b14fd829a619813d】。文章转载请联系作者。

老王说编程

关注

还未添加个人签名 2021.03.03 加入

微信公众号【Python 集中营】作者，擅长后端编程语言开发，每天更新原创文章，专注于 Python实战干货技术，快来关注我吧！

发布

暂无评论

创作场景

程序员必须知道的数据结构：队列与栈

老王说编程

评论