`

java 实现数据结构之栈

阅读更多
   在学数据结构课程时,对栈的最大特点是是后进先出(First In Last Out),对栈的操作主要是入栈和出栈,判断栈是否为空,计算栈的大小。
   栈是一种数据结构,它代表只能在某一端进行插入、删除操作的特殊线性表。对栈而言,允许插入删除的一端是栈顶,另一端则称为栈底。
1.栈的顺序存储实现:
public class Stack 
{
	//存放栈内元素的数组
	private Object[] elementData; 
	//记录栈内元素的个数
	private int size = 0;
	//以指定初始化容量创建一个Stack
	private int capacityIncrement;
	//以指定初始化容量创建一个Stack
	public Stack(int initialCapacity) 
	{
		elementData = new Object[initialCapacity];
	}
	public Stack(int initialCapacity , int capacityIncrement)
	{
		this(initialCapacity);
		this.capacityIncrement = capacityIncrement;
	}
	//向“栈”顶压入一个元素
	public void push(Object object)
	{
		ensureCapacity();
		elementData[size++] = object;
	}
	public Object pop()
	{
		if(size == 0)
		{
			throw new RuntimeException("空栈异常");
		}
		return elementData[--size];
	}
	public int size()
	{
		return size;
	}
	//保证底层数组能容纳栈内所有元素
	private void ensureCapacity()
	{ //增加堆栈的容量
		if(elementData.length==size)
		{
			Object[] oldElements = elementData;
			int newLength = 0;
			//已经设置capacityIncrement
			if (capacityIncrement > 0)
			{
				newLength = elementData.length + capacityIncrement;
			}
			else
			{
				//将长度扩充到原来的1.5倍
				newLength = (int)(elementData.length * 1.5);
			}
			elementData = new Object[newLength];
			//将原数组的元素复制到新数组中
			System.arraycopy(oldElements , 0 , elementData , 0 , size);
		}
	}
	public static void main(String[] args)
	{
		Stack stack = new Stack(10);
		//向栈顶压入10个元素
		for (int i = 0 ; i < 10 ; i++)
		{
			stack.push("元素" + i);
			System.out.println("元素" + i+"入栈");
		}
		//依次弹出10个元素
		for (int i = 0 ; i < 10 ; i++)
		{
			System.out.println(stack.pop()+"出栈");
		}
	}
}

运行结果:
元素0入栈
元素1入栈
元素2入栈
元素3入栈
元素4入栈
元素5入栈
元素6入栈
元素7入栈
元素8入栈
元素9入栈
元素9出栈
元素8出栈
元素7出栈
元素6出栈
元素5出栈
元素4出栈
元素3出栈
元素2出栈
元素1出栈
元素0出栈


2.栈的链式存储实现:
public class LinkStack<T>
{
	//定义一个内部类Node,Node实例代表链栈的节点。
	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;
	//创建空链栈
	public LinkStack()
	{
		//空链栈,top的值为null
		top = null;
	}
	//以指定数据元素来创建链栈,该链栈只有一个元素
	public LinkStack(T element)
	{
		top = new Node(element , null);
		size++;
	}
	//返回链栈的长度	
	public int length()
	{
		return size;
	}
	//进栈
	public void push(T element)
	{
		//让top指向新创建的元素,新元素的next引用指向原来的栈顶元素
		top = new Node(element , top);
		size++;
	}
	//出栈
    public T pop()
	{
		Node oldTop = top;
		//让top引用指向原栈顶元素的下一个元素
		top = top.next;
		//释放原栈顶元素的next引用
		oldTop.next = null;
		size--;
		return oldTop.data;
	}
	//访问栈顶元素,但不删除栈顶元素
	public T peek()
	{
		return top.data;
	}
	//判断链栈是否为空栈
	public boolean empty()
	{
		return size == 0;
	}
	//清空链栈
	public void clear()
	{
		//将底层数组所有元素赋为null
		top = null;
		size = 0;
	}
	public String toString()
	{
		//链栈为空链栈时
		if (empty())
		{
			return "[]";
		}
		else
		{
			StringBuilder sb = new StringBuilder("[");
			for (Node current = top ; current != null
				; current = current.next )
			{
				sb.append(current.data.toString() + ", ");
			}
			int len = sb.length();
			return sb.delete(len - 2 , len).append("]").toString();
		}
	}
}



java集合提供了两种栈供开发者使用:
java.util.Stack:一个普通的顺序栈,底层基于数组实现。这个Stack类是线程安全的。
java.util.LinkedList:是一个双向链表。线程不安全,可以当做栈来使用,提供了push(),pop(),peek()等方法。在多线程环境下使用,可以使用Collections类的工具方法将其改造成线程安全类。
1
2
分享到:
评论

相关推荐

    java实现数据结构

    下面将详细介绍Java中实现链表、栈、队列、优先级队列以及哈希表这些基本数据结构的方法。 首先,我们来看链表。链表是一种线性数据结构,其中的元素不连续存储,而是通过指针连接。Java中的`LinkedList`类实现了`...

    Java语言编写的数据结构-栈实现

    在这个主题中,我们将深入探讨如何在Java中实现栈这一基本数据结构,具体包括顺序栈(stack_SqStack)和链栈(stack_SLinkList)。 栈是一种后进先出(Last In First Out, LIFO)的数据结构,常用于临时存储和快速...

    java基础数据结构-栈

    本文通过对《Java基础复习笔记05数据结构-栈》的解析,详细介绍了栈的基本概念、操作方法以及应用场景,并提供了栈的两种实现方式——顺序实现与链表实现的详细说明。理解这些知识点对于深入学习数据结构与算法至关...

    Java常见数据结构面试题(带答案)

    "Java常见数据结构面试题(带答案)" 以下是对Java常见数据结构面试题的...本篇文章主要介绍了Java常见数据结构面试题,涵盖了栈、队列、链表、线性表、树、算法、数据结构等知识点,希望对广大的程序爱好者有所帮助。

    java-数据结构代码实现

    本资料包“java-数据结构代码实现”提供了使用Java语言实现数据结构的实例,旨在帮助开发者加深对数据结构的理解并提升编程技能。 1. **链表**:链表是一种动态数据结构,其元素在内存中不是顺序排列的。Java中的...

    数据结构之栈的定义及实现

    在这个主题中,“数据结构之栈的定义及实现”将深入探讨栈的基本概念、操作以及在编程中的具体实现。 栈的定义: 栈是一种线性数据结构,它的特点是元素只能在栈的一端进行插入和删除操作,这一端被称为栈顶。新...

    java 栈的实现和应用

    Java栈是一种基于后进先出(LIFO)原则的数据结构,它在计算机科学和编程中具有广泛的应用。本文将深入探讨Java中栈的实现以及其在实际应用中的使用。 首先,我们来理解栈的基本概念。栈是一种特殊类型的线性数据...

    Java数据结构之栈的基本定义与实现方法示例

    Java数据结构之栈的基本定义与实现方法示例 Java数据结构之栈是一种特殊的线性表,它只能在某一端插入和删除元素,按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶...

    数据结构(Java)迷宫实现

    总之,利用Java和栈数据结构解决迷宫问题是一个很好的实践项目,它能够帮助我们深入理解数据结构与算法在实际问题中的应用。在进行这样的实践作业时,不仅要关注代码的实现,还要注重代码的可读性和优化,这对提升...

    数据结构中栈和队的源代码

    栈和队列是两种最基本且重要的数据结构,广泛应用于各种算法和系统设计中。 首先,栈(Stack)是一种后进先出(LIFO, Last In First Out)的数据结构。它的工作原理类似于日常生活中使用的堆叠物品,最后放入的物品...

    JAVA基本5种数据结构的实现。

    本主题将深入探讨Java中的五种基础数据结构:链表、队列、栈、双端队列(deque)以及堆。我们将通过分析给定的源代码文件来理解这些数据结构的实现。 首先,链表是一种线性数据结构,它不连续存储数据,而是通过...

    Java数据结构-栈

    总之,Java中的栈数据结构提供了一种高效的方法来处理需要后进先出逻辑的问题,它在编程中扮演着至关重要的角色,尤其是在处理需要临时存储和按顺序处理数据的任务时。了解和熟练掌握栈的操作和实现对于提升编程技能...

    JAVA版数据结构.pdf

    文中提到了数据结构(Data Structures)和Java语言的结合,这表明文档可能涉及数据结构在Java中的实现方式,包括基本的结构如数组、链表、栈、队列、树和图等,以及它们的特性、操作方法和应用场景。 2. Java中的...

    Java版数据结构代码,栈,动态数组,队列,链表,二叉树

    本资源提供了Java实现的数据结构代码,包括栈、动态数组、队列、链表和二叉树,这些都是计算机科学中最基础且重要的数据结构。 1. **栈(Stack)**:栈是一种“后进先出”(LIFO)的数据结构,常用于表达式求值、...

    数据结构中栈和队列思想的停车场管理系统

    基于c语言数据结构中栈和队列思想的简单停车场管理系统,以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车...

    数据结构与算法代码详解JAVA版

    本资源"数据结构与算法代码详解JAVA版"聚焦于使用Java语言来理解和实现这些核心概念。 首先,数据结构是组织和存储数据的方式,它为高效地执行各种操作提供了便利。常见的数据结构包括数组、链表、栈、队列、树(如...

    Java数据结构课件

    栈是一种后进先出(LIFO)的数据结构,Java中的`java.util.Stack`类可以用来实现栈。栈常用于表达式求值、深度优先搜索等场景。队列是一种先进先出(FIFO)的数据结构,`java.util.Queue`接口及其实现类如`...

    java数据结构实例

    在这个压缩包文件中,我们可以预期找到一些用Java实现的数据结构的源代码。 数据结构是计算机存储、组织数据的方式,它决定了数据的逻辑结构、存储结构以及数据的操作。在Java中,常见的数据结构包括数组、链表、栈...

    java实现的数据结构与算法

    《Java实现的数据结构与算法》是一本全面介绍数据结构和算法实现的书籍,以Java语言为载体,涵盖了面向对象程序设计的基本概念和特性,并深入探讨了数据结构与算法的方方面面,包括各种数据结构的基本概念、算法的...

Global site tag (gtag.js) - Google Analytics