栈的Java实现--链栈
链栈，顾名思义，就是以链表的形式实现的栈的相关操作，其实是功能弱化了的链表，如果已经阅读过链表的实现代码，那么链栈的实现显得更为容易。
链栈的基本结构：
链栈的入栈操作：
- 让top引用指向新的节点，新节点的next指向原来的top
- 记录栈内元素个数的size+1
链栈的出栈操作：
- top引用指向原栈顶元素的下一个元素（top.next），并释放原栈顶元素的引用
- 记录栈内元素个数的size-1
链栈的Java实现代码：
package com.liuhao.DataStructures;
public class LinkStack<T> {
private class Node {
private T data;// 保存节点的数据元素
private Node next;// 保存下一个节点的引用
public Node() {
}
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
private Node top;// 存放栈顶节点
private int size = 0;// 存放栈中已有的元素个数
// 创建空链栈
public LinkStack() {
top = null;
}
// 已指定数据元素创建链栈，只有一个元素
public LinkStack(T element) {
top = new Node(element, null);
size++;
}
// 返回链栈的长度
public int length() {
return size;
}
// 进栈
public void push(T elemnt) {
// 让top指向新节点，新节点的next指向原来的top
top = new Node(elemnt, top);
size++;
}
// 出栈
public T pop() {
// 若当前为空栈，则返回null
if (size == 0) {
return null;
}
Node oldTop = top;
// 让top指向原栈顶的下一个节点
top = top.next;
// 释放原栈顶元素的引用
oldTop.next = null;
size--;
return oldTop.data;
}
// 获取栈顶元素
public T getTop() {
// 若当前为空栈，则返回null
if (size == 0) {
return null;
}
return top.data;
}
// 判断是否为空
public boolean isEmpty() {
return size == 0;
}
// 清空栈
public void clear() {
top = null;
size = 0;
}
public String toString() {
if (size == 0) {
return "[]";
}
else {
StringBuilder sb = new StringBuilder("[");
for (Node current = top; current != null; current = current.next) {
sb.append(current.data.toString() + ", ");
}
sb.append("]");
int length = sb.length();
return sb.delete(length - 3, length - 1).toString();
}
}
}
测试代码：
package com.liuhao.test;
import org.junit.Test;
import com.liuhao.DataStructures.LinkStack;
public class LinkStackTest {
@Test
public void test() {
// 以指定第一个元素和底层数组长度的方式构建顺序栈
LinkStack<String> linkStack = new LinkStack<String>("我");
System.out.println("当前所含内容" + linkStack);
// 压入数据元素,元素格式大于了定义栈时底层数组的长度
linkStack.push("是");
linkStack.push("liuhao");
linkStack.push("程序员");
// 发现是先入后出的方式打印的
System.out.println("当前所含内容" + linkStack);
// 获取栈中元素个数
System.out.println("当前栈中元素个数是：" + linkStack.length());
// 获取栈顶元素
System.out.println("当前栈顶元素是：" + linkStack.getTop());
// 弹出元素
System.out.println("弹出元素：" + linkStack.pop());
// 发现是先入后出的方式打印的
System.out.println("当前所含内容" + linkStack);
// 获取栈顶元素
System.out.println("当前栈顶元素是：" + linkStack.getTop());
// 获取栈中元素个数
System.out.println("当前栈中元素个数是：" + linkStack.length());
// 判断是否为空栈
System.out.println("当前栈是否为空：" + linkStack.isEmpty());
// 清空栈
linkStack.clear();
// 判断是否为空栈
System.out.println("当前栈是否为空：" + linkStack.isEmpty());
// 获取栈顶元素,空栈时返回null
System.out.println("当前栈顶元素是：" + linkStack.getTop());
// 获取栈中元素个数
System.out.println("当前栈中元素个数是：" + linkStack.length());
// 空栈时进行弹出元素
System.out.println("弹出元素：" + linkStack.pop());
}
}
测试结果：
JDK提供的栈：
对于Java集合而言，并没有提供一个Stack接口，再为该接口提供顺序栈、链栈两种实现。
实际上提供了一下两种实现方式：
- java.util.Stack：一个普通的顺序栈，底层基于数组实现，同时是线程安全的，可以在多线程环境下放心使用。
- java.util.LinkedList：之前介绍过，LinkedList是一个双向链表，但是查看该类的API可以发现，它同时也提供了push()、pop()、peek()等方法，这表明LinkedList完全可以当成栈来使用。但是要注意LinkedList不是线程安全的。
代码获取地址：https://github.com/liuhao123/JavaMore.git
