人生设计师
这是系列文章，每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现，从而对常用的数据结构和
java集合有个大概的了解。当然实现没有java集合的实现那么复杂，功能也没有那么强大，但是可以通过这些简单的实现窥探到底层的一些共性原理。
一.链式栈
采用链式储存结构的栈叫做链式栈，采用单链表来实现。单链表的第一个结点为栈顶结点，设top指向栈顶结点，入栈操作是在当前栈顶结点之前插入新的结点；出栈操作是删除当前栈顶结点并返回栈顶元素值，再使top指向新的栈顶结点。链式栈的空栈(a)，入栈操作(b)和出栈操作(c)如下图示所示：
二.链式栈的实现
1. 定义链式栈
前面文章自己实现集合框架(九):栈接口介绍了栈接口的定义，链式栈类LinkedStack实现栈接口SStack，并实现栈接口中定义的方法，代码如下所示：
package org.light4j.dataStructure.linearList.stack.link;
import org.light4j.dataStructure.linearList.Node;
import org.light4j.dataStructure.linearList.stack.SStack;
/**
* 链式栈
*
* @author longjiazuo
*
* @param <E>
*/
public class LinkedStack<E> implements SStack<E> {
private Node<E> top;// 栈顶元素结点
public LinkedStack() {
this.top = null;
}
}
代码解释：
① 链式栈实现栈接口类
SStack，但不能继承前面实现的单链表类SinglyLinkedList，因为栈不支持线性表在任意位置的插入和删除操作。
2. 判断栈是否为空
/**
* 判断栈是否为空，若为空则返回true
*
* @return
*/
@Override
public boolean isEmpty() {
return this.top == null;
}
代码解释
① 链式栈是否为空栈的依据是判断栈顶结点是否为空。
3. 入栈
/**
* 元素入栈，成为新的栈顶元素，若操作成功返回true
*/
@Override
public boolean push(E element) {
if (element == null) {// 空对象不能入栈
return false;
}
this.top = new Node<E>(element, this.top);// 新的元素作为栈顶元素，原来的栈顶元素作为其后继元素
return true;
}
代码解释：
①
top指向栈顶结点，入栈操作是在当前栈顶结点之前插入新的结点。
4.出栈
/**
* 元素出栈，返回当前栈顶元素，栈顶元素改变，若栈为空则返回null
*/
@Override
public E pop() {
if (!isEmpty()) {// 判断是否为空空栈
E temp = this.top.data;// 取栈顶元素
this.top = this.top.next;// 删除原来的栈顶结点，改变栈顶元素
return temp;// 返回原来的栈顶元素值
}
return null;
}
代码解释：
① 出栈操作是删除当前栈顶结点并返回栈顶元素值，再使
top指向新的栈顶结点。
5. 取栈顶元素值
/**
* 取栈顶元素值，元素未出栈，栈顶元素未改变
*/
@Override
public E get() {
if (!isEmpty()) {// 判断是否为空栈
return this.top.data;// 返回栈顶元素值
}
return null;
}
6.重写toString()方法
/**
* 返回栈中各元素的字符串表示
*/
@Override
public String toString() {
String str = "(";
Node<E> p = this.top;// 新建一个结点指向栈顶结点top
while (p != null) {
if (p.next == null) {// 判断是否有后继结点
str += p.data;
} else {
str += p.data + ",";
}
p = p.next;
}
return str + ")";
}
三. 测试
package org.light4j.dataStructure.linearList.stack.link;
import org.light4j.dataStructure.linearList.stack.SStack;
public class Test {
public static void main(String[] args) {
SStack<String> stack = new LinkedStack<String>();
System.out.println(stack.isEmpty());//判空
stack.push("A");//入栈
stack.push("B");
stack.push("C");
System.out.println(stack.toString());
stack.pop();// 出栈
stack.push("D");
stack.get();// 取栈顶元素
System.out.println(stack.toString());
System.out.println(stack.isEmpty());//判空
}
}
运行结果如下图所示：
四.时间复杂度分析
栈的入栈，出栈操作都在栈顶进行，不需要遍历单链表，所以栈的入栈操作push()，出栈操作pop()和取栈顶元素get()的时间复杂度都是O(1)。
五.源代码示例
公众号ID：longjiazuoA
未经允许不得转载：人生设计师 » 自己实现集合框架(十一):链式栈的实现