Question

八种数据结构特点

Answer 1

数据结构：计算机存储、组织数据的方式。程序员的目标是为当前的问题选择最优的数据结构。

八种数据结构：数组，栈，链表，队列，堆，图，树，散列表，每种数据结构都有其特殊的存储方式。

概念：

一维数组：数组元素+数组索引

多维数组：数组的元素也是数组

基本操作：insert,get,delete（删除某个索引处的数组）,size(获取数组长度）

题目：

查找数组第二小的元素

查找第一个没有重复的数组元素

合并2个排序号的数据

重新排列数组中的正数和负数

特点：栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出。栈中的元素采用LIFO (Last In First Out)，即后进先出。

基本操作：Push（栈顶插入元素），Pop(返回栈最上方的元素，并删除），isEmpty（查询栈是否为空），Top（返回最上方元素，并不删除）

题目：使用栈计算后缀表达式、使用栈为栈中的元素排序、检查字符串中的括号是否匹配正确

使用场景：栈常应用于实现递归功能方面的场景，例如斐波那契数列。撤回，即Ctrl+Z，是我们最常见的操作之一，大多数应用都会支持这个功能。你知道它是怎么实现的吗？答案是这样的：把之前的应用状态(限制个数)保存到内存中，最近的状态放到第一个。这时，我们需要栈(stack)来实现这个功能。

概念：队列(Queue)与栈类似，都是采用线性结构存储数据。它们的区别在于，栈采用LIFO方式，而队列采用先进先出，即FIFO(First in First Out)。

使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。

基本操作：Enqueue—在队列末尾插入元素，Dequeue—将队列第一个元素删除i，sEmpty—查询队列是否为空，Top—返回队列的第一个元素

习题：使用队列实现栈，倒转队列的前K个元素，使用队列将1到n转换为二进制。

概念“链表(Linked List)也是线性结构，它与数组看起来非常像，但是它们的内存分配方式、内部结构和插入删除操作方式都不一样。链表是一系列节点组成的链，每一个节点保存了数据以及指向下一个节点的指针。链表头指针指向第一个节点，如果链表为空，则头指针为空或者为null。链表分为：单向链表，双向链表。

使用场景：链表可以用来实现文件系统、哈希表和邻接表。

基本操作：InsertAtEnd—在链表结尾插入元素，InsertAtHead—在链表开头插入元素，Delete—删除链表的指定元素，DeleteAtHead—删除链表第一个元素，Search—在链表中查询指定元素，isEmpty—查询链表是否为空

题目：倒转1个链表，检查链表中是否存在循环，返回链表倒数第N个元素，移除链表中的重复元素

概念：图(graph)由多个节点(vertex)构成，节点之间阔以互相连接组成一个网络。(x, y)表示一条边(edge)，它表示节点x与y相连。边可能会有权值(weight/cost)。

分类：无向图，有向图

表现形式：邻接矩阵(Adjacency Matrix)，邻接表(Adjacency List)

遍历图的两种算法：广度优先搜索(Breadth First Search)，深度优先搜索(Depth First Search)

常见题目：

实现广度优先搜索，实现深度优先搜索，检查图是否为树，统计图中边的个数，使用Dijkstra算法查找两个节点之间的最短距离。

树(Tree)是一个分层的数据结构，由节点和连接节点的边组成。树是一种特殊的图，它与图最大的区别是没有循环。树被广泛应用在人工智能和一些复杂算法中，用来提供高效的存储结构。

常见树：N叉树(N-ary Tree)，平衡树(Balanced Tree)，二叉树(Binary Tree)，二叉查找树(Binary Search Tree)，平衡二叉树(AVL Tree)，红黑树(Red Black Tree)，2-3树(2–3 Tree)

题目：计算树的高度，查找二叉平衡树中第K大的元素，查找树中与根节点距离为k的节点，查找二叉树中某个节点所有祖先节点。

哈希(Hash)将某个对象变换为唯一标识符，该标识符通常用一个短的随机字母和数字组成的字符串来代表。哈希可以用来实现各种数据结构，其中最常用的就是哈希表(hash table)。

哈希表通常由数组实现。

哈希表的性能取决于3个指标：

哈希函数哈希表的大小哈希冲突处理方式

题目：查找数组中对称的组合，确认某个数组的元素是否为另一个数组元素的子集，确认给定的数组是否互斥。

前缀树(Prefix Trees或者Trie) 与树类似，用于处理字符串相关的问题时非常高效。它可以实现快速检索，常用于字典中的单词查询，搜索引擎的自动补全甚至IP路由。

参考资料： http://www.cnblogs.com/williamjie/p/9558015.html