简述
在编程过程中，通常会遇到的一个问题就是，性能瓶颈。很多时候考虑的都是怎么去做横向扩展，但偏偏忽略掉了最基本的问题就是系统是否真的已经达到了瓶颈？
性能瓶颈通常的表象是资源消耗过多外部处理系统的性能不足；或者资源消耗不多但程序的响应速度却仍达不到要求。
而调优的方式就是寻找过度消耗资源的代码 和 寻找未充分使用资源但程序执行慢的原因和代码。基础决定高度就拿汽车来比较，通常不懂变速箱、发动机的原理但也是能开车，同样一个不懂数据结构和算法的人也能编程。很多人觉得基本的数据结构及操作已经在高级语言中封装,都可以直接调用库函数，那么到底有没有必要好好学习数据结构？
数据结构+算法＝程序
通常在程序中，遇到一个实际问题，充分利用数据结构，将数据及其之间的关系有效地存储在计算机中，然后选择合适的算法策略，并用程序高效实现，这才是提高程序性能的主要方式。
如果没有具备这块相应的知识，怎么完成上述的实现？如果脱离了原有的调用，怎么完成程序的高效实现？而所有的应用实现都依赖于基础，基础就是数据结构和算法。了解这块，才能做到无惧任何技术的演变。所有说基础决定高度！
基本的概念
数据结构表示数据在计算机中的存储和组织形式java算法研究，主要描述数据元素之间和位置关系等。选择适当的数据结构可以提高计算机程序的运行效率（时间复杂度）和存储效率（空间复杂度）。
数据结构的三种层次：
逻辑结构--抽象层： 主要描述的是数据元素之间的逻辑关系
物理结构--存储层： 主要描述的是数据元素之间的位置关系运算结构--实现层： 主要描述的是如何实现数据结构
每种逻辑结构采用何种物理结构来实现，并没有具体的规定。当一个结构，在逻辑结构中只有一种定义，而在物理结构中却有两种选择，那么这个结构就属于逻辑结构；
数据结构比较
常用的数据结构：
数据结构选择：
O符号
O在算法当中表述的是时间复杂度，它在分析算法复杂性的方面非常有用。常见的有：
O(1)：最低的复杂度，无论数据量大小，耗时都不变，都可以在一次计算后获得。哈希算法就是典型的O(1)O(n)：线性，n表示数据的量，当量增大java算法研究 数据结构与算法（java），耗时也增大，常见有遍历算法O(n²)：平方，表示耗时是n的平方倍，当看到循环嵌循环的时候，基本上这个算法就是平方级的，如：冒泡排序等O(log n)：对数，通常ax=n,那么数x叫做以a为底n的对数,也就是x=logan，这里是a通常是2，如：数量增大8倍，耗时只增加了3倍，二分查找就是对数级的算法java算法研究，每次剔除一半O(n log n)：线性对数，就是n乘以log n,按照上面说的数据增大8倍，耗时就是8*3=24倍，归并排序就是线性对数级的算法Array
在Java中，数组是用来存放同一种数据类型的集合，注意只能存放同一种数据类型。
//只声明了类型和长度
数据类型 [] 数组名称 = new 数据类型[数组长度];
//声明了类型，初始化赋值，大小由元素个数决定
数据类型 [] 数组名称 = {数组元素1，数组元素2，......}
大小固定，不能动态扩展(初始化给大了，浪费；给小了，不够用)，插入快，删除和查找慢
Array模拟实现
public class Array {
private int[] intArray;
private int elems;
private int length;
public Array(int max) {
length = max;
intArray = new int[max];
elems = 0;
}
/**
* 添加
* @param value
*/
public void add(int value){
if(elems == length){
System.out.println("error");
return;
}
intArray[elems] = value;
elems++;
}
/**
* 查找
* @param searchKey
* @return
*/
public int find(int searchKey){
int i;
for(i = 0; i < elems; i++){
if(intArray[i] == searchKey)
break;
}
if(i == elems){
return -1;
}
return i;
}
/**
* 删除
* @param value
* @return
*/
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
*/
public boolean update(int oldValue,int newValue){
int i = find(oldValue);
if(i == -1){
return false;
}
intArray[i] = newValue;
return true;
}
/**
* 显示所有
*/
public void display(){
for(int i = 0 ; i < elems ; i++){
System.out.print(intArray[i]+" ");
}
System.out.print("\n");
}
/**
* 冒泡排序
* 每趟冒出一个最大数/最小数
* 每次运行数量：总数量-运行的趟数(已冒出)
*/
public void bubbleSort(){
for(int i = 0; i < elems-1; i++){//排序趟数 n-1次就行了
System.out.println("第"+(i+1)+"趟：");
for(int j = 0; j < elems-i-1; j++){//每趟次数 (n-i) -1是防止下标越界，后面赋值用到了+1
if(intArray[j] > intArray[j+1]){ //控制按大冒泡还是按小冒泡
int temp = intArray[j];
intArray[j] = intArray[j+1];
intArray[j+1] = temp;
}
display();
}
}
}
/***
* 选择排序
* 每趟选择一个最大数/最小数
* 每次运行数量：总数量-运行的趟数(已选出)
*/
public void selectSort(){
for(int i = 0; i < elems-1; i++) {//排序趟数 n-1次就行了
int min = i;
for(int j = i+1; j < elems; j++){ //排序次数 每趟选择一个数出来，-1次
if(intArray[j] < intArray[min]){
min = j;
}
}
if(i != min ){
int temp = intArray[i];
intArray[i] = intArray[min];
intArray[min] = temp;
}
display();
}
}
/**
* 插入排序
* 每趟选择一个待插入的数
* 每次运行把待插入的数放在比它大/小后面
*/
public void insertSort(){
int j;
for(int i = 1; i < elems; i++){
int temp = intArray[i];
j = i;
while (j > 0 && temp < intArray[j-1]){
intArray[j] = intArray[j-1];
j--;
}
intArray[j] = temp;
}
display();
}
public static void main(String[] args) {
Array array = new Array(10);
array.add(6);
array.add(3);
array.add(8);
array.add(2);
array.add(11);
array.add(5);
array.add(7);
array.add(4);
array.add(9);
array.add(10);
// array.bubbleSort();
// array.selectSort();
array.insertSort();
// array.display();
// System.out.println(array.find(4));
// System.out.println(array.delete(1));
// array.display();
// System.out.println(array.update(2,6));
// array.display();
}
}
Stack
Stack()
Stack模拟实现
<p><pre>public class Stack {
//小贴士：通常可以利用栈实现字符串逆序，还可以利用栈判断分隔符是否匹配，如，可以正进反出，栈为空则成功。
/**基于数组实现的顺序栈，连续存储的线性实现，需要初始化容量**/
//固定数据类型
//private int[] array;
//动态数据类型
private Object[] objArray;
private int maxSize;
private int top;
public Stack() {
}
public Stack(int maxSize) {
if(maxSize > 0){
objArray = new Object[maxSize];
this.maxSize = maxSize;
top = -1;
}else{
throw new RuntimeException("初始化大小错误：maxSize=" + maxSize);
}
}
/**
* 入栈
* @param obj
*/
public void objPush(Object obj){
//扩容
grow();
//++在前表示先运算再赋值，优先级高，在后表示先赋值再运算，优先级低
objArray[++top] = obj;
}
/**
* 出栈
* @return
*/
public Object objPop(){
Object obj = peekTop();
//声明原顶栈可以回收空间(GC)
objArray[top--] = null;
return obj;
}
/**
* 查看栈顶
* @return
*/
public Object peekTop(){
if(top != -1){
return objArray[top];
}else{
throw new RuntimeException("stack is null");
}
}
/**
* 动态扩容
*/
public void grow(){
//