一、前言
之前我们已经学习了链表的所有操作及其时间复杂度分析,我们可以了解到对于链表头的相关操作基本都是O(1)的,例如链表头增加、删除元素,查询元素等等。那我们其实有一个数据结构其实可以完美利用到这些操作的特点,都是在某一段进行操作,那就是栈。本章我们通过链表去实现栈。并且比较用数组实现和用链表实现他们之间的差异。
二、用链表实现栈
2.1、代码实现
那么通过链表实现栈就很简单了,我们知道入栈和出栈都是从链表的同一端进行操作,那么我们只需调用链表的addFirst/removeFirst的方法即可,查找同理。
首先我们将链表栈命名为LinkedListStack,并且实现我们Stack的抽象类,然后设置一个内部属性为我们之前实现的链表,通过该链表完成实现需要重写的方法即可,代码如下:
public class LinkedListStack<T> implements Stack<T> {
private LinkedList<T> linkedList;
public LinkedListStack() {
this.linkedList = new LinkedList<>();
}
@Override
public int getSize() {
return linkedList.getSize();
}
@Override
public boolean isEmpty() {
return linkedList.isEmpty();
}
@Override
public void push(T t) {
linkedList.addFirst(t);
}
@Override
public T pop() {
return linkedList.removeFirst();
}
@Override
public T peek() {
return linkedList.getFirst();
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("Stack: top ");
stringBuilder.append(linkedList);
return stringBuilder.toString();
}
}
测试一下:
public static void main(String[] args) {
LinkedListStack<Integer> 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(Stack<Integer> 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) {
ArrayStack<Integer> integerArrayStack = new ArrayStack<>();
LinkedListStack<Integer> 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次,这个时候两者的时间差距就比较大了:
文章来源:https://www.toymoban.com/news/detail-727453.html
所以仍然取决于你测试使用的操作系统,配置,jvm版本等等。但是其实我想强调的是,对于数组栈和链表栈来说,他们的各项操作的时间复杂度其实是一致的。他们之间没有复杂度之间的巨大差异。不像数组队列和循环队列,一个6s,一个0.01s,这之间的差距是非常大的。文章来源地址https://www.toymoban.com/news/detail-727453.html
到了这里,关于数据结构与算法(七)--使用链表实现栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!