概念

数据结构表示的是计算机中的存储和组织形式，主要描述数据之间的位置关系等，选择合适的数据结构，可以提高程序的运行速率，减少存储空间。

数据的三种结构

• 数据的逻辑结构： 描述数据之间的逻辑关系 （集合、线性、树形和网状）

• 数据的存储结构： 主要描述数据元素之间的位置关系。（顺序、链式、索引和散列）

• 数据的操作集合： 主要描述如何实现数据结构

此次为大家着重介绍基于Java实现数据的逻辑结构。

数据的逻辑结构

• 集合结构

  1. 成员是无序的；

  2. 成员只在集合中出现一次；

• 线性结构

  1. 具有一对一关系的数据

  2. 存在前驱和后继

• 树形结构

  1.数据间存在一对多关系

• 网站结构

  1.数据间存在多对多的关系

Array基于Java实现

特点：

• 只能存储同一数据类型

• 大小固定，不能动态扩容

查询实现：

//查询后返回的为该数在此数组中的下标public int find(int searchKey){   int i;   for(i = 0; i < length; i++){       if(intArray[i] == searchKey)          break;   }   if(i == length){       return -1;    }       return i;  //返沪查找数据的索引下标}

添加实现：

// elems为数组下标索引；length为数组长度 public void add(int value){   if(elems == length){        System.out.println("error 数组已满");        return;   }   intArray[elems] = value;      elems++;}

删除实现：

//删除实现主要是通过传递的参数，//调用查询方法 查到了则执行删除 未查到则返回false。public boolean delete(int value){    int i = find(value);    if(i == -1){        return false;    }    for (int j = i; j < elems-1; j++) {    //后面的数据往前移        intArray[j] = intArray[j + 1];    }  elems--;  return true;}

更新实现：

 /**   * @param oldValue  需要替换的数据   * @param newValue  新的数据   * @return 布尔值 更新成功返回ture 否则false*/public boolean update(int oldValue,int newValue){     int i = find(oldValue);     if(i == -1){         return false;     }     intArray[i] = newValue;     return true;}

Stack基于Java实现

栈的特点

• 最主要的是先进后出；

• 是一种特殊的线性表，只能在表尾进行插入删除操作；

• 栈的所有插入和删除只能在栈顶进行。

动态扩容

    public void grow(){        if(top == maxSize-1){            maxSize = maxSize<<1;            objArray = Arrays.copyOf(objArray,maxSize);        }    }

出栈

   public Object objPop(){        Object obj = peekTop();        objArray[top--] = null;        return obj;    }

入栈

    public void objPush(Object obj){        //扩容        grow();        objArray[++top] = obj;    }

Queue基于Java实现

队列特点

先进先出的数据结构，类似于生活中的排队

使用Java实现常见的Queue方法

 //使用数组模拟一个arrayQueue类class ArrayQueue{    private int maxSize;    private int front; //队头    private int rear; // 队尾    private int arr[] ; // 数组 存放数据    //创造队列的构造器    public ArrayQueue(int arrmaxSize){        maxSize = arrmaxSize;        arr = new int [maxSize];        front = -1; //指向对头的前一个位置        rear = -1; //队尾的前一个位置    }    //判断队列是否满    public  boolean isFull(){        return rear == maxSize -1;    }    //是否为空    public boolean isEmpty(){        return rear == front;    }    //添加数据    public void addQueue(int n ){        if (isFull()){            System.out.println("队列满！");            return;        }else {            rear++; //后移            arr[rear] = n;        }    }    //出队列 获取数据    public int getQueue(){        //判断队列是否空        if(isEmpty()){            throw  new RuntimeException("队列为空！");        }        front++; //后移        return arr[front];    }    //显示队列    public void showQueue(){        if (isEmpty()){            System.out.println("无法便利！");        }        for (int i = 0; i < arr.length; i++) {            System.out.println(arr[i]);        }    }    //显示数据头    public int headQueue(){        //判断        if (isEmpty()){            System.out.println("为空！");        }        return arr[front+1];    }}