数据结构——线性表：栈、队列

栈

栈的特点

• 先进后出

栈的实现函数以及时间复杂度

Stack<E> stack //创建栈对象
stack.push()   //向栈中添加元素       时间复杂度：O(1) 均摊
stack.pop()	   //将栈中的元素弹出	 时间复杂度：O(1) 均摊
stack.peek()   //获取当前栈顶元素	 时间复杂度：O(1) 
stack.getSize()//获取栈长度			 时间复杂度：O(1) 
stack.isEmpty()//判断栈是否为空，为空返回true    时间复杂度：O(1) 
1
2
3
4
5
6

队列

队列特征

• 只能从一端（队尾）添加元素，从另一端（队首）取出元素

队列的实现以及时间复杂度

Queue<E> queue   //创建队列对象
queue.enqueue()  //向队列中添加元素       时间复杂度：O(1) 均摊
queue.dequeue()  //从队列中取出一个元素	 时间复杂度：O(n) 原因，队列所有元素前移 均摊
queue.getFront() //获取队列的首元素	     时间复杂度：O(1) 
queue.getSize()  //获取队列长度			 时间复杂度：O(1) 
queue.isEmpty()  //判断队列是否为空，为空返回true    时间复杂度：O(1) 
　　add        增加一个元索                     如果队列已满，则抛出一个IIIegaISlabEepeplian异常
　　remove   移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
　　element  返回队列头部的元素             如果队列为空，则抛出一个NoSuchElementException异常
　　offer       添加一个元素并返回true       如果队列已满，则返回false
　　poll         移除并返问队列头部的元素    如果队列为空，则返回null
　　peek       返回队列头部的元素             如果队列为空，则返回null
　　put         添加一个元素                      如果队列满，则阻塞
　　take        移除并返回队列头部的元素     如果队列为空，则阻塞
       drainTo(list)   一次性取出队列所有元素


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

循环队列

• 解决出队是 时间复杂度问题
  LoopQueue

使用Stream的方式遍历

使用Stream的方式遍历
1、将数组转换为stream,有两种方式: Stream.of(arr),Arrays.stream(arr)
2、使用Arrays.stream()转换时，如果是包装类，转换后的类型为Stream，基础类型，转换后为IntStream
3、使用Stream.of()转换时，如果是包装类，转换后的类型为Stream，基础类型，转换后为Stream