数据结构基础（java）

一、数据结构的基本概念：
     1.数据(Data)
            数据是描述客观十四五的数值、字符以及能输入机器且能被处理的各种符号集合。
     2.数据元素(Data Element)
            数据元素是组成数据的基本单位，是数据集合的个体。
     3.数据对象(Data Object)
            数据对象谁性质相同的元素的集合，是数据的一个子集。
     4.数据结构(Data Structure)
            数据结构是指相互之间存在一种或多种特定关系的数据元素集合。
     5.数据类型(Data Type)
            数据类型是一组性质相同的集合以及定义这个值集合的一组数据操作的总称。
     6.算法：性能评价
            1.时间复杂度：使用大“O”表示法：比如：
              T(n) = O(1)表示常数型；
                        O(n)表示线性型；
                        O(n^2)表示平方型；
                        O(2^n)表示指数型；
                        O(log n)对数型；
                        O(n log n)二维型；
            2.空间复杂度：一个算法的占用空间是指算法实际占用的辅助空间总和。
               时间和空间要想两者兼顾是很难的，有时候需要根据实际的需求以及条件来舍其一，来换取另一个。

二、接下来正式进入数据结构：
    1、线性表：n个类型相同数据元素的有限集合。
                  (1) 特点：   (1)同一性, (2)有穷性,(3)有序性
                  (2)线性表在 java 中的实现：

List表示线性表：有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。：

ArrayList ：顺序表，线性表的顺序存储。底层使用数组实现。功能上也类似于数组。

(1).继承关系：

java.lang.Object
  java.util.AbstractCollection
      java.util.AbstractList
          java.util.ArrayList

(2).类的声明：

                 public class ArrayList

                 extends AbstractList

                 implements List, RandomAccess, Cloneable, Serializable

(3).实例化对象：

// 表示该 ArrayList 的元素类型是 Integer 型
//(java中的包装类型，上一篇文章中有所有基本类型的包装类)
        
List arrayList = new ArrayList<>();

arrayList 对象可以使用List的所有功能。

可以看到 ArrayList 实现了 List接口。所以 List接口的所有方法ArrayList也同样可以使用。绝大多数情况下使用ArrayList就足够了，因为相比较linkedList而言，ArrayList省时省力。除非是特定情况下使用 linkedList。

linkedList ：链表，线性表的链式存储。

(1).继承关系：

java.lang.Object
  java.util.AbstractCollection
      java.util.AbstractList
          java.util.AbstractSequentialList
              java.util.linkedList

(2).类的声明：

                 public class linkedList

                 extends AbstractSequentialList

                 implements List, Deque, Cloneable, Serializable

(3).实例化对象：linkedList对象可以完成链表的所有操作。

        //linkedList 对象可以可以完成链表的所有操作。
        List linkedList = new linkedList<>();

linkedList不仅实现了 List 接口还有Deque双端队列接口。可以进行一系列关于队列的操作。

2、Queue队列接口：

        什么是队列？队列是一种限定性线性表，他只允许在表的一端插入元素，另一端删除元素，所以队列有先进先出(First In First Out,FIFO)的特性。与我们日常生活中的排队是一样的道理。而双端队列则是允许在两端进行元素的插入和移除。

上面提到 linkedList 实现了Deque接口，那么通过一下代码实例化的Deque对象就可以完成Deque接口的所有操作:

        //queue对象是一个简单的队列,具体有如下操作:add(E e), element(), offer(E e), peek(), poll(), remove() 
        Queue queue = new linkedList<>();
        //deque对象时一个双端队列,对应可以完成双端队列的操作。
        Deque deque = new linkedList<>();

 Queue 和 Deque的一些方法是等效的：

3、Queue是线性结构的一种具体应用，线性结构还有另一种具体的应用，那就是栈（Stack）

        栈作为一种限定性线性表，是将线性比表的插入和删除操作限制为仅在表的一段进行，通常将表中允许操作的一段成为栈顶(Top)，另一端称为栈底（Bottom）

(1).继承关系：

java.lang.Object
  java.util.AbstractCollection
      java.util.AbstractList
          java.util.Vector
              java.util.Stack

(2).类的声明：

                 public class Stack

                               extends Vector

Stack 类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。

(3).实例化对象：

Stack stack = new Stack<>();

 
总结：以上是对java数据结构的一个入门介绍，对于 ArrayList 和 linkedList 一定要学会使用它的各种操作，以及能够完成自己的 List。对于Queue 和 Stack 首先要理解其含义，并且能够使用线性表来实现自己的队列和栈。对于java给定的队列和栈也要学会使用它的各项操作。