栈的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