链栈,顾名思义,就是以链表的形式实现的栈的相关操作,其实是功能弱化了的链表,如果已经阅读过链表的实现代码,那么链栈的实现显得更为容易。
?
?
class="java" name="code">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()); } }
?
?
对于Java集合而言,并没有提供一个Stack接口,再为该接口提供顺序栈、链栈两种实现。
?
实际上提供了一下两种实现方式:
?
?
代码获取地址:https://github.com/liuhao123/JavaMore.git
?