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

本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点:

栈的抽象数据类型顺序栈的设计与实现链式栈的设计与实现栈的应用

栈的抽象数据类型

  栈是一种用于存储数据的简单数据结构,有点类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素,则称为空栈,栈的结构如下图:

由图我们可看成栈只能从栈顶存取元素,同时先进入的元素反而是后出,而栈顶永远指向栈内最顶部的元素。到此可以给出栈的正式定义:栈(Stack)是一种有序特殊的线性表,只能在表的一端(称为栈顶,top,总是指向栈顶元素)执行插入和删除操作,最后插入的元素将第一个被删除,因此栈也称为后进先出(Last In First Out,LIFO)或先进后出(First In Last Out FILO)的线性表。栈的基本操作创建栈,判空,入栈,出栈,获取栈顶元素等,注意栈不支持对指定位置进行删除,插入,其接口Stack声明如下:

/*
* 栈接口抽象数据类型
*/
public interface Stack<T> {

 /**
 * 栈是否为空
 * @return
 */
 boolean isEmpty();

 /**
 * data元素入栈
 * @param data
 */
 void push(T data);

 /**
 * 返回栈顶元素,未出栈
 * @return
 */
 T peek();

 /**
 * 出栈,返回栈顶元素,同时从栈中移除该元素
 * @return
 */
 T pop();
}

顺序栈的设计与实现

  顺序栈,顾名思义就是采用顺序表实现的的栈,顺序栈的内部以顺序表为基础,实现对元素的存取操作,当然我们还可以采用内部数组实现顺序栈,在这里我们使用内部数据组来实现栈,至于以顺序表作为基础的栈实现,将以源码提供。这里先声明一个顺序栈其代码如下,实现Stack和Serializable接口:

/*
* 顺序栈的实现
 */
public class SeqStack<T> implements Stack<T>,Serializable {

 private static final long serialVersionUID = -5413303117698554397L;

 /**
  * 栈顶指针,-1代表空栈
  */
 private int top=-1;

 /**
  * 容量大小默认为10
  */
 private int capacity=10;

 /**
  * 存放元素的数组
  */
 private T[] array;

 private int size;

 public SeqStack(int capacity){
  array = (T[]) new Object[capacity];
 }

 public SeqStack(){
  array= (T[]) new Object[this.capacity];
 }
 //.......省略其他代码
}

其获取栈顶元素值的peek操作过程如下图(未删除只获取值):

以上是获取栈顶元素的操作,代码如下:

/**
 * 获取栈顶元素的值,不删除
 * @return
 */
 @Override
 public T peek() {
  if(isEmpty())
   new EmptyStackException();
  return array[top];
 }

从栈添加元素的过程如下(更新栈顶top指向):

以上是入栈操作,代码如下:

/**
 * 添加元素,从栈顶(数组尾部)插入
 * 容量不足时,需要扩容
 * @param data
 */
@Override
public void push(T data) {
 //判断容量是否充足
 if(array.length==size)
  ensureCapacity(size*2+1);//扩容

 //从栈顶添加元素
 array[++top]=data;
 }

栈弹出栈顶元素的过程如下(删除并获取值):

以上是出栈操作,代码如下:

/**
 * 从栈顶(顺序表尾部)删除
 * @return
 */
 @Override
 public T pop() {
  if(isEmpty())
   new EmptyStackException();
  size--;
  return array[top--];
 }

到此,顺序栈的主要操作已实现完,是不是发现很简单,确实如此,栈的主要操作就这样,当然我们也可以通过前一篇介绍的MyArrayList作为基础来实现顺序栈,这个也比较简单,后面也会提供带代码,这里就不过多啰嗦了。下面给出顺序栈的整体实现代码:

import java.io.Serializable;
import java.util.EmptyStackException;

/*
 * 顺序栈的实现
 */
public class SeqStack<T> implements Stack<T>,Serializable {

 private static final long serialVersionUID = -5413303117698554397L;

 /**
  * 栈顶指针,-1代表空栈
  */
 private int top=-1;

 /**
  * 容量大小默认为10
  */
 private int capacity=10;

 /**
  * 存放元素的数组
  */
 private T[] array;

 private int size;

 public SeqStack(int capacity){
  array = (T[]) new Object[capacity];
 }

 public SeqStack(){
  array= (T[]) new Object[this.capacity];
 }

 public int size(){
  return size;
 }

 @Override
 public boolean isEmpty() {
  return this.top==-1;
 }

 /**
  * 添加元素,从栈顶(数组尾部)插入
  * @param data
  */
 @Override
 public void push(T data) {
  //判断容量是否充足
  if(array.length==size)
   ensureCapacity(size*2+1);//扩容

  //从栈顶添加元素
  array[++top]=data;

  size++;
 }

 /**
  * 获取栈顶元素的值,不删除
  * @return
  */
 @Override
 public T peek() {
  if(isEmpty())
   new EmptyStackException();
  return array[top];
 }

 /**
  * 从栈顶(顺序表尾部)删除
  * @return
  */
 @Override
 public T pop() {
  if(isEmpty())
   new EmptyStackException();
  size--;
  return array[top--];
 }

 /**
  * 扩容的方法
  * @param capacity
  */
 public void ensureCapacity(int capacity) {
  //如果需要拓展的容量比现在数组的容量还小,则无需扩容
  if (capacity<size)
   return;

  T[] old = array;
  array = (T[]) new Object[capacity];
  //复制元素
  for (int i=0; i<size ; i++)
   array[i]=old[i];
 }

 public static void main(String[] args){
  SeqStack<String> s=new SeqStack<>();
  s.push("A");
  s.push("B");
  s.push("C");
  System.out.println("size->"+s.size());
  int l=s.size();//size 在减少,必须先记录
  for (int i=0;i<l;i++){
   System.out.println("s.pop->"+s.pop());
  }

  System.out.println("s.peek->"+s.peek());
 }
}

链式栈的设计与实现

  了解完顺序栈,我们接着来看看链式栈,所谓的链式栈(Linked Stack),就是采用链式存储结构的栈,由于我们操作的是栈顶一端,因此这里采用单链表(不带头结点)作为基础,直接实现栈的添加,获取,删除等主要操作即可。其操作过程如下图:

从图可以看出,无论是插入还是删除直接操作的是链表头部也就是栈顶元素,因此我们只需要使用不带头结点的单链表即可。代码实现如下,比较简单,不过多分析了:

import com.zejian.structures.LinkedList.singleLinked.Node;

import java.io.Serializable;

/*
 * 栈的链式实现
 */
public class LinkedStack<T> implements Stack<T> ,Serializable{

 private static final long serialVersionUID = 1911829302658328353L;

 private Node<T> top;

 private int size;

 public LinkedStack(){
  this.top=new Node<>();
 }

 public int size(){
  return size;
 }

 @Override
 public boolean isEmpty() {
  return top==null || top.data==null;
 }

 @Override
 public void push(T data) {
  if (data==null){
   throw new StackException("data can\'t be null");
  }
  if(this.top==null){//调用pop()后top可能为null
   this.top=new Node<>(data);
  }else if(this.top.data==null){
   this.top.data=data;
  }else {
   Node<T> p=new Node<>(data,this.top);
   top=p;//更新栈顶
  }
  size++;
 }

 @Override
 public T peek() {
  if(isEmpty()){
   throw new EmptyStackException("Stack empty");
  }

  return top.data;
 }

 @Override
 public T pop() {
  if(isEmpty()){
   throw new EmptyStackException("Stack empty");
  }

  T data=top.data;
  top=top.next;
  size--;
  return data;
 }
 //测试
 public static void main(String[] args){
  LinkedStack<String> sl=new LinkedStack<>();
  sl.push("A");
  sl.push("B");
  sl.push("C");
  int length=sl.size();
  for (int i = 0; i < length; i++) {
   System.out.println("sl.pop->"+sl.pop());
  }
 }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Java用数组实现循环队列的示例

    复习了下数据结构,用Java的数组实现一下循环队列. 队列的类 //循环队列 class CirQueue{ private int QueueSize; private int front; private int rear; private int[] queueList ; public CirQueue(int QueueSize){ this.QueueSize = QueueSize; queueList = new int[QueueSize]; front = 0; rear =

  • java数据结构与算法之双向循环队列的数组实现方法

    本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

  • Java数据结构之简单链表的定义与实现方法示例

    本文实例讲述了Java数据结构之简单链表的定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 只有一个数据项(链接点Link),每个数据插入时都是对第一个数据的引用. 2.插入数据说明: 当链表没有数据时,插入的值就是第一个数据,如果链表里有数据,就把当前的数据的next指针指向第一个数据. 3.插入数据图: 4.特点:先进后出 5.实现功能: 数据插入,指定位置插入,显示,查询,删除等 6.删除原理 7.插入头节点原理 二.实现: 1.创建节点 /** * @描述 节点

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

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

  • java 数据结构单链表的实现

    java 数据结构单链表的实现 单链表实现链表的打印及元素删除操作,链表的实现主要是next属性的定义,将一堆节点关联起来的.实现简单的链表如下: public class LinkNode { private int value; private LinkNode next; public LinkNode(int x) { value = x; } public LinkNode getNext(){ return next; } public void setNext(LinkNode n

  • Java数据结构之双端链表原理与实现方法

    本文实例讲述了Java数据结构之双端链表原理与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.什么时双端链表: 链表中保持这对最后一个连点引用的链表 2.从头部插入 要对链表进行判断,如果为空则设置尾节点为新添加的节点 3.从尾部进行插入 如果链表为空,则直接设置头节点为新添加的节点,否则设置尾节点的后一个节点为新添加的节点 4.从头部删除 判断节点是否有下个节点,如果没有则设置节点为null 二.具体实现 /** * @描述 头尾相接的链表 * @项目名称 Java_DataStr

  • Java数据结构之简单的连接点(link)实现方法示例

    本文实例讲述了Java数据结构之简单的连接点(link)实现方法.分享给大家供大家参考,具体如下: 一.概述: 链接点由:数据和指向下个数据的指针构成 如图: 二.简单实现: package com.java.link; /** * @描述 TODO * @项目名称 Java_DataStruct * @包名 com.java.link * @类名 Link * @author chenlin */ public class Link { private long data; private L

  • 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.基本概念: 栈是一种数据结构,是只能在某一端插入和删除的特殊线性表.它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来). 栈是允许在同一端进行插入和删除操作的特殊线性表.允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom):栈底固定,而栈顶 浮动:栈中元素个数为零时称为空栈.插入一般

  • Java数据结构之循环队列简单定义与用法示例

    本文实例讲述了Java数据结构之循环队列简单定义与用法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 与普通队列的区别在于循环队列添加数据时,如果其有效数据end == maxSize - 1(最大空间)的话,end指针又移动到-1的位置 删除数据时,如果head== maxSize时 head指针移动到0的位置 2.示例图: 二.实现代码: package com.java.queue; /** * @描述 对列 * @项目名称 Java_DataStruct * @包名 com.

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

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

随机推荐