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

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

# Java  # 数据结构  # 算法  # 栈  # Java数据结构与算法之栈(动力节点Java学院整理)  # java数据结构关于栈的实例应用  # Java数据结构之栈与队列实例详解  # java数据结构之栈的详解  # java数据结构基础:栈  # 带你了解Java数据结构和算法之栈  # 链式  # 是一种  # 线性表  # 的是  # 链表  # 如下图  # 到此  # 来实现  # 为空  # 操作过程  # 默认为  # 在这里  # 也会  # 还可以  # 第一个  # 就不  # 没有任何  # 我们可以  # 可以通过 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： Win11怎样安装网易有道词典_Win11安装词典教程【步骤】  javascript事件捕获机制【深入分析IE和DOM中的事件模型】  Laravel定时任务怎么设置_Laravel Crontab调度器配置  Laravel怎么设置路由分组Prefix_Laravel多级路由嵌套与命名空间隔离【步骤】  Laravel如何将应用部署到生产服务器_Laravel生产环境部署流程  猪八戒网站制作视频,开发一个猪八戒网站，大约需要多少？或者自己请程序员，需要什么程序员，多少程序员能完成？  大同网页,大同瑞慈医院官网？  Laravel API资源类怎么用_Laravel API Resource数据转换  绝密ChatGPT指令：手把手教你生成HR无法拒绝的求职信  合肥制作网站的公司有哪些,合肥聚美网络科技有限公司介绍？  Android仿QQ列表左滑删除操作  Laravel怎么防止CSRF攻击_Laravel CSRF保护中间件原理与实践  Laravel Facade的原理是什么_深入理解Laravel门面及其工作机制  如何快速搭建安全的FTP站点？  Bootstrap整体框架之JavaScript插件架构  高防服务器：AI智能防御DDoS攻击与数据安全保障  ChatGPT回答中断怎么办 引导AI继续输出完整内容的方法  Laravel全局作用域是什么_Laravel Eloquent Global Scopes应用指南  北京网站制作费用多少,建立一个公司网站的费用.有哪些部分,分别要多少钱？  Android Socket接口实现即时通讯实例代码  香港服务器如何优化才能显著提升网站加载速度？  Laravel如何实现用户角色和权限系统_Laravel角色权限管理机制  如何在阿里云虚拟机上搭建网站？步骤解析与避坑指南  linux写shell需要注意的问题(必看)  Python结构化数据采集_字段抽取解析【教程】  html5如何实现懒加载图片_ intersectionobserver api用法【教程】  专业型网站制作公司有哪些,我设计专业的，谁给推荐几个设计师兼职类的网站？  新三国志曹操传主线渭水交兵攻略  html5怎么画眼睛_HT5用Canvas或SVG画眼球瞳孔加JS控制动态【绘制】  php读取心率传感器数据怎么弄_php获取max30100的心率值【指南】  Laravel Vite是做什么的_Laravel前端资源打包工具Vite配置与使用  Microsoft Edge如何解决网页加载问题 Edge浏览器加载问题修复  HTML 中动态设置元素 name 属性的正确语法详解  Laravel怎么返回JSON格式数据_Laravel API资源Response响应格式化【技巧】  Laravel策略(Policy)如何控制权限_Laravel Gates与Policies实现用户授权  ChatGPT 4.0官网入口地址 ChatGPT在线体验官网  如何快速生成高效建站系统源代码？  Python面向对象测试方法_mock解析【教程】  Laravel如何部署到服务器_线上部署Laravel项目的完整流程与步骤  如何在建站之星绑定自定义域名？  焦点电影公司作品,电影焦点结局是什么？  深圳网站制作平台,深圳市做网站好的公司有哪些？  PHP正则匹配日期和时间(时间戳转换)的实例代码  如何在自有机房高效搭建专业网站？  Laravel Blade模板引擎语法_Laravel Blade布局继承用法  详解Nginx + Tomcat 反向代理 如何在高效的在一台服务器部署多个站点  laravel怎么配置和使用PHP-FPM来优化性能_laravel PHP-FPM配置与性能优化方法  如何构建满足综合性能需求的优质建站方案？  高防服务器租用首荐平台，企业级优惠套餐快速部署  如何在不使用负向后查找的情况下匹配特定条件前的换行符