栈: 一个先入后出的有序序列(First In LastOut)
限制线性表中的插入和删除只在同一端进行,允许插入和删除的一段叫做栈顶(Top),另外一段叫做栈底(Bottom),所以最先放入的元素在栈底,最后放入的元素在栈顶。
总有一个变量指向栈顶,如果栈为空,那么栈顶变量下标为-1.
常用的场景:
1)子程序的调用,在跳往子程序之前,会将下一个指令的地址存到堆栈中,直到子程序结束再将地址取出,回到原来的程序中。
2)处理递归调用,类似子程序调用,只是除了存储下一个指令的地址外,也将参数,区域变量等数据存入堆栈中
3)表达式的转换与求值
4)二叉树的遍历
5)图的深度优先搜索法(depth-first)
package com.dataStructure.heapStack; import javax.swing.Popup; public class MyStack { private int top = -1;//该栈为空 private int maxSize = 50;//该栈最大容量 private Object[] stacks = new Object[maxSize]; /** * 入栈 * @param data */ public void push(Object data){ //Check stack if max if(this.top == maxSize-1){ System.out.println("该栈已经最大了,不能存放数据了"); return; } this.top++; this.stacks[this.top] = data; } /** * 出栈,取栈顶的值 */ public Object pop(){ if(this.top == -1){ System.out.println("该栈为空"); return -1; } Object topValue = this.stacks[this.top]; this.top--; return topValue; } public int getResult(int num1, int num2, String operation){ char[] operationCharArray = operation.toCharArray(); int result = 0; switch (operationCharArray[0]) { case '+': result = num1 + num2; break; case '-': result = num2 - num1; break; case '*': result = num1 * num2; break; case '/': result = num2 / num1; break; default: break; } return result; } public boolean isOperation(String character){ return character.equals("+") || character.equals("-") || character.equals("*") || character.equals("/"); } public boolean isEmpty(){ return this.top == -1; } public int getOperationPrior(String character){ return (character.equals("*") || character.equals("/")) ? 1 : 0; } public Object getTopValue(){ return this.stacks[this.top]; } public void showStack(Object[] stacks){ if(this.top == -1){ return; } for(int x = this.top; x > -1; x--){ System.out.println("当前第"+x+"元素: "+stacks[x]); } } public static void main(String[] args) { MyStack myStack = new MyStack(); myStack.push(3); myStack.push(25); myStack.push(12); myStack.push(15); myStack.pop(); myStack.showStack(myStack.getStacks()); } public int getTop() { return top; } public void setTop(int top) { this.top = top; } public int getMaxSize() { return maxSize; } public void setMaxSize(int maxSize) { this.maxSize = maxSize; } public Object[] getStacks() { return stacks; } public void setStacks(Object[] stacks) { this.stacks = stacks; } }
package com.dataStructure.heapStack; public class Calculate { private String expression = "100-60/2+2*14/4-12"; private MyStack numStack = new MyStack(); private MyStack operationStack = new MyStack(); private void scanExpression(String expression){ int index = 0; while(true){ //依次取出字符 String singleCharacter = expression.substring(index, 1); //判断singleCharacter是不是运算符 if(this.operationStack.isOperation(singleCharacter)){ //如果为空,直接入符号栈 if(this.operationStack.isEmpty()){ this.operationStack.push(singleCharacter); }else{//表示不为空 this.operationStack.push(singleCharacter); int currentOperation = this.operationStack.getOperationPrior(singleCharacter); int topOperation = Integer.valueOf((String)this.operationStack.getTopValue()); if(currentOperation <= topOperation){ //数栈弹出两个数, int num1 = Integer.valueOf((String)this.numStack.pop()); int num2 = Integer.valueOf((String)this.numStack.pop()); String operationTop = (String)this.operationStack.pop(); int result = this.numStack.getResult(num1, num2, operationTop); this.numStack.push(result); } } }else{ //如果是数字就入数栈 this.numStack.push(singleCharacter); } index++; //check if complete the scan if(index == this.expression.length()){ break; } } } }
相关推荐
数据结构与算法 数据结构-栈和队列全文共41页,当前为第1页。 一、线性结构 (二)栈和队列 数据结构-栈和队列全文共41页,当前为第2页。 1.定义 2.1 栈 与线性表相同,仍为一对一( 1:1)关系。 用顺序栈或链栈存储均...
C语言-数据结构-栈队列实现
数据结构-栈的C语言实现,随手笔记
数据结构-栈的顺序存储
C++实现数据结构-栈
Java语言编写的数据结构-栈的实现,包括顺序栈和链栈。
定义了栈,只含有一些基本操作,算法很少,对大学初学数据结构者有用
Educoder题目:数据结构-栈基本运算的实现及其应用答案解析.md
数据结构-栈的基本操作-代码
数据结构-栈相关算法和功能
数据结构-栈的应用:顺序栈与链栈的应用
基于C语言的数据结构-栈stack
"数据结构-栈和队列-PPT" 数据结构中栈和队列是两种常用的线性表结构,下面对它们的定义、特点和应用进行详细介绍。 栈的定义和特点 栈是一种只能在一端(栈顶)进行插入和删除运算的线性表。栈的逻辑结构与...
java基础笔记数据结构-栈,详细描述了栈的原理及其实现方式,基础数据结构。
数据结构 -- C语言版 -- 栈的部分实现代码(栈的实现、栈的应用),详细介绍参考数据结构--栈的系列博文。链接为:https://blog.csdn.net/songshuai0223/category_9742561.html。
数据结构-栈 中缀转后缀再计算 算术表达式-代码
数据结构-栈的定义及基本操作(代码+报告)
Java基础复习笔记05数据结构-栈~~~~~~~~~~