这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和
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

未经允许不得转载:人生设计师 » 自己实现集合框架(十一):链式栈的实现