java数据结构之java实现栈

代码如下:

import java.util.Arrays;

/**
 * 栈的实现<br>
 * @author Skip
 * @version 1.0
 */
public class Stack<T> {
 private int size;    //栈中元素的个数
 private Object[] arr;  //底层数组
 private final int defaultLength = 200; //默认长度

/**
  * 无参构造,使用默认长度初始化数组
  */
 public Stack(){
  arr = new Object[defaultLength];
  size = 0;
 }

/**
  * 使用长度参数初始化数组
  * @param length 长度
  */
 public Stack(int length){
  arr = new Object[length];
  size = 0;
 }

/**
  * 入栈
  * @param element 数据
  */
 public void push(T element){
  //是否需要扩容
  if(size >= arr.length){
   //数组扩容
   extendCapacity(size+1);
  }
  arr[size++] = element;
 }

/**
  * 出栈
  * @return 数据
  */
 @SuppressWarnings("unchecked")
 public T pop(){
  //元素个数为0,无法执行出栈操作
  if(size==0){
   return null;
  }
  T t = (T)arr[size-1];
  arr[--size] = null;  //数据已出栈,还原为null
  return t;
 }

/**
  * 清空栈
  */
 public void clear(){
  for(int i=0;i<size;i++){
   arr[i]=null;
  }
  size = 0;
 }

/**
  * 获得当前栈中元素的个数
  * @return 元素的个数
  */
 public int getSize(){
  return size;
 }

/**
  * 判断是否为空栈
  * @return 空为true,非空为false
  */
 public boolean isEmpty(){
  return size == 0;
 }

/**
  * 打印栈中所有的元素
  */
 @SuppressWarnings("unchecked")
 public void printStack(){
  for(int i=0;i<size;i++){
   System.out.print(((T)arr[i]).toString());
  }
  System.out.println();
 }

/**
  * 扩容
  * @param length 需要的长度
  */
 private void extendCapacity(int length){
  //当前数组长度和需要的长度取最大
  int minCapacity = Math.max(arr.length, length);
  //判断是否需要扩容
  if(minCapacity - arr.length>0){
   //数组长度增加一半
   int newLength = arr.length + arr.length/2;
   //如果新的长度还比需求要小,将需求的长度作为数组长度
   if(newLength < minCapacity){
    newLength=minCapacity;
   }
   //数组长度不能超过Integer.Max_Value
   if(newLength > Integer.MAX_VALUE - 8){
    newLength = Integer.MAX_VALUE;
   }
   //数组扩容
   arr = Arrays.copyOf(arr, newLength);
  }
 }
}

赞 (0)

相关推荐

  • Java数据结构之队列的简单定义与使用方法

    Java数据结构之队列的简单定义与使用方法

    本文实例讲述了Java数据结构之队列的简单定义与使用方法.分享给大家供大家参考,具体如下: 一.概述: 1.说明: 队列的原则时先进先出,就像生活中排队取票一样,谁排在前面谁先得到 2.有五个属性: 1)数组元素 2)最大空间 3)长度 4)队头 5)队尾 3.示例图: 二.代码实现 /** * @描述 对列 * @项目名称 Java_DataStruct * @包名 com.java.stack * @类名 Queue * @author chenlin * @version 1.0 * @S

  • Java数据结构与算法之栈(Stack)实现详解

    Java数据结构与算法之栈(Stack)实现详解

    本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点: 栈的抽象数据类型顺序栈的设计与实现链式栈的设计与实现栈的应用 栈的抽象数据类型   栈是一种用于存储数据的简单数据结构,有点类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作

  • java 数据结构中栈和队列的实例详解

    java 数据结构中栈和队列的实例详解 栈和队列是两种重要的线性数据结构,都是在一个特定的范围的存储单元中的存储数据.与线性表相比,它们的插入和删除操作收到更多的约束和限定,又被称为限定性的线性表结构.栈是先进后出FILO,队列是先进先出FIFO,但是有的数据结构按照一定的条件排队数据的队列,这时候的队列属于特殊队列,不一定按照上面的原则. 实现栈:采用数组和链表两种方法来实现栈 链表方法: package com.cl.content01; /* * 使用链表来实现栈 */ public cl

  • Java数据结构与算法之栈(动力节点Java学院整理)

    stack,中文翻译为堆栈,其实指的是栈,heap,堆.这里讲的是数据结构的栈,不是内存分配里面的堆和栈. 栈是先进后出的数据的结构,好比你碟子一个一个堆起来,最后放的那个是堆在最上面的. 队列就是排队买苹果,先去的那个可以先买. 栈 public class Stack { private int array[]; private int max; private int top; public Stack(int max){ this.max = max; array = new int[m

  • Java模拟栈和队列数据结构的基本示例讲解

    栈和队列: 一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建: 访问受限,在特定时刻,只有一个数据可被读取或删除: 是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组.链表来实现栈. 模拟栈结构 同时,只允许一个数据被访问,后进先出 对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数,操作比较快 例,使用数组作为栈的存储结构 public class StackS<T> { private int max; private T[] ary; priv

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

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

    本文实例讲述了Java数据结构之栈的基本定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.基本概念: 栈是一种数据结构,是只能在某一端插入和删除的特殊线性表.它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来). 栈是允许在同一端进行插入和删除操作的特殊线性表.允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom):栈底固定,而栈顶 浮动:栈中元素个数为零时称为空栈.插入一般

  • 用Java代码实现栈数据结构的基本方法归纳

    链式实现: 在栈的一段添加和删除元素,在栈中维护一个指向栈顶的结点和一个count变量指示栈的大小: private LinearNode top; //指向栈顶 private int count;//标记栈的大小 每次出栈和压栈在链表的表头:(也可以再表尾,实现方式不一样而已) top--->元素1--->元素2--->元素3......... 实现(附带测试main): LinkedStack package Stack; import Bag.LinearNode; //为了重点

  • java 数据结构中栈结构应用的两个实例

    java 数据结构中栈结构应用的两个实例 1.单词逆序. 要求从控制台读入一串字符,按回车结束输入,同时显示其逆序字符串. 对于颠倒顺序的操作,用栈来解决是很方便的.具体思想是把字符串中的每一个字符按顺序存入栈中,然后再一个一个的从栈中取出.这时就是按照逆序取出的字符串. // reverse.java // stack used to reverse a string // to run this program: C>java ReverseApp import java.io.*; //

  • java 数据结构之栈与队列

    java 数据结构之栈与队列 一:对列 队列是一种先进先出的数据结构 实现代码: package Queue; /* * 使用java构建队列,并模拟实现队列的入队和出对方法 */ public class Queue { //队列类 private int maxSize; //定义队列的长度 private int[] arrQueue; //队列 private int rear; //定义队列的尾指针 private int front; //定义队列的头指针 private int e

  • Java中使用数组实现栈数据结构实例

    栈是Java语言中最重要的数据结构之一,它的实现,至少应该包括以下几个方法: 1.pop() 出栈操作,弹出栈顶元素. 2.push(E e) 入栈操作 3.peek() 查看栈顶元素 4.isEmpty() 栈是否为空 另外,实现一个栈,还应该考虑到几个问题: 1.栈的初始大小以及栈满以后如何新增栈空间 2.对栈进行更新时需要进行同步 简单示例,使用数组实现栈,代码如下: 复制代码 代码如下: public class Stack<E> { // Java 不支持泛型数组,如需使用,请使用J

随机推荐