Introduction to Data Structures 数据结构简介
What is data:
Data is the collection of different numbers, symbols, and alphabets to represent information.
什么是数据：
数据是用来表示信息的不同数字、符号和字母的集合
What is data structure:
A data structure is a group of data elements that provides the easiest way to store and perform different actions on the data of the computer. A data structure is a particular way of organizing data in a computer so that it can be used effectively. The idea is to reduce the space and time complexities of different tasks.
The choice of a good data structure makes it possible to perform a variety of critical operations effectively. An efficient data structure also uses minimum memory space and execution time to process the structure.
A data structure has also defined an instance of ADT. ADT means Abstract Data Type. It is formally defined as a triplet[D, F, A].
D: Set of the Domain
F: Set of the Operations
A: Set of Axioms
什么是数据结构：
数据结构是一组数据元素，他们提供在一台电脑上最简单的方法来储存和实现不同的操作。一种数据结构是一种特定的管理数据的方法，能够使数据得到有效的运用。其想法是减少完成不同功能所需要的时间和空间复杂度.
选择好的数据结构能够让有效的执行许多重要的操作变得可能。一个有效的数据结构在实现的时候往往占用最少的内存空间和执行时间。
一种数据结构也被定义成一个抽象数据类型（ADT）的实现。抽象数据类型ADT往往包含三个要素（D、F、A）：
D: 定义的集合
F: 操作的集合
A: 公理的集合
Type of data structure:
Linear Data Structure
Elements are arranged in one dimension, also known as linear dimension
Example: lists, stack, queue, etc.
Non-Linear Data Structure
Elements are arranged in one-many, many-one and many-many dimensions
Example: tree, graph, table, etc.
数据结构的种类：
线性数据结构
元素在一个维度之内排列，这个维度也叫做线性维度
例子：列表，栈，队列，等等
非线性数据结构
元素在一乘多，多乘一或者多乘多维度排列
例子：树，图，表等等
Data structures are used in various fields such as:
Operating System
Graphics
Computer Design
Blockchain
Genetics
Image Processing
Simulation
......
数据结构常用于各种领域，例如：
操作系统
图形学
计算机设计
区块链
遗传学
图像处理
模拟
......
1. Array 数列
An array is a collection of data items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This make it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array)
一个数列是在连续的内存空间存储的数据元素的集合。其目的是将相同类型的数据存储在一起。这能够让计算每个元素的存储位置变得更加简单，只需要把偏移量加到一个基础数值上，也就是数组第一个元素的的内存位置（通常由数组的名称表示）
2. Linked Lists 链表
Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.
和数列相同的，链表也是是一种线性数据结构；和数列不同的是，链表不是在连续的空间之内存储的，而是通过指针的方法连接起来。
3. Stack 栈
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). In stack, all insertion and deletion are permitted at only one end of the list
栈是一种线性数据结构，在对其进行操作的时候要遵循特定的顺序，这个顺序是FILO先入后出或者叫做LIFO后入先出。在栈中，所有的插入和删除操作都只允许在列表的一段进行。
Mainly the following basic operations are performed in the stack:
Initialize: Make a stack empty
Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
Peek or Top: Returns top element of the stack.
isEmpty: Returns true if the stack is empty, else false.
栈主要需要实现以下基本功能：
Initialize初始化：初始化一个空栈
Push入栈：将一个元素入栈，如果栈已经满了，则称为溢出
Pop出栈：将一个元素出栈，如果栈已经是空栈，则称为下溢
Peek/Top查看栈顶元素：返回栈顶的元素
isEmpty判断是否为空：如果是空栈返回true，否则返回false
4. Queue 队列
Like Stack, Queue is a linear data structure which follows a particular order in which the operations are performed. The order is FIFO (First In First Out). In the queue, items are inserted at one end and deleted from the other end. A good example of the queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we first remove the item the most recently added; in a queue, we remove the item the least recently added.
和栈相同的是，队列也是一个按照特定顺序执行操作的线性数据结构。它所遵循的顺序是FIFO先入先出。在队列中，元素从一头插入并且从另一头取出。栈的一个好的的例子就是资源的任何使用者队列，先出现的使用者会先提供服务。队列和栈的区别就是在移出时的顺序，栈会优先移出最近入栈的元素，而队列则会优先移出最先进入队列的元素
Mainly the following basic operations are performed on queue:
Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition
Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition
Front: Get the front item from the queue
Rear: Get the last item from the queue
队列主要需要实现以下基本功能：
Enqueue入列：向队列中添加一个元素。如果队列已经满了，称为溢出
Dequeue出列：从队列中删除一个元素，最先进入队列的元素最先删除，如果队列已经空了，成为下溢
Front查看头元素：获取队列头部的元素
Rear查看尾元素：获取队列尾部的元素
5. Binary Tree 二叉树
Unlike Arrays, Linked Lists, Stacks and Queues, which are linear data structures, trees are hierarchical data structures. A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. It is implemented mainly using Links.
A Binary Tree is represented by a pointer to the topmost node in the tree. If the tree is empty, then the value of the root is NULL. A Binary Tree node contains the following parts.
data
Pointer to the left child
Pointer to the right child
与数列、列表、栈和队列这些线性数据结构不同，二叉树是分层的数据结构。一个二叉树是一个树状结构，每个节点都有至多两个子节点，分别称为左子节点和右子节点。二叉树通常用链表实现。
二叉树由树的最顶端的节点来表示，如果树是空的，那么根节点的值是NULL。一个二叉树包括下列部分：
数据
指向左子节点的指针
指向右子节点的指针
6. Binary Search Tree 二叉查找树
A Binary Search Tree (BST) is a Binary Tree with the following additional properties:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
The left and right subtree each must also be a binary search tree.
二叉查找树（BST）是具有如下特征的一个二叉树：
左子树所包含的节点的数据小于该节点的数据
右子树所包含的节点的数据大于该节点的数据
左子树和右子树分别也都是二叉查找树BST
7. Heap 堆
A Heap is a special Tree based data structure in which the tree is a complete binary tree. Generally, Heaps can be of two types:
Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it's children. The same property must be recursively true for all sub-trees in that Binary Tree.
一个堆是一种由完全二叉树实现的特殊的树状结构，通常有如下两种属性的堆：
最大堆：在一个最大堆中根节点的数据大于他的所有子节点中的数据。这样一条属性必须对这个二叉树的所有子树递归的满足
最小堆：在一个最小堆中根节点的数据小于他的所有子节点中的数据。这样一条属性必须对这个二叉树的所有子树递归的满足
8. Hashing Data Structure 散列数据结构
Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends on the efficiency of the hash function used.
Let a hash function H(x) maps the value x at the index x%10 in an Array. For example, if the list of values is [11, 12, 13, 14, 15] it will be stored at positions {1, 2, 3, 4, 5} in the array or Hash table respectively.
散列表是一种重要的数据结构，用一种特殊的函数将一个给定的值和一个特定的键映射到一起，以实现快速的元素查找，称作哈希函数。映射的效率取决于所使用的哈希函数的效率。
例如，让一个哈希函数将值x映射到一个数列中x%10的位置。如果这个列表是[11, 12, 13, 14, 15],那么他们就会被分别储存在数列或者被称作哈希表的第{1, 2, 3, 4, 5}的位置。
9. Matrix 矩阵
A matrix represents a collection of numbers arranged in an order of rows and columns. It is necessary to enclose the elements of a matrix in parentheses or brackets.
矩阵表示一个按照行和列的顺序排列的数据集合。矩阵中的元素往往用中括号或者小括号括起来。
10. Trie 字典树
Trie is an efficient information retrieval data structure. Using Trie, search complexities can be brought to an optimal limit (key length). If we store keys in the binary search tree, a well balanced BST will need time proportional to O(MlogN), where M is a maximum string length and N is the number of keys in the tree. Using Trie, we can search the key in O(M) time. However, the penalty is on Trie storage requirements.
字典树是一种有效的信息检索数据结构。通过字典树，查找的时间复杂度能够降低至一个最优的极限。如果我们将数据存放在二叉查找树中，一个较为平衡的二叉查找树能够具备O(MlogN)的时间复杂度，其中M是字符串长度，N是树中的数据数量。通过字典树，我们能将时间复杂度缩短到O(M)，代价是需要更多的存储空间。
参考：geeksforgeeks.org
