许吉友 - 运维

基本数据结构

数组

很常见,也很好理解,一维数组和多维数组

数组的基本操作

常见的数组(Arrays)面试问题

堆栈

撤销选项(Undo)几乎存在于每个应用程序中,但大家有没有想过它是如何工作的? 它的主要思路是:将你先前的工作状态转换为一个独一无二的数字(ID)并按照从新到旧的顺序存储在存储器中。 而这不是一个单纯的数组能够实现的,这也就是Stack能派上用场的地方。

Stack的现实例子可能是一堆垂直排列的成堆的书籍。为了获得位于中间位置的书,你需要移除放在它上面的所有书籍。这就是LIFO(后进先出)方法的工作原理。

这是包含三个数据元素(1,2和3)的堆栈图像,其中3位于顶部,并且将被最先移除:

堆栈的基本操作:

常见的堆栈(Stack)面试问题

队列

与堆栈(Stack)类似,队列(Queue)是另一种线性数据结构,以顺序的方式存储元素。堆栈(Stack)和队列(Queue)之间唯一明显的区别是,队列(Queue)不使用LIFO方法,而是执行FIFO方法,这是先进先出(First in First Out)的缩写。

一个完美的队列(Queue)的现实生活例子:一排人在售票亭排队等候。 如果一个新来的人来了,他们将从最后加入队伍,而不是从头开始 -- 站在前面的人将是最先获得票的,然后再离开队伍。

队列的基本操作

常见的Queue面试问题

链表

链表是另一个重要的线性数据结构,它最初可能看起来类似于数组(Arrays),但在内存分配,内部结构以及如何执行插入和删除的基本操作方面与数组有所不同。

链表就像一个节点链(chain of nodes),每个节点(Node)包含数据和指向链中后续节点的指针等信息。 有一个头指针,它指向链表的第一个元素,如果列表是空的,那么它只是指向空值(Null)或什么都没有。

链表用于执行文件系统,哈希表和邻接列表。

以下是链接列表的类型:

链表的基本操作:

常见的链接列表面试问题

哈希表

散列转换(Hashing,音译为哈希)是一个用于区分和标识不同对象并将每个对象存储于一些提前预设好的的独一无二的索引(称为 Key)的过程。因此,该对象以“键值对” (Key-Value pairs)的形式存储,而这些键值对的集合被称为“字典”。在需要查询某个对象时,使用该对象对应的键来进行搜索。散列有不同的数据结构,但最常用的数据结构是散列表/哈希表(Hash Table)。

散列表通常使用数组实现。

散列数据结构的性能取决于以下三个因素:

这是一个如何在数组中映射哈希的说明。该数组的索引是通过哈希函数计算的。

常见的有关Hashing的面试问题:

优先队列