栈：
概念：
百度百科：
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
简单来说，栈就是一种先进后出的数据结构，图示如下
栈的实现：
1.数组
package com.study.spring.transaction.stack; import lombok.Getter; import lombok.Setter; /** * @author dmz * @date Create in 23:44 2019/8/12 */ @Getter @Setter public class ArrayStack<T> { public ArrayStack(int size) { this.size = size; this.array = new Object[size]; } // 初始化的大小 private int size; private Object[] array; // 下一次要放入的元素的位置 private int currentIndex; public void push(T t) { if (currentIndex == size) { throw new RuntimeException("栈中元素已满"); } array[currentIndex++] = t; } public T pop() { if (currentIndex == 0) { throw new RuntimeException("栈中已经没有元素啦"); } Object o = array[--currentIndex]; return (T) o; } } package com.study.spring.transaction.stack; /** * @author dmz * @date Create in 23:43 2019/8/12 */ public class StackDemo { public static void main(String[] args) { ArrayStack<Integer> arrayStack = new ArrayStack<>(5); arrayStack.push(1); arrayStack.push(2); arrayStack.push(3); arrayStack.push(4); arrayStack.push(5); System.out.println(arrayStack.pop()); System.out.println(arrayStack.pop()); System.out.println(arrayStack.pop()); System.out.println(arrayStack.pop()); System.out.println(arrayStack.pop()); } }
运行结果就不贴了，大家可以自行运行测试
2.链表
package com.study.spring.transaction.stack; import lombok.Getter; import lombok.Setter; import java.util.LinkedList; /** * @author dmz * @date Create in 0:01 2019/8/13 */ @Getter @Setter public class LinkStack<T> { // 最大容量 private int size; // 存储数据的链表 private LinkedList<T> linkedList; public LinkStack(int size) { this.size = size; this.linkedList = new LinkedList<T>(); } public void push(T t) { if (linkedList.size() < size) { linkedList.add(t); } else { throw new RuntimeException("栈中元素已满"); } } public T pop() { if (linkedList.size() == 0) { throw new RuntimeException("栈中已经没有元素啦"); } return linkedList.removeLast(); } }
大家可以按照数组的方式自行测试。其实JDK中的LinkedList本身就已经实现了栈这种数据结构。大家可以直接查找LinkedList中的push以及pop方法
队列：
概念：
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
简单来说，队列就是一种先进先出的数据结构，如下图所示：
队列的实现：
1.数组
package com.study.spring.transaction.queue; import lombok.Data; /** * @author dmz * @date Create in 0:25 2019/8/13 */ @Data public class ArrayQueue<T> { private int size; private Object[] objects; // 下个加入的元素的下标 private int currentIndex; public ArrayQueue(int size) { this.size = size; currentIndex = size - 1; objects = new Object[size]; } public void offer(T t) { if (currentIndex < 0) { throw new RuntimeException("队列中元素已满"); } objects[currentIndex--] = t; } public T peek() { if (0 == size) { throw new RuntimeException("队列中已经没有元素啦"); } return (T) objects[--size]; } } /** * @author dmz * @date Create in 0:25 2019/8/13 */ public class QueueDemo { public static void main(String[] args) { ArrayQueue<Integer> arrayQueue = new ArrayQueue<>(5); arrayQueue.offer(5); arrayQueue.offer(4); arrayQueue.offer(3); arrayQueue.offer(2); arrayQueue.offer(1); System.out.println(arrayQueue.peek()); System.out.println(arrayQueue.peek()); System.out.println(arrayQueue.peek()); System.out.println(arrayQueue.peek()); System.out.println(arrayQueue.peek()); System.out.println(arrayQueue.peek()); } }
2.链表
package com.study.spring.transaction.queue; import lombok.Data; import java.util.LinkedList; /** * @author dmz * @date Create in 0:25 2019/8/13 */ @Data public class LinkQueue<T> { private int size; private LinkedList<T> linkedList; public LinkQueue(int size) { this.size = size; linkedList = new LinkedList<>(); } public void offer(T t) { if (size == linkedList.size()) { throw new RuntimeException("队列中元素已满"); } linkedList.addLast(t); } public T peek() { if (size == 0) { throw new RuntimeException("队列中已经没有元素啦"); } return linkedList.removeLast(); } }
关于链表的实现我也不验证了，大家可以参考之前的示例进行验证。
为什么需要队列跟栈这些数据结构？
通过 上面的例子已经讲解不知道大家有没有这个疑惑？既然栈跟队列可以通过数组或链表实现，它们其实就是一个受限的数组或链表。相比于数组跟链表，栈跟队列这种数据结构带来的更多不过是限制罢了，那么为什么我们还需要它们呢？事实上，从功能上来看，数组跟链表确实能完全提代这两种数据结构，但是我们要知道的是，特点的数据结构是对特定场景的抽象，而且数组跟链表暴露了过多的操作接口，虽然操作上更加灵活，但是使用时就更加不可控，更容易出错。
