链表应用--基于链表实现栈
在上几小节中我们实现了基本的链表结构，并在上一节的底部给出了有关链表的源码，此处在贴一次吧，猛戳
在开始栈的实现之前，我们再来看看关于链表的只在头部进行的增加、删除、查找操作，时间复杂度均为O(1)，基于链表的这几个优势，我们在此基础上实现栈。
前言，在写本小节之前，我们已经实现了一个基于静态数组的栈，转到查看。此处我们实现基于链表的栈。
1.链表类拷贝到Stack 包下：
在实现基于静态数组的栈的时候，我们已经新建了一个package，此时我们将已经实现的链表类拷贝到该package下，目录结构为：
2.实现栈
新建一个LinkedListStack类，实现Stack接口，相关代码如下：
Stack接口:
package Stack;
public interface Stack<E> {
//栈中元素个数
int getSize();
//栈中元素个数是否为空
boolean isEmpty();
//进栈
void push(E e);
//出栈
E pop();
//查看栈顶元素
E peek();
}个LinkedListStack类:
package Stack;
public class LinkedListStack<E> implements Stack<E> {
private LinkedList<E> list;
public LinkedListStack() {
list = new LinkedList<E>();
}
//栈中元素个数
@Override
public int getSize() {
return list.getSize();
}
//栈中是否为空
@Override
public boolean isEmpty() {
return list.isEmpty();
}
//在栈中添加元素
@Override
public void push(E e) {
list.addFirst(e);
}
//从栈中删除第一个元素
@Override
public E pop() {
return list.removeFirst();
}
//查看栈中第一个元素
@Override
public E peek() {
return list.getFirst();
}
//主要是便于输出给对象信息
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack: top ");
res.append(list);
return res.toString();
}
}3.添加测试代码
为了测试的简单，我们在已经实现了Stack接口的LinkedListStack类中建立以main()方法，main中代码如下：
//测试
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<Integer>();
for (int i = 0; i < 5; i++) {
stack.push(i);
System.out.println(stack);
}
System.out.println("出栈一个元素：");
stack.pop();
System.out.println(stack);
}结果为：
到此我们实现了底层是链表的栈。
关于本小节，若您觉得还行、还过得去，记得给个推荐哦~，谢谢！！
本节源码 https://github.com/FelixBin/dataStructure/blob/master/src/Stack/LinkedListStack.java
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-04-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读