河北网站建设制作/百度联系电话多少

队列

队列(queue): first in first out …按照历史的顺序，将历史重演一遍
操作：

• 入队enqueue
• 出队 dequeue

队头 front
队尾 rear

双端队列 dequeue
优先队列： 谁的优先级高，谁先出队，，二叉堆实现

数组实现

public class MyQueue {/*** queue的实际大小  比 array.length 少 1 。。。坐标刚好对上*/private int[] array;private int front;/*** 队尾的位置,, 这个位置没有元素，，*/private int rear;public MyQueue(int capacity) {this.array = new int[capacity];}/*** 入队* @param element 入队的元素*/public void enQueue(int element) throws Exception{if((rear+1)%array.length == front){throw new Exception("队列已满");}array[rear] = element;rear = (rear+1)%array.length;}public int deQueue() throws Exception{if(rear == front){throw  new Exception("队列为空");}int deQueueElement = front;front = (front+1)%array.length;return deQueueElement;}public void output(){for (int i = front; i != rear ; i = (i+1)%array.length) {System.out.println(array[i]);}}public static void main(String[] args) throws Exception {MyQueue myQueue = new MyQueue(4);myQueue.enQueue(1);myQueue.enQueue(2);myQueue.enQueue(3);
//        myQueue.enQueue(4);myQueue.output();}
}

栈

栈：stack : first in last out …回溯方法，历史回溯
操作：

• 入栈 push
• 出栈 pop

栈顶 top
栈底 bottom

递归可以用栈代替，，，
应用： 面包屑导航

哈希表

hash table : 跟数组查找差不多，需要将key通过hash函数，位运算，转换成数组下标
操作：

• put
• get
• resize
  当散列表达到一定饱和度，key映射位置发生冲突的概率会逐渐提高，大量元素拥挤在相同的数组下标位置，形成很长的链表
  hashMap扩容因素: 1.capacity2.loadFactory , 当 hashmap.size> capacity * loadFactory 时候，会扩容： 1.创建一个新数组，为原来数组的2倍 2.将所有元素重新hash`

哈希冲突解决方法：

• 开放寻址法： 当一个key通过hash函数获得对应数组下标已经被占用时，寻找下一个空档位置
• 链表法

数据结构分类

• 物理结构
  • 顺序存储结构： 数组
  • 链式存储结构： 链表
• 逻辑结构
  • 线性结构
    • 顺序表
    • 栈
    • 队列
  • 非线性结构
    • 树
    • 图