• 栈Stack

    目录

    数组实现的栈结构

    java预定义的栈实现

    总结自定义栈

    顺序栈和链式栈 

    Queue

    1、阻塞和非阻塞  

     阻塞队列

     非阻塞队列

     2、有界和无界

    非阻塞队列

     阻塞队列

     Queue的实现

     五个队列所提供的各有不同

    栈的实现可以有数组实现的顺序栈和链表结构的链式栈

    数组实现的栈结构

    如果需要一个支持动态扩容的顺序栈，则底层还需要以来一个支持动态扩容的数组，将原来的数据搬移到新数组中。也可以使用顺序栈支持动态扩容。

    1. public class ArrayStack {
    2. 	private Object[] items;  //栈中存放的数据
    3. 	private int size;  // 栈中存放数据的个数
    4. 	
    5. 	public ArrayStack() {
    6. 		this(10);
    7. 	}
    8. 	public ArrayStack(int capacity) {
    9. 		items=new Object[capacity];
    10. 	}
    11. 	//数据压栈--将数据存储在栈顶
    12. 	public boolean push(Object item) {
    13. 		//如果栈已经满了则不允许再添加数据
    14. 		if(size==items.length)
    15. 			return false;
    16. 		items[size++]=item;
    17. 		return true;
    18. 	}
    19. 	//数据弹栈--将数据栈栈顶的数据获取出来，同时删除栈顶数据
    20. 	public Object pop() {
    21. 		//如果栈中没有数据则返回为null
    22. 		if(size==0)
    23. 			return null;
    24. 		return items[--size];
    25. 	}
    26. }

    java预定义的栈实现

    public class Stack extends Vector 
     实现方式为自定义实现的可变长数组，线程安全

    1. E push(E item) 把项压入堆栈顶部
    2. synchronized E pop() 移除堆栈顶部的对象，并作为此函数的值返回该对象
    3. synchronized E peek() 查看堆栈顶部的对象，但不从堆栈中移除它
    4. boolean empty() 测试堆栈是否为空
    5. synchronized int search(Object o) 返回对象在堆栈中的位置，以 1 为基数
    1. public class Test1 {
    2.  
    3. 	public static void main(String[] args) {
    4. 		Stack stack = new Stack<>();
    5. 		for(int i=1;i<=5;i++)
    6. 			stack.push(i);
    7. 		Integer kk=stack.pop();
    8. 		System.out.println(kk+"::"+stack.size());
    9. 		int pos=stack.search(Integer.valueOf(4));
    10. 		System.out.println("4位于栈中的索引号为"+pos);//1，获取的位置从栈顶开始计算，序号从1开始
    11. 		Integer kk2=stack.peek();
    12. 		System.out.println(kk2+"::"+stack.size());
    13. 		while(!stack.empty())
    14. 			System.out.println(stack.pop());
    15. 		System.out.println(stack.size());
    16. 	}
    17. }

    总结自定义栈

    栈是一种用于存储数据的简单数据结构，栈与线性表的最大区别是数据的存取的操作，可以这样认为栈Stack是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶Top，不可操作的一端称为栈底Bottom，同时把插入元素的操作称为入栈Push，删除元素的操作称为出栈Pop。若栈中没有任何元素，则称为空栈

    顺序栈和链式栈 

    1. public class Test2 {
    2. 	public static void main(String[] args) {
    3. 		Stack s = new SeqStack();
    4. 		System.out.println("是否为空" + s.empty());
    5. 		for (int i = 0; i < 5; i++)
    6. 			s.push(i);
    7. 		System.out.println("栈顶数据为" + s.peek());
    8. 		while (!s.empty())
    9. 			System.out.println(s.pop());
    10.  
    11. 	}
    12. }
    13.  
    14. //定义接口
    15. interface Stack {
    16. 	// 栈是否为空
    17. 	boolean empty();
    18.  
    19. 	// data元素入栈
    20. 	void push(T data);
    21.  
    22. 	// 返回栈顶元素,未出栈
    23. 	T peek();
    24.  
    25. 	// 出栈,返回栈顶元素,同时从栈中移除该元素
    26. 	T pop();
    27. }
    28.  
    29. //如果不考虑编程成本，下一步应该定义抽象类，在抽象类中添加公共方法
    30. /*
    31.  * 顺序栈，顾名思义就是采用顺序表实现的的栈，顺序栈的内部以顺序表为基础，实现对元素的存取操作，
    32.  * 当然还可以采用内部数组实现顺序栈，这里使用内部数据组来实现栈，至于以顺序表作为基础的栈实现
    33.  */
    34. class SeqStack implements Stack, Serializable {
    35. 	// 栈顶指针，-1代表空栈
    36. 	private int top = -1;
    37. 	// 容量大小默认为10
    38. 	private int capacity = 10;
    39. 	// 存放元素的数组
    40. 	private T[] array;
    41. 	private int size;
    42.  
    43. 	public SeqStack() {
    44. 		array = (T[]) new Object[capacity];
    45. 	}
    46.  
    47. 	// 一般情况下应该方法名称为getSize，但是遵循一般的使用习惯，所以命名为size()
    48. 	public int size() {
    49. 		return size;
    50. 	}
    51.  
    52. 	@Override
    53. 	public boolean empty() {
    54. 		return this.top == -1;
    55. 	}
    56.  
    57. 	// 添加元素,从栈顶(数组尾部)插入
    58. 	public void push(T data) {
    59. 		// 判断容量是否充足
    60. 		if (size == array.length)
    61. 			ensureCapacity(size * 2 + 1);// 扩容
    62. 		// 从栈顶添加元素
    63. 		array[++top] = data;
    64. 		size++;
    65. 	}
    66.  
    67. 	private synchronized void ensureCapacity(int len) {
    68. 		Object[] res = new Object[len];
    69. 		System.arraycopy(array, 0, res, 0, this.size);
    70. 		this.array = (T[]) res;
    71. 	}
    72.  
    73. 	// 获取栈顶元素的值,不删除
    74. 	public T peek() {
    75. 		if (empty())
    76. 			throw new EmptyStackException();
    77. 		return array[top];
    78. 	}
    79.  
    80. 	// 从栈顶(顺序表尾部)删除
    81. 	public T pop() {
    82. 		if (empty())
    83. 			throw new EmptyStackException();
    84. 		size--;
    85. 		return array[top--];
    86. 	}
    87.  
    88. }
    89.  
    90. class EmptyStackException extends RuntimeException {
    91. 	private static final long serialVersionUID = -4870633979582008865L;
    92.  
    93. 	public EmptyStackException() {
    94. 		super("栈中没有数据");
    95. 	}
    96.  
    97. 	public EmptyStackException(String message, Throwable cause, boolean enableSuppression, boolean writableStackTrace) {
    98. 		super(message, cause, enableSuppression, writableStackTrace);
    99. 	}
    100.  
    101. 	public EmptyStackException(String message, Throwable cause) {
    102. 		super(message, cause);
    103. 	}
    104.  
    105. 	public EmptyStackException(String message) {
    106. 		super(message);
    107. 	}
    108.  
    109. 	public EmptyStackException(Throwable cause) {
    110. 		super(cause);
    111. 	}
    112.  
    113. }

    Queue

    Queue队列就是一个先入先出FIFO的数据结构

    队列是一种特殊的线性表，遵循先入先出、后入后出的基本原则，一般来说，它只允许在表的前端进行删除操作，而在表的后端进行插入操作，但是java的某些队列运行在任何地方插入删除；比如常用的LinkedList集合，它实现了Queue接口，因此可以理解为LinkedList就是一个队列

    1. 接口定义
    2.   public interface Queue extends Collection {
    3.   	 boolean add(E e);  在队尾添加数据
    4.     boolean offer(E e); 在LinkedList中就是使用add提供的实现
    5.     
    6.     E remove();  删除队列头部的数据，同时返回删除的数据
    7.     E poll();
    8.     
    9.     E element(); 获取队列头部的数据，并不会执行删除操作
    10.     E peek();
    11.    }

     队列主要分为阻塞和非阻塞，有界和无界、单向链表和双向链表之分

    1、阻塞和非阻塞  

     阻塞队列

    入列(添加元素)时，如果元素数量超过队列总数，会进行等待（阻塞），待队列的中的元素出列后，元素数量未超过队列总数时，就会解除阻塞状态，进而可以继续入列；
    出列(删除元素)时，如果队列为空的情况下，也会进行等待（阻塞），待队列有值的时候即会解除阻塞状态，进而继续出列；
    阻塞队列的好处是可以防止队列容器溢出；只要满了就会进行阻塞等待；也就不存在溢出的情况；只要是阻塞队列，都是线程安全的；

     非阻塞队列

    不管出列还是入列，都不会进行阻塞，
    入列时，如果元素数量超过队列总数，则会抛出异常，
    出列时，如果队列为空，则取出空值；
    一般情况下，非阻塞式队列使用的比较少，一般都用阻塞式的对象比较多；阻塞和非阻塞
    队列在使用上的最大区别就是阻塞队列提供了以下2个方法：
    出队阻塞方法 ： take()
    入队阻塞方法 ： put()

     2、有界和无界

    有界：有界限，大小长度受限制
    无界：理论上来说无限大小，其实说是无限大小，其实是有界限的，只不过超过界限时就会
    进行扩容，就行ArrayList 一样，在内部动态扩容

    非阻塞队列

    1、ConcurrentLinkedQueue 单向链表结构的无界并发队列, 非阻塞队列，由CAS实现线程安
    全，内部基于节点实现 
    2、ConcurrentLinkedDeque双向链表结构的无界并发队列, 非阻塞队列，由CAS实现线程安全   
    3、PriorityQueue 内部基于数组实现，线程不安全的队列

     阻塞队列

    1、DelayQueue 一个支持延时获取元素的无界阻塞队列
    2、LinkedTransferQueue一个由链表结构组成的无界阻塞队列。
    3、ArrayBlockingQueue有界队列，阻塞式,初始化时必须指定队列大小，且不可改变；底层由数组实现；
    4、SynchronousQueue最多只能存储一个元素，每一个put操作必须等待一个take操作，否则不能继续添加元素
    5、PriorityBlockingQueue一个带优先级的队列，而不是先进先出队列。元素按优先级顺序被
    移除，而且它也是无界的，也就是没有容量上限，虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError 错误；

    Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Deque接口 

    1. 双向队列接口Deque
    2.  public interface Deque extends Queue {
    3.      void addFirst(E e); 在队列头部添加数据
    4.      	   boolean offerFirst(E e);
    5.      void addLast(E e);  在队尾添加数据
    6.          boolean offerLast(E e);
    7.      E removeFirst(); 从对头中删除数据，同时返回删除的数据
    8.          E pollFirst();
    9.      E removeLast();  从队尾伤处数据
    10.          E pollLast();
    11.      E getFirst(); 从对头获取数据
    12.          E peekFirst();
    13.      E getLast(); 从队尾获取数据
    14.          E peekLast();
    15.   }

     Queue的实现

    1、没有实现的阻塞接口的LinkedList： 
    实现了java.util.Queue接口和java.util.AbstractQueue接口
    内置的不阻塞队列： PriorityQueue 和 ConcurrentLinkedQueue
    PriorityQueue 类实质上维护了一个有序列表。加入到Queue中的元素根据它们的天然排序（通过其java.util.Comparable实现）或者根据传递给构造函数的java.util.Comparator实现来定位。
    ConcurrentLinkedQueue是基于链接节点的、CAS实现线程安全的队列。并发访问不需要同步。

    因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小，ConcurrentLinkedQueue
    对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。
    实现阻塞接口的：
    java.util.concurrent中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的FIFO数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。 

     五个队列所提供的各有不同

    1.  ArrayBlockingQueue ：一个由数组支持的有界队列。
    2. LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。
    3.  PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。
    4.  DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。
    5.  SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制
    add   增加一个元索    如果队列已满，则抛出一个IllegalStateException异常
    offer 添加一个元素并返回true 如果队列已满，则返回false
     
    remove    移除并返回队列头部的元素如果队列为空，则抛出一个NoSuchElementException异常
    poll       移除并返问队列头部的元素如果队列为空，则返回null
    element返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
    peek返回队列头部的元素   如果队列为空，则返回null
    put 添加一个元素 如果队列满，则阻塞
    take 移除并返回队列头部的元素如果队列为空，则阻塞

    阻塞队列的操作可以根据它们的响应方式分为以下三类：add、removee和element操作在你试
    图为一个已满的队列增加元素或从空队列取得元素时 抛出异常。当然，在多线程程序中，队列
    在任何时间都可能变成满的或空的，所以你可能想使用offer、poll、peek方法。这些方法在
    无法完成任务时 只是给出一个出错示而不会抛出异常。

    注意：poll和peek方法出错进返回null。因此，向队列中插入null值是不合法的 

    最后有阻塞操作put和take。put方法在队列满时阻塞，take方法在队列空时阻塞。

    LinkedBlockingQueue的容量是没有上限的（说的不准确，在不指定时容量为Integer.MAX_VALUE，不要然的话在put时怎么会受阻呢），但是也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO先进先出排序元素。

    ArrayBlockingQueue在构造时需要指定容量， 并可以选择是否需要公平性，如果公平参数被设置true，等待时间最长的线程会优先得到处理（其实就是通过将ReentrantLock设置为true来 达到这种公平性的：即等待时间最长的线程会先操作）。通常，公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队 列，此队列按 FIFO（先进先出）原则对元素进行排序。

    PriorityBlockingQueue是一个带优先级的 队列，而不是先进先出队列。元素按优先级顺序被移除，该队列也没有上限（看了一下源码，PriorityBlockingQueue是对 PriorityQueue的再次包装，是基于堆数据结构的，而PriorityQueue是没有容量限制的，与ArrayList一样，所以在优先阻塞 队列上put时是不会受阻的。
    虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError）但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。另外，往入该队列中的元 素要具有比较能力。

    DelayQueue（基于PriorityQueue来实现的）是一个存放Delayed 元素的无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用 null 元素

  • 相关阅读:
    C语言学生信息管理系统
    BHQ淬灭试剂BHQ-2 acid|cas:1214891-99-2|BHQ-2 酸|BHQ-2 羧基的信息你知道多少
    MySQL的执行计划explain
    Okhttp通用工具类
    Java对象内存布局与Synchronized锁升级
    软件测试技术之如何编写测试用例（2）
    OR青年学员访谈特辑 | 充分发挥主观能动性 自主探索 提升能力
    嵌入式编程规范及注意事项
    直播回顾 | 京东科技研发效能度量的大体系与小实践
    element ui框架（准备）
  • 原文地址：https://blog.csdn.net/qq_51222096/article/details/126558876