鞍山做网站企业,品牌推广广告,什么网站可以做注册任务,阿里网站seo一、前言
之前我们已经学习了链表的所有操作及其时间复杂度分析#xff0c;我们可以了解到对于链表头的相关操作基本都是O(1)的#xff0c;例如链表头增加、删除元素#xff0c;查询元素等等。那我们其实有一个数据结构其实可以完美利用到这些操作的特点#xff0c;都是在…一、前言
之前我们已经学习了链表的所有操作及其时间复杂度分析我们可以了解到对于链表头的相关操作基本都是O(1)的例如链表头增加、删除元素查询元素等等。那我们其实有一个数据结构其实可以完美利用到这些操作的特点都是在某一段进行操作那就是栈。本章我们通过链表去实现栈。并且比较用数组实现和用链表实现他们之间的差异。
二、用链表实现栈
2.1、代码实现
那么通过链表实现栈就很简单了我们知道入栈和出栈都是从链表的同一端进行操作那么我们只需调用链表的addFirst/removeFirst的方法即可查找同理。 首先我们将链表栈命名为LinkedListStack,并且实现我们Stack的抽象类然后设置一个内部属性为我们之前实现的链表通过该链表完成实现需要重写的方法即可代码如下
public class LinkedListStackT implements StackT {private LinkedListT linkedList;public LinkedListStack() {this.linkedList new LinkedList();}Overridepublic int getSize() {return linkedList.getSize();}Overridepublic boolean isEmpty() {return linkedList.isEmpty();}Overridepublic void push(T t) {linkedList.addFirst(t);}Overridepublic T pop() {return linkedList.removeFirst();}Overridepublic T peek() {return linkedList.getFirst();}Overridepublic String toString() {StringBuilder stringBuilder new StringBuilder();stringBuilder.append(Stack: top );stringBuilder.append(linkedList);return stringBuilder.toString();}
}
测试一下
public static void main(String[] args) {LinkedListStackInteger integerArrayStack new LinkedListStack();for (int i 0; i 5; i) {integerArrayStack.push(i);System.out.println(integerArrayStack);}integerArrayStack.pop();System.out.println(integerArrayStack);}结果没有问题通过链表实现栈就这样简单的实现了。
2.2、和数组栈比较性能
这个代码和之前数组队列和循环队列效率的对比很接近
public class TestStackCompare {private static double testQueue(StackInteger s, int opCount){long startTime System.currentTimeMillis();Random random new Random();for (int i 0; i opCount; i) {s.push(random.nextInt(Integer.MAX_VALUE));}for (int i 0; i opCount; i) {s.pop();}long endTime System.currentTimeMillis();return (endTime - startTime)/1000.0;}public static void main(String[] args) {ArrayStackInteger integerArrayStack new ArrayStack();LinkedListStackInteger integerLinkedListStack new LinkedListStack();System.out.println(arrayStack,time:testQueue(integerArrayStack,1000000)s);System.out.println(linkedListStack,time:testQueue(integerLinkedListStack,1000000)s);}
}那么我们运行下发现两者效率近乎一致 当然也有可能得到的结果是有差距的对于arrayStack来说时不时就需要扩容这个对于某些操作系统来说比较耗费时间而对于linkedListStack来说它每次new Node就需要不断的开辟空间这个操作又对于某些操作系统来说更耗费时间而且这两者的差距会随着操作次数的增多不断拉大因为扩容并不是每次扩容而new Node确实是需要每次都new一个例如我将操作次数放大为10000000次这个时候两者的时间差距就比较大了
所以仍然取决于你测试使用的操作系统配置jvm版本等等。但是其实我想强调的是对于数组栈和链表栈来说他们的各项操作的时间复杂度其实是一致的。他们之间没有复杂度之间的巨大差异。不像数组队列和循环队列一个6s,一个0.01s,这之间的差距是非常大的。
