关键词：
1、栈-概念
栈是一种用于存储数据的简单数据结构，类似链表或者顺序表（统称线性表），栈与线性表的最大区别是数据的存取的操作，我们可以这样认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈，栈的结构如下图：
由上图，我们可看出，栈只能从栈顶存取元素，同时先进入的元素反而是后出，而栈顶永远指向栈内最顶部的元素。到此可以给出栈的正式定义：栈(Stack)是一种有序特殊的线性表，只能在表的一端(称为栈顶，top，总是指向栈顶元素)执行插入和删除操作，最后插入的元素将第一个被删除，因此栈也称为后进先出(Last In First Out,LIFO)或先进后出(First In Last Out FILO)的线性表。栈的基本操作创建栈，判空，入栈，出栈，获取栈顶元素等，注意栈不支持对指定位置进行删除，插入，其接口Stack声明如下：
public interface Stack<T>
boolean isEmpty(); // 判断栈是否为空 void push(T data); // data元素入栈 T peek(); //返回栈顶元素（未出栈） T pop(); //出栈,返回栈顶元素,同时从栈中移除该元素
2、顺序栈的设计与实现
顺序栈，顾名思义就是采用顺序表实现的的栈，顺序栈的内部以顺序表为基础，实现对元素的存取操作，当然我们还可以采用内部数组实现顺序栈，在这里我们使用内部数据组来实现栈，代码如下：
import java.io.Serializable; /** * 顺序栈的实现 */ public class SeqStack<T> implements Stack<T>,Serializable private static final long serialVersionUID = -5413303117698554397L; private int top=-1; // 栈顶指针,-1代表空栈 private int capacity=10; //容量大小默认为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; // -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()) throw new EmptyStackException("Stack empty"); return array[top]; /** * 从栈顶(顺序表尾部)删除 * @return */ @Override public T pop() if(isEmpty()) throw new EmptyStackException("Stack empty"); 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 class StackException extends RuntimeException public StackException(String msg) super(msg);
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());
现在逐个方法分析:
1、获取栈顶元素值的peek操作过程如下图（未删除只获取值）：
2、入栈过程如下（更新栈顶top指向）：
3、栈弹出栈顶元素的过程如下（删除并获取值）：
到此，顺序栈的主要操作已实现完，栈的主要操作就这样简单。
3、链式栈的设计与实现
了解完顺序栈，我们接着来看看链式栈，所谓的链式栈（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());
4、栈的应用
栈是一种很重要的数据结构，在计算机中有着很广泛的应用，如下一些操作都应用到了栈。
- 符号匹配
- 中缀表达式转换为后缀表达式
- 计算后缀表达式
- 实现函数的嵌套调用
- HTML和XML文件中的标签匹配
- 网页浏览器中已访问页面的历史记录
接下来我们分别对符合匹配，中缀表达式转换为后缀表达式进行简单的分析，以加深我们对栈的理解
4.1、符号匹配
在编写程序的过程中，我们经常会遇到诸如圆括号“()”与花括号“”，这些符号都必须是左右匹配的，这就是我们所说的符合匹配类型，当然符合不仅需要个数相等，而且需要先左后右的依次出现，否则就不符合匹配规则，如“)(”，明显是错误的匹配，而“()”才是正确的匹配。有时候符合如括号还会嵌套出现，如“9-(5+(5+1))”,而嵌套的匹配原则是一个右括号与其前面最近的一个括号匹配，事实上编译器帮我检查语法错误也是执行一样的匹配原理，而这一系列操作都需要借助栈来完成，接下来我们使用栈来实现括号”()”是否匹配的检测。
判断原则如下（str=”((5-3)*8-2)”）：
- a.设置str是一个表达式字符串，从左到右依次对字符串str中的每个字符char进行语法检测，如果char是，左括号则入栈，如果char是右括号则出栈(有一对匹配就可以去匹配一个左括号，因此可以出栈)，若此时出栈的字符char为左括号，则说明这一对括号匹配正常，如果此时栈为空或者出栈字符不为左括号，则表示缺少与char匹配的左括号，即目前不完整。
- b.重复执行a操作，直到str检测结束，如果此时栈为空，则全部括号匹配，如果栈中还有左括号，是说明缺少右括号。
整个检测算法的执行流程如下图：
/** * 表达式检测 */ public class CheckExpression // 这类似相亲节目，1个男的必须配1个女的 // 房间里来1个女的，女的入栈 // 如果来1男的，男的与女的牵手成功，则女的出栈 // 最后房间为空，则表明所有男女配对成功 public static String isValid(String expstr) LinkedStack<String> stack = new LinkedStack<>(); //创建栈 int i=0; while(i<expstr.length()) char ch=expstr.charAt(i); i++; switch(ch) case ‘(‘: stack.push(ch+""); //左括号直接入栈 break; case ‘)‘: if (stack.isEmpty() || !stack.pop().equals("(")) return "("; //遇见右括号左括号直接出栈 //最后检测栈是否为空,为空则检测通过 if(stack.isEmpty()) return "check pass!"; else return "check exception!"; public static void main(String args[]) String expstr="((5-3)*8-2)"; System.out.println(expstr+" "+isValid(expstr));
4.2、中缀表达式转换为后缀表达式
我们先来了解一下什么是中缀表达式，平常所见到的计算表达式都算是中缀表达式，如以下的表达式：
1+3*(9-2)+9 --->中缀表达式（跟日常见到的表达式没啥区别）
了解中缀表达式后来看看其定义：将运算符写在两个操作数中间的表达式称为中缀表达式。在中缀表达式中，运算符拥有不同的优先级，同时也可以使用圆括号改变运算次序，由于这两点的存在，使用的中缀表达式的运算规则比较复杂，求值的过程不能从左往右依次计算，当然这也是相对计算机而言罢了，毕竟我们日常生活的计算使用的还是中缀表达式。既然计算机感觉复杂，那么我们就需要把中缀表达式转化成计算机容易计算而且不复杂的表达式，这就是后缀表达式了，在后缀表达式中，运算符是没有优先级的，整个计算都是遵守从左往右的次序依次计算的，如下我们将中缀表达式转为后缀表达式：
1+3*(9-2)+9 转化前的中缀表达式 1 3 9 2 - * + 9 + 转化后的后缀表达式
中缀转后缀的转换过程需要用到栈，这里我们假设栈A用于协助转换，并使用数组B用于存放转化后的后缀表达式具体过程如下：
1）如果遇到操作数，我们就直接将其放入数组B中。
2）如果遇到运算符，则我们将其放入到栈A中，遇到左括号时我们也将其放入栈A中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的运算符输出并存入数组B中直到遇到左括号为止。注意，左括号只弹出并不存入数组。
4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素存入数组B直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到” ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( “。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出存入到数组B中。
6）到此中缀表达式转化为后缀表达式完成，数组存储的元素顺序就代表转化后的后缀表达式。
执行图示过程如下：
简单分析一下流程，当遇到操作数时（规则1），直接存入数组B中，当i=1（规则2）时，此时运算符为+，直接入栈，当i=3(规则2)再遇到运算符 *，由于栈内的运算符+优先级比*低，因此直接入栈，当i=4时，遇到运算符 ’(‘，直接入栈，当 i=6时，遇运算符 -，直接入栈，当i=8时（规则3），遇 ’)’，- 和 ’(‘直接出栈，其中运算符-存入后缀数组 B中，当 i=9时（规则5），由于*优先级比+高，而 +与 +平级，因此 和+出栈，存入数组B，而后面的 +再入栈，当i=10（规则5），结束，+直接出栈存入数组B，此时数组B的元素顺序即为1 3 9 2 - * + 9 +，这就是中缀转后缀的过程。
接着转成后缀后，我们来看看计算机如何利用后缀表达式进行结果运算，通过前面的分析可知，后缀表达式是没有括号的，而且计算过程是按照从左到右依次进行的，因此在后缀表达的求值过程中，当遇到运算符时，只需要取前两个操作数直接进行计算即可，而当遇到操作数时不能立即进行求值计算，此时必须先把操作数保存等待获取到运算符时再进行计算，如果存在多个操作数，其运算次序是后出现的操作数先进行运算，也就是后进先运算，因此后缀表达式的计算过程我们也需要借助栈来完成，该栈用于存放操作数，后缀表达式的计算过程及其图解如下：
借助栈的程序计算过程：
简单分析说明一下：
1)如果ch是数字，先将其转换为整数再入栈
2)如果是运算符，将两个操作数出栈，计算结果再入栈
3)重复1）和2）直到后缀表达式结束，最终栈内的元素即为计算的结果。
整体整体呈现实现如下：
/** * 中缀转后缀,然后计算后缀表达式的值 */ public class CalculateExpression /** * 中缀转后缀 * @param expstr 中缀表达式字符串 * @return */ public static String toPostfix(String expstr) //创建栈,用于存储运算符 SeqStack<String> stack = new SeqStack<>(expstr.length()); String postfix=""; //存储后缀表达式的字符串 int i=0; while (i<expstr.length()) char ch=expstr.charAt(i); switch (ch) case ‘+‘: case ‘-‘: //当栈不为空或者栈顶元素不是左括号时,直接出栈,因此此时只有可能是*/+-四种运算符(根据规则4),否则入栈 while (!stack.isEmpty() && !stack.peek().equals("(")) postfix += stack.pop(); //入栈 stack.push(ch+""); i++; break; case ‘*‘: case ‘/‘: //遇到运算符*/ while (!stack.isEmpty() && (stack.peek().equals("*") || stack.peek().equals("/"))) postfix += stack.pop(); stack.push(ch+""); i++; break; case ‘(‘: //左括号直接入栈 stack.push(ch+""); i++; break; case ‘)‘: //遇到右括号(规则3) String out = stack.pop(); while (out!=null && !out.equals("(")) postfix += out; out = stack.pop(); i++; break; default: //操作数直接入栈 while (ch>=‘0‘ && ch<=‘9‘) postfix += ch; i++; if (i<expstr.length()) ch=expstr.charAt(i); else ch=‘=‘; //分隔符 postfix += " "; break; //最后把所有运算符出栈(规则5) while (!stack.isEmpty()) postfix += stack.pop(); return postfix; /** * 计算后缀表达式的值 * @param postfix 传入后缀表达式 * @return */ public static int calculatePostfixValue(String postfix) //栈用于存储操作数,协助运算 LinkedStack<Integer> stack = new LinkedStack<>(); int i=0, result=0; while (i<postfix.length()) char ch=postfix.charAt(i); if (ch>=‘0‘ && ch<=‘9‘) result=0; while (ch!=‘ ‘) //将整数字符转为整数值ch=90 result = result*10 + Integer.parseInt(ch+""); i++; ch = postfix.charAt(i); i++; stack.push(result);//操作数入栈 else //ch 是运算符,出栈栈顶的前两个元素 int y= stack.pop(); int x= stack.pop(); switch (ch) //根据情况进行计算 case ‘+‘: result=x+y; break; case ‘-‘: result=x-y; break; case ‘*‘: result=x*y; break; case ‘/‘: result=x/y; break; //注意这里并没去判断除数是否为0的情况 //将运算结果入栈 stack.push(result); i++; //将最后的结果出栈并返回 return stack.pop(); //测试 public static void main(String args[]) String expstr="1+3*(9-2)+90"; String postfix = toPostfix(expstr); System.out.println("中缀表达式->expstr= "+expstr); System.out.println("后缀表达式->postfix= "+postfix); System.out.println("计算结果->value= "+calculatePostfixValue(postfix));
转载自：https://github.com/shinezejian/javaStructures
数据结构与算法(代码片段)
数据结构与算法一、基本概念1.1、数据结构起源1.2、数据结构1.3、数据结构基本概念1.4、数据结构三要素1.5、数据结构三个方面二、线性表（逻辑结构）2.1、线性表的概念2.2、顺序表2.3、链表2.4、顺序表vs链表2.5、双链表... 查看详情
一起学数据结构与算法深度学习栈(代码片段)
目录一、什么是栈？二、怎么使用栈？2.1入栈-push()2.2判空-empty()2.3出栈-pop()2.4获取栈顶元素-peek()2.5获取栈中有效元素个数-size()三、栈的模拟实现3.1push3.2isEmpty3.3pop3.4peek3.5MyStack.java四、经典题4.1有效的括号4.2逆波兰表达式... 查看详情
数据结构与算法学习笔记栈和队列ⅰ(代码片段)
数据结构与算法学习笔记(5)栈和队列文章目录数据结构与算法学习笔记(5)栈和队列一.栈和队列的定义和特点1.栈的定义和特点相关概念示意图栈与一般线性表的不同2.队列的定义和特点相关概念二.案例引入1.栈的典型案例进制转... 查看详情
数据结构与算法——栈和队列(代码片段)
😊数据结构与算法——栈和队列🚀前言🚀栈（satck）🚢栈的定义🚢共享栈（节省空间）🚢栈的表示和实现（顺序栈）👻顺序栈的定义👻初始化操作👻进栈操作👻... 查看详情
五种编程语言解释数据结构与算法—链式栈(代码片段)
目录五种编程语言解释数据结构与算法—链式栈1、栈的链式存储结构介绍1.1、逻辑结构示意图2、栈的应用2.1、括号匹配问题2.2、表达式求值问题3、栈和递归的关系4、C语言实现链式栈4.1、LinkStack.h文件的内容4.2、LinkStack.c文件中... 查看详情
《数据结构与算法》-3-栈和队列(代码片段)
目录1.栈1.1栈的基本概念1.2栈的顺序存储结构1.3栈的链式存储结构2.队列2.1队列的基本概念2.2队列的顺序存储结构2.3队列的链式存储结构2.4双端队列3.栈和队列的应用3.1栈在括号匹配中的应用3.2栈在表达式求值中的应用3.3栈对递归... 查看详情
结构与算法-----栈(代码片段)
...组，数组更多的是用来进行数据的存储，我们期望的数据结构是插入、删除和查找性能都比较好。对于无序数组，插入快，但是删除和查找都很慢，为了解决这些问题，后面我们会讲解比如二叉树、哈希表的数据结构。 而本... 查看详情
《图解数据结构与算法》（java代码实现注释解析算法分析）(代码片段)
文章目录第1章数据结构与算法基础概述1.1数据结构和算法的重要性1.2数据结构概述逻辑结构存储结构1.3算法概述如何理解“大O记法”时间复杂度空间复杂度第2章数组2.1数组概念2.2无序数组2.3有序数组第三章栈3.1栈概念3.2栈的操... 查看详情
数据结构与算法—数组栈和链表栈(代码片段)
数据结构与算法—数组栈和链表栈🌈一览众山小数据结构与算法—数组栈和链表栈栈介绍栈图解栈实现数组实现栈实现思路实现代码单链表实现栈实现思路(图解)实现代码栈总结栈力扣栈介绍栈,存储货物或供旅客住宿的地方... 查看详情
数据结构与算法(代码片段)
数据结构与算法1.数组模拟循环队列1.1.实现的关键步骤：1.2.实现代码2.单链表2.1.实现的关键步骤：2.2.实现代码2.3.拓展：3.双链表3.1.实现的关键步骤3.2.实现代码：4.单向环形链表5.数组模拟栈（stack）5.1.实... 查看详情
数据结构与算法：栈+队列+递归(代码片段)
【栈】Python实现：1.用数组实现一个顺序栈classSStack():def__init__(self):self._elems=[]defis_empty(self):returnself._elems==[]deftop(self):ifself._elems==[]:raiseStackUnderflow("inSStack.top()")returnself._elems[-1]de 查看详情
数据结构与算法分析-2-栈adt(代码片段)
1.描述：实质是一种受到限制的表，即插入删除只能在表的末端，能够实现LIFO（后进先出）2.栈的实现 链表实现（链栈） 数组实现（顺序栈） 3.链栈创建一个空栈1structNode23intvalue;4Node*next;5;67//创建了一个头节点为S的... 查看详情
数据结构与算法栈与队列c语言版(代码片段)
目录3.1栈和队列的定义和特点3.2栈、队列与一般线性表的区别3.3栈的表示和操作的实现顺序栈与顺序表=================顺序栈的表示顺序栈初始化判断顺序栈是否为空求顺序栈的... 查看详情
学习数据结构笔记=====＞栈(代码片段)
学习来源–>传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）案例引入;一个计算器的运算原理比如说输入5*6+3-2;计算器收到的是一个字符串,他就得一个一个分隔这些字符;然后计算;栈(Stack)先进后出的... 查看详情
数据结构与算法--栈和队列(代码片段)
...此，栈又称为后进先出（lastinfirstout）的线性表（简称LIFO结构）。表示及实现栈是一种"特殊"的线性存储结构，因此栈的具体实现有以下两种方式：顺序栈：采用顺序存储结构可以模拟栈存储数 查看详情
数据结构与算法同种算法分别用递归/回溯与栈实现(代码片段)
一、阶乘importjava.util.Stack;publicclassMain publicstaticintfact1(intn) if(n==0)return1; elsereturnn*fact1(n-1); publicstaticintfact2(intn) intans=1; Stack<Integer>stack=ne 查看详情
[nefu数据结构]阶段一复习(代码片段)
文章目录[NEFU数据结构]阶段一复习算法模块第1章绪论1.2基本概念和术语逻辑结构：存储结构：1.3抽象数据类型的表示与实现1.4算法和算法分析第2章线性表2.3~2.4线性表的顺序存储结构2.5线性表的链式表示和实现单链表循... 查看详情
数据结构与算法.栈队列(代码片段)
...ff0c;栈二、队列一，栈定义：一种操作受限的线性结构特点：①栈中数据遵从’先进先出‘原则②只能在栈顶对数据进行操作（出栈pop和入栈push）基于数组的栈：顺序栈基于链表的栈：链式栈栈中的常... 查看详情