栈的Java实现--链栈_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 栈的Java实现--链栈

栈的Java实现--链栈

 2014/4/14 18:45:57  NO.6  程序员俱乐部  我要评论(0)
  • 摘要:栈的Java实现--链栈链栈,顾名思义,就是以链表的形式实现的栈的相关操作,其实是功能弱化了的链表,如果已经阅读过链表的实现代码,那么链栈的实现显得更为容易。链栈的基本结构:链栈的入栈操作:让top引用指向新的节点,新节点的next指向原来的top记录栈内元素个数的size+1链栈的出栈操作:top引用指向原栈顶元素的下一个元素(top.next),并释放原栈顶元素的引用记录栈内元素个数的size-1链栈的Java实现代码:packagecom.liuhao.DataStructures
  • 标签:实现 Java

栈的Java实现--链栈

链栈,顾名思义,就是以链表的形式实现的栈的相关操作,其实是功能弱化了的链表,如果已经阅读过链表的实现代码,那么链栈的实现显得更为容易。

?

链栈的基本结构:


链栈的入栈操作:

  • ?让top引用指向新的节点,新节点的next指向原来的top
  • 记录栈内元素个数的size+1


链栈的出栈操作:

  • ?top引用指向原栈顶元素的下一个元素(top.next),并释放原栈顶元素的引用
  • 记录栈内元素个数的size-1

?链栈的Java实现代码:

?

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());
	}

}

?

测试结果:



?

JDK提供的栈:

对于Java集合而言,并没有提供一个Stack接口,再为该接口提供顺序栈、链栈两种实现。

?

实际上提供了一下两种实现方式:

?

  • java.util.Stack:一个普通的顺序栈,底层基于数组实现,同时是线程安全的,可以在多线程环境下放心使用。
  • java.util.LinkedList:之前介绍过,LinkedList是一个双向链表,但是查看该类的API可以发现,它同时也提供了push()、pop()、peek()等方法,这表明LinkedList完全可以当成栈来使用。但是要注意LinkedList不是线程安全的。

?

代码获取地址:https://github.com/liuhao123/JavaMore.git

?

  • 大小: 5.7 KB
  • 大小: 14.6 KB
  • 大小: 13.7 KB
  • 大小: 6.5 KB
  • 查看图片附件
发表评论
用户名: 匿名