栈:先进后出(底层用数组实现)
栈只有一个开口,先进去的就到最底下,后进来的就在前面,要是拿出去的话,肯定是从开口端拿出去,
所以说先进后出,后进先出。
数据结构:
java实现栈(基于数组):
/** * 栈只有一个开口,先进去的就到最底下,后进来的就在前面,要是拿出去的话,肯定是从开口端拿出去, * 所以说先进后出,后进先出。 */ public class MyStack { //底层实现是一个数组 private long[] arr; /** * 最上层的一个指针 栈顶 */ private int top; /** * 默认的构造方法 */ public MyStack(){ arr = new long[10]; top=-1; } /** * 增加数据 先把指针加一 * 然后指针指向最新的数据 */ public void push(int value){ //top++是top先不自加,在语句完后自加。| ++top先自加 然后使用top的值 arr[++top] = value; } /** * 移除数据 先把最顶层指针执行的数据return 然后指针减一 */ public long pop(){ //--top 是先执行top=top-1,然后再使用top的值 | top-- 是先使用top的值 然后 在执行top=top-1 return arr[top--]; } public static void main(String[] args) { MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.push(3); System.out.println(myStack.pop()); } }
main()方法中 3是最后push()进去 是最先pop()出来,先进后出,后进先出。
队列:先进先出(底层用数组实现)
队列有队头(front)和队尾(end),数据从队尾进入队列,从队头出队列,队头(front)指向队列的第一个数据,队尾(end)指向队列中的最后一个数据。
队列的数据结构
java实现队列(基于数组)
package javaee.net.cn.tree.ch10; public class MyQueue { //底层使用数组 private long[] arr; //队头 private int front; //队尾 private int end; /** * 默认构造方法 */ public MyQueue(){ arr = new long[10]; front=0; end = -1; } /** * 添加数据 从队尾插入 */ public void insert(long value){ arr[++end] = value; } /** * 删除数据,从队头删除 */ public long remove(){ return arr[front++]; } public static void main(String[] args) { MyQueue myQueue = new MyQueue(); myQueue.insert(1L); myQueue.insert(2L); System.out.println(myQueue.remove()); } }
main()方法中 1是先insert()进去 也是先remove()出来,所以说 先进先出。
链表实现队列
JDK中的LinkedList(底层用链表实现)
以上队列是以数组来模拟(比较简单),JDK API中的Queue队列底层是以链表来实现的。
LinkedList 类实现了Deque(双端队列)接口 并且具有
addFirst() addLast() getFirst() getLast() removeFirst() removeLast() 方法
使得LinkList可以作为 栈 队列 双向队列使用
至于LinkedList的实现原理,在这就不做多叙述了 大家可以参考API
链表
上面的栈和队列都是以数组模拟实现,但是JDK中LinkedList底层是链表实现的,现在我们看看什么是链表
链表是由一个个的节点构成的,节点(Node)分为两个部分,第一个部分(data)保存或者显示关于节点的信息,另一个部分存储下一个节点的地址。
链表最后一个节点存储地址的部分指向空值。
节点Node:
/** * 连接点 相当于是车厢 */ public class Node { //数据域 保存数据 public long data; //指针域 保存下一个节点的引用 public Node next; public Node(long value){ this.data=value; } }
而插入一个节点,对于单向链表,我们只提供在链表头插入,只需要将next指向原头节点,当前插入的节点设置为头节点即可。
/** * 插入一个节点,在头结点进行插入 */ public void insertFirst(long value){ Node node = new Node(value); node.next=first; first=node; }
删除一个节点,我们将该节点的上一个节点的next指向该节点的下一个节点。
如果被删除的是头结点,直接将头节点的下一个节点,赋值给头节点
/** * 删除方法 根据数据域进行删除 */ public Node delete(long value){ Node current = first; Node pre = null; while(current.data!=value){ if(current.next==null){ return null; } pre = current; current= current.next; } if(current == first){ first = first.next; }else{ pre.next=current.next; } return current; }
BlockingQueue
普通的队列没有考虑线程之间的同步,当多个线程操作同一个队列时,会导致并发问题。
BlockingQueue接口继承了Queue接口,BlockingQueue接口为多个线程操作同一个队列提供了四种处理方案(,对于不能立即满足但可能在将来某一时刻可以满足的操作)
抛出异常 | 特殊值 | 阻塞 | 超时 | |
插入 | add(e) |
offer(e) |
put(e) |
offer(e, time, unit) |
移除 | remove() |
poll() |
take() |
poll(time, unit) |
检查 | element() |
peek() |
不可用 | 不可用 |
其中方案一和方案二来自Queue接口,方案三和方案四是在BlockingQueue接口中新增的。
比如线程阻塞:
在通过put(e)方法向队列尾部添加元素时,如果队列已满,则当前线程进入阻塞状态,直到队列有剩余容量来添加元素,才退出阻塞。
在通过take()方法从队列头部删除并返回元素时,如果队列为空,则当前线程进入阻塞状态,直到从队列中成功删除并返回元素为止。
在java.util.concurrent包中 BlockingQueue接口主要有以下实现类