Stack是一种数据结构，主要功能包括存放数据、取数据、删除栈中的元素等，下面分别用数组和链表结构实现Stack
1、Stack接口
public interface MyStack<E> {/*** 向栈顶插入元素* @param e*/void push(E e);/*** 获取栈顶元素* @return 栈顶元素*/E peek();/*** 获取栈顶元素并从栈中删除该元素* @return 栈顶元素*/E pop();/*** 判断栈是否为空* @return true--栈为空；false--栈不为空；*/boolean isEmpty();/*** 返回栈中元素个数* @return 栈中元素个数*/int size();}
2、数组实现栈——ArrayStack
public class ArrayStack<E> implements MyStack<E> {private static final Logger LOGGER = LoggerFactory.getLogger(ArrayStack.class);private static final int DEFAULT_CAPACITY = 10;private E[] data;private int size;public ArrayStack() {this(DEFAULT_CAPACITY);}public ArrayStack(int iniCapacity) {data = (E[]) new Object[iniCapacity];}@Overridepublic void push(E e) {if (data.length == size) {resize(data.length * 2);}data[size++] = e;}@Overridepublic E peek() {return isEmpty() ? null : data[size - 1];}@Overridepublic E pop() {if (isEmpty()) {return null;}E e = data[--size];data[size] = null;if (size == data.length / 4) {resize(data.length / 2);}return e;}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic int size() {return size;}/*** 栈容量大小调整* 在元素入栈或出站时，可能会被调用* @param targetCapacity 新的栈容量*/private void resize(int targetCapacity) {LOGGER.info("resize# targetCapacity = {}", targetCapacity);E[] oldData = data;data = (E[]) new Object[targetCapacity];for (int i = 0; i < size; i++) {data[i] = oldData[i];}}@Overridepublic String toString() {return "ArrayStack{" +"data=" + Arrays.toString(data) +'}';}
}
2、链表实现——LinkedStack
public class LinkedStack<E> implements MyStack<E> {private static final Logger LOGGER = LoggerFactory.getLogger(LinkedStack.class);private int size;private Node head;class Node {E e;Node next;public Node(E e, Node next) {this.e = e;this.next = next;}}@Overridepublic void push(E e) {Node node = new Node(e, null);size++;if (head == null) {head = node;return ;}Node oldHead = head;head = node;head.next = oldHead;}@Overridepublic E peek() {return head == null ? null : head.e;}@Overridepublic E pop() {if (head == null) {return null;}E e = head.e;head = head.next;size--;return e;}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic int size() {return size;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder("LinkedStack{");if (head == null) {sb.append("null");} else {for (Node first = head; first != null; first = first.next) {sb.append(first.e + "->");}sb = new StringBuilder(sb.substring(0, sb.length() - 2));}sb.append("}");return sb.toString();}
}
4、测试用例
public class CollectionTest {@Testpublic void arrayStackTest01() {MyStack<String> stack = new ArrayStack<>();stack.push("111");System.out.println("step1----stack = " + stack);stack.push("222");stack.push("222");stack.push("222");stack.push("222");stack.push("222");stack.push("222");stack.push("222");stack.push("222");stack.push("222");stack.push("222");stack.push("222");stack.push("222");stack.push("222");System.out.println("step2----stack = " + stack);System.out.println("pop1----" + stack.pop());System.out.println("pop2----" + stack.pop());System.out.println("pop3----" + stack.pop());System.out.println("pop4----" + stack.pop());System.out.println("pop5----" + stack.pop());System.out.println("pop6----" + stack.pop());System.out.println("peek1----" + stack.peek());System.out.println("pop7----" + stack.pop());System.out.println("pop8----" + stack.pop());System.out.println("pop9----" + stack.pop());System.out.println("pop10----" + stack.pop());System.out.println("step3----stack = " + stack);}@Testpublic void linkedStackTest() {LinkedStack<String> stack = new LinkedStack<>();System.out.println(stack);stack.push("111");stack.push("222");stack.push("333");stack.push("444");stack.push("222");System.out.println(stack);System.out.println(stack.peek());System.out.println(stack);System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack);}}
5、分析
1）数组实现的数据结构
优点：数据查找较快（按索引就行）；
缺点：用数组实现的数据结构，会存在扩容和缩容的问题，这也存在着性能消耗问题（创建过大的数组则会消耗过大的内存）；插入或删除数据稍慢些；
2）链表实现的数据结构：
优点：插入或删除数据稍较快；没有扩容的性能消耗；
缺点：数据查找较慢（可能会遍历整个链表才能找到）。