数据结构面试题

数据结构是计算机存储、组织数据的方式。对于特定的数据结构(比如数组)，有些操作效率很高(读某个数组元素)，有些操作的效率很低(删除某个数组元素)。程序员的目标是为当前的问题选择最优的数据结构。

八种常用数据结构：

一、数组 分为一维数组和多维数组。 优点：查询某个元素比较方便，时间复杂度为O(1)。 缺点：构建时必须分配一段连续的空间，添加和删除元素时间复杂度为O(n)

二、链表 也是线性结构，是由一系列节点组成的链，每一个节点保存了数据及指向下一节点的指针。 优点：灵活分配内存空间，在O(1)时间内删除或添加元素。 缺点： 查询第k个元素需要O(k)时间。 三、栈 栈中元素采用先进后出，常用操作包括push()、pop()、isEmpty()、peek()。 对于栈中数据来说，所有操作在栈顶完成，只能查看栈顶部的数据，向栈顶压入数据，也只能从栈顶弹出数据。 四、队列 与栈类似，都采用线性结构存储数据。队列采用先进先出。 对于队列的数据来说，只允许在队尾查看和添加数据，在队头查看和删除数据。双端队列的头尾都能在O(1)的时间内进行数据的查看、添加和删除。 五、图 由多个节点组成，节点间可以互相连接组成一个网络。图分为有向图和无向图。 六、树 分层的数据结构，由节点和连接节点的边组成。树是一种特殊的图，与图的区别在于没有循环。 树的节点可以分为根节点、子节点，子节点又包括非叶子节点和叶子节点。 二叉树和二叉查找树是最常用的树。 七、前缀树 与树类似，处理字符串问题非常高效。 八、哈希表