数据结构之栈（Stack）

陆砚码

2026-07-09 • 👁 0人浏览过

简介栈是一种线性结构，具有先进后出的特点，即先入栈的最后出栈。

删除时刚好相反：最后放入的元素最先删除，最先放入的元素最后删除。

栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。

允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

入栈示意图

出栈示意图

栈是集合Vector的一个子类，它实现了一个标准的后进先出的栈。

堆栈只定义了默认构造函数，用来创建一个空栈。

堆栈除了包括由Vector定义的所有方法，也定义了自己的一些方法。

常用方法： 1 boolean empty() 判断堆栈是否为空。

2 Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。

3 Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。

4 Object push(Objectelement) 把项压入堆栈顶部。

应用场景子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。

处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。

表达式的转换[中缀表达式转后缀表达式]与求值二叉树的遍历。

图形的深度优先(depth一first)搜索法。

栈的实现栈有两种实现方式：数组和链表。

使用数组模拟栈：

  package DataStructure.Stack;


/**
* @author Jerssy
* @version V1.0
* @Description 栈
* @create 2021-02-17 17:31
*/


public class ArrayStack {


private  int head;
private final T[] arr;
private final int maxSize;


public static void main(String[] args) {
ArrayStack stack = new ArrayStack<>(5);
stack.push(1);
stack.push(2);
stack.push(-1);
stack.push(0);
stack.push(5);
System.out.println(stack);
System.out.println(stack.pop());
System.out.println(stack);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
stack.push(8);
stack.push(98);
System.out.println(stack);
}


public ArrayStack(int arrMaxSize){
if (arrMaxSize <= 0) throw new IndexOutOfBoundsException("arrMaxSize 不能为0");
maxSize=arrMaxSize;


arr= (T []) new Object[arrMaxSize];
head=-1;//指向栈顶
}


public  void push(T t){
if (isFull()){
throw new IndexOutOfBoundsException("栈已满");
}
arr[++head]=t;
}


public  boolean isEmpty() {
return  head==-1;
}


//判断队列满
public  boolean isFull(){


return  head==maxSize-1;
}


public T pop() {


if (isEmpty()) {
throw new RuntimeException("栈为空");
}


return arr[head--];
}


public  String toString() {
StringBuilder buf = new StringBuilder();
for(int j=head;j>=0;j--){
buf.append(arr[j]);
if (j == 0) {
break;
}
buf.append("---");
}
return buf.toString();
}
}

单链表模拟栈

package DataStructure.Stack;


import java.util.ArrayList;
import java.util.List;


/**
* @author Jerssy
* @version V1.0
* @Description 栈的单链表展现
* @create 2021-02-18 10:24
*/
public class LinkedStack {


private  Node top;


static  class  Node{


T item;
Node next;


public Node(T item) {
this.item = item;
}
@Override
public String toString() {
return "Node{" +
"item=" + item +
'}';
}
}


public  void push(T item) {


Node node= new Node<>(item);
if (top != null) {
node.next=top;
}
top=node;
}


public T  pop() {


if (top == null){
throw  new RuntimeException("栈为空");
}


Node  newNode = top.next;
T oldValue= top.item;
top.next = null;
top=newNode;


return oldValue;
}


public  String toString() {


if(top == null){
throw new RuntimeException("队列是空的");
}


List list = new ArrayList<>();


Node node=top;
while (node != null){
list.add((String) node.item);
node=node.next;
}


return  String.join("-->", list);
}


public static void main(String[] args) {
LinkedStack linkedStack=new LinkedStack<>();
linkedStack.push("kobe");
linkedStack.push("james");
linkedStack.push("leo");
linkedStack.push("cop");
linkedStack.push("io");


System.out.println(linkedStack);
linkedStack.pop();
linkedStack.pop();
linkedStack.pop();
System.out.println(linkedStack);
}
}

中缀，前缀，后缀表达式中缀表达式中缀表达式就是常见的运算表达式，如(3+4)×5-6 中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作。

下面使用栈模拟简易计算器：实现数（包括小数）的基本的加减乘除，取模，次方等运算操作思路其实比较简单：定义两个栈：数字栈和符号栈如果扫描发现是数字，则入数字栈如果发现扫描到运算符：如果当前符号栈为空则入符号栈如果符号栈不为空，有操作符，就进行比较运算符优先级，当前运算符优先级小于等于栈中的操作符从数字栈pop出两个数，符号栈pop一个符号进行运算，得到一个结果，入数字栈；然后当前运算符入符号栈如果符号栈不为空，有操作符。

当前运算符优先级大于栈中的操作符，就直接入符号栈扫描结束后就顺序的从数栈和符号栈pop相应的数和符号并运算,并将计算结果入数字栈最后数字栈只有一个数字，即表达式的结果小结：符号栈为空则直接入栈，若符号栈中栈顶优先级低，则该符号直接入栈，反之栈顶优先级高，则取出数字栈中两个元素和符号栈的一个符号进行计算结果入数字栈扫描结束从循环从数字栈依次弹出两个数字和符号栈弹出一个符号进行计算，并将结果入数字栈，最后弹出数字栈的栈顶即为表达式的最终结果。

package DataStructure.Stack;


import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Stack;


/**
* @author Jerssy
* @version V1.0
* @Description:使用栈(中缀表达式)实综合计算器
* @create 2021-02-18 16:36
*/
public class CalculateByStack {


public static void main(String[] args) {


new calculateFrame();


}


public static Double calculate(String str){
Stack numsStack=new Stack<>();//数字栈
Stack markStack=new Stack<>();//符号栈
String newStr=str.replaceAll("\\s*|\t|\r|\n","");
StringBuilder numBuilder= new StringBuilder();


for (int i = 0; i < newStr.length();i++) {
char calculateChar = newStr.charAt(i);
if (Character.isDigit(calculateChar)||calculateChar=='.') {
numBuilder.append(calculateChar);
int lastLen = newStr.length()-1;
char nextChar= newStr.charAt(Math.min(i+1,lastLen));
if (nextChar!='.'&&(!Character.isDigit(nextChar)||i==lastLen)){//下一个字符不是数字或者到末尾了
numsStack.push(Double.parseDouble(numBuilder.toString()));
numBuilder.delete(0,numBuilder.length());
}
}


else if(calculateChar=='('){
markStack.push(String.valueOf(calculateChar));
}
else if(calculateChar==')'){//计算括弧里的数据
while (true){
if (markStack.peek().charAt(0)=='('){
markStack.pop();
break;
}
Double result1 = numsStack.pop();
Double result2 = numsStack.pop();
String pop = markStack.pop();
Double result = countMarked(pop, result2, result1);
numsStack.push(result);
}


}else if (isOption(String.valueOf(calculateChar))){


if (!markStack.isEmpty()) {


boolean isHigh = isHighPriority(String.valueOf(newStr.charAt(i)),markStack.peek());
if (!isHigh) {//小于栈中的运算符优先级则计算
Double result1 = numsStack.pop();
Double result2 = numsStack.pop();
String pop = markStack.pop();
Double result = countMarked(pop, result2, result1);
numsStack.push(result);
}
}


markStack.push(String.valueOf(calculateChar));
}


}


while (!numsStack.isEmpty()&&!markStack.isEmpty()) {


Double result1 = numsStack.pop();
Double result2 = numsStack.pop();


String pop = markStack.pop();
numsStack.push(countMarked(pop, result2, result1));
}
return numsStack.pop();
}


public  static int  getPriority(String option){
return switch (option) {
case "+", "-" -> 0;
case "*", "/","%" -> 1;
case "^"-> 2;
default -> -1;
};


}
private static boolean isHighPriority(String operate1, String operate2) {


return getPriority(operate1) > getPriority(operate2);
}


public  static  boolean  isOption(String option){


return option.equals("+") || option.equals("-") || option.equals("*") || option.equals("/") || option.equals("%")|| option.equals("^");
}


public static Double countMarked(String pop, Double result2, Double result1){
Double aDouble2 = scaleResult(result2);
Double aDouble1 = scaleResult(result1);


return switch (pop){
case "+"-> aDouble2+aDouble1;
case  "-"-> aDouble2-aDouble1;
case  "*"-> aDouble2*aDouble1;
case  "/"-> aDouble2/aDouble1;
case  "%"-> aDouble2%aDouble1;
case  "^"-> Math.pow(aDouble2,aDouble1);
default -> throw new IllegalStateException("Unexpected value: " + pop);
};
}


private static Double scaleResult(Double result){
BigDecimal bd1 = new BigDecimal(String.valueOf(result));
BigDecimal bdResult= bd1.setScale(4, RoundingMode.HALF_UP);


return bdResult.doubleValue();


}


static class calculateFrame extends Frame {
Button  btn0, btn1, btn2, btn3, btn4, btn5, btn6, btn7, btn8, btn9, btn10,add,
min, mul, div,div1,div2,div3,div4, equal, clear, delete;
TextField tx;


public calculateFrame() {


//添加组件


btn0 = new Button("0");
btn1 = new Button("1");
btn2 = new Button("2");
btn3 = new Button("3");
btn4 = new Button("4");
btn5 = new Button("5");
btn6 = new Button("6");
btn7 = new Button("7");
btn8 = new Button("8");
btn9 = new Button("9");
btn10 = new Button(".");
add = new Button("+");
min = new Button("-");
mul = new Button("*");
div = new Button("/");
div1 = new Button("%");
div2 = new Button("(");
div3 = new Button(")");
div4 = new Button("^");
equal = new Button("=");
clear = new Button("clear");
delete = new Button("<-");
tx = new TextField("");


//添加一个面板
Panel panel = new Panel();
//设置面板布局
panel.setLayout(new GridLayout(4, 3));
addBtn(panel, btn0,btn1, btn2, btn3, btn4, btn5, btn6, btn7, btn8,btn9,btn10);
addBtn(panel, add, min, mul, div, div1,div2,div3,div4, delete);
//将面板添加到Frame中心
add(panel, BorderLayout.CENTER);
//将文本框添加到Frame
add(tx, BorderLayout.NORTH);
add(panel);
add(clear, BorderLayout.WEST);
add(equal, BorderLayout.EAST);


//添加事件监听
addWindowListener(new WindowAdapter() {
@Override
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});
ActionListen  actionListen = new ActionListen();
addListens(actionListen, add, min, mul, div, div1,div2,div3, clear, delete, equal,div4);
addListens(actionListen, btn0,btn1, btn2, btn3, btn4, btn5, btn6, btn7, btn8, btn9,btn10);


setVisible(true);
setBounds(100, 100, 350, 300);
setResizable(false);
}


private void addListens(ActionListen actionListen, Button ...arButtons) {
for (Button arButton : arButtons) {
arButton.addActionListener(actionListen);
}
}


private void addBtn(Panel panel, Button ...buttons) {


for (Button button : buttons) {
panel.add(button);
}
}


//事件监听
private class ActionListen implements ActionListener {


@Override
public void actionPerformed(ActionEvent e) {
String text = tx.getText();


text = setText(e, text, btn0, btn1, btn2, btn3, btn4, btn5, btn6,btn7,div4);
text = setText(e, text, btn8, btn9,btn10, add, min, mul, div,div1,div2,div3);


//计算表达式的结果
if (e.getSource() == equal) {
if (tx.getText() != null) {
String newString;
int i = text.lastIndexOf("=");
if (i > 0) {
newString=text.substring(text.lastIndexOf("=")+1);
}
else {
newString=text;
}
text += equal.getLabel();
tx.setText(text);


Double calculate = calculate(newString);
BigDecimal bdCalculate = new BigDecimal(String.valueOf(calculate));
BigDecimal bdResult= bdCalculate.setScale(4, RoundingMode.HALF_UP);
String sResult = bdResult.stripTrailingZeros().toPlainString();


text += sResult;
tx.setText(text);
}


}
//清零按钮
if (e.getSource() == clear) {
tx.setText("");
}
//删除按钮
if (e.getSource() == delete) {
String s = tx.getText();
if (s.length() > 0) {
tx.setText(s.substring(0, s.length() - 1));
}
}
}


private String setText(ActionEvent e, String text, Button ...buttons) {
for (Button button : buttons) {
if (e.getSource() == button) {
text += button.getLabel();
tx.setText(text);
}
}


return text;
}


}
}
}

效果图

前缀表达式前缀表达式也叫波兰表达式前缀表达式的运算符都位于操作数之前 (6+8)*5-2 -->前缀表达式：- * +6 8 5 2 思路：从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下: 从右至左扫描，将6、5、4、3压入堆栈遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈最后是-运算符，计算出35-6的值，即29，由此得出最终结果小结：反向扫描表达式，遇数字压人数字栈，遇运算符弹出栈顶和次栈顶两个数和此运算符进行计算结果入数字栈，扫描结束时，数字栈栈顶即为表达式的最终计算的结果实现

package DataStructure.Stack;


import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.List;
import java.util.Stack;


/**
* @author Jerssy
* @version V1.0
* @Description 前缀表达式(波兰表达式)
* @create 2021-02-20 11:29
*/
public class PrefixStack {


public static void main(String[] args) {
String PrefixString="- * + 3 4 5 6.5";


System.out.println("前缀表达式的值："+preFixCalculate(PrefixString));


System.out.println("原值"+((3+4)*5-6.5));
}


public  static  String  preFixCalculate(String string){
String newStr=string.replaceAll("\t|\r|\n*","");
Stack numberStack = new Stack<>();
List splitList = List.of(newStr.split("\\s"));


for(int j=splitList.size()-1;j>=0;j--){
if (splitList.get(j).matches("^[+-]?\\d+(\\.\\d+)?$")) {
numberStack.push(Double.valueOf(splitList.get(j)));
} else if (splitList.get(j).matches("^[+\\-*/%]$")) {
calculateNumber(numberStack, splitList.get(j));
}
}


BigDecimal bd1 = new BigDecimal(String.valueOf(numberStack.pop()));


return bd1.stripTrailingZeros().toPlainString();
}
public  static void  calculateNumber(Stack numberStack ,String str){
Double num1 = numberStack.pop();
Double num2 = numberStack.pop();


Double result = countMarked(str, num1, num2);
numberStack.push(result);


}


public static Double countMarked(String str, Double result2, Double result1){


Double aDouble2 = scaleResult(result2);
Double aDouble1 = scaleResult(result1);


return switch (str){
case "+"-> aDouble2+aDouble1;
case  "-"-> aDouble2-aDouble1;
case  "*"-> aDouble2*aDouble1;
case  "/"-> aDouble2/aDouble1;
case  "%"-> aDouble2%aDouble1;
case  "^"-> Math.pow(aDouble2,aDouble1);
default -> throw new IllegalStateException("Unexpected value: " + str);
};
}


private static Double scaleResult(Double result){
BigDecimal bd1 = new BigDecimal(String.valueOf(result));
BigDecimal bdResult= bd1.setScale(4, RoundingMode.HALF_UP);


return bdResult.doubleValue();


}
}

后缀表达式后缀表达式也叫逆波兰表达式与前缀表达式相似，只是运算符位于操作数之后例如：(6+8)*5-2 -->后缀表达式：6 8 + 5 * 2 - 其实现和前缀及其相似：从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下: 1 从左至右扫描，将3和4压入堆栈； 2 +运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈； 3 将5入栈； 4 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈； 5 将6入栈 6 最后是-运算符，计算出35-6的值，即29，由此得出最终结果小结：正向扫描表达式遇数字直接入数字栈，遇运算符，依次弹出数字栈栈顶两个数和此运算符进行计算，结果再次入数字栈，扫描结束时最后数字栈的栈顶即为表达式计算的最终结果。

package DataStructure.Stack;


import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.List;
import java.util.Stack;


/**
* @author Jerssy
* @version V1.0
* @Description 后缀表达式(逆波兰表达式)
* @create 2021-02-20 11:41
*/


//逆波兰表达式
public class SuffixStack {
public static void main(String[] args) {


String suffixString="1 2 348 + 6 4.1 * - + 5 -";


System.out.println("后缀表达式值:"+calculate(suffixString));


System.out.println("原值"+(1+((2+348)-6*4.1)-5));


}


public static String calculate(String suffixStr) {
String newStr=suffixStr.replaceAll("\t|\r|\n*","");
List splitList = List.of(newStr.split("\\s"));


Stack numberStack = new Stack<>();
for (String str : splitList) {
if (str.matches("^[+-]?\\d+(\\.\\d+)?$")) {
numberStack.push(Double.valueOf(str));
} else if (str.matches("^[+\\-*/%]$")) {
calculateNumber(numberStack, str);
}
}
BigDecimal bd1 = new BigDecimal(String.valueOf(numberStack.pop()));


return bd1.stripTrailingZeros().toPlainString();
}


public  static void  calculateNumber(Stack numberStack ,String str){
Double num1 = numberStack.pop();
Double num2 = numberStack.pop();


Double result = countMarked(str, num2, num1);
numberStack.push(result);


}


public static Double countMarked(String str, Double result2, Double result1){


Double aDouble2 = scaleResult(result2);
Double aDouble1 = scaleResult(result1);


return switch (str){
case "+"-> aDouble2+aDouble1;
case  "-"-> aDouble2-aDouble1;
case  "*"-> aDouble2*aDouble1;
case  "/"-> aDouble2/aDouble1;
case  "%"-> aDouble2%aDouble1;
case  "^"-> Math.pow(aDouble2,aDouble1);
default -> throw new IllegalStateException("Unexpected value: " + str);
};
}


private static Double scaleResult(Double result){
BigDecimal bd1 = new BigDecimal(String.valueOf(result));
BigDecimal bdResult= bd1.setScale(4, RoundingMode.HALF_UP);


return bdResult.doubleValue();


}


}

中缀转后缀思路：初始化运算符栈s1和储存中间结果的List s2；从左至右扫描中缀表达式；遇到操作数时，将其放入s2；遇到运算符时，比较其与s1栈顶运算符的优先级： 1 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；2 若优先级比栈顶运算符的高，也将运算符压入s1；否则，将s1栈顶的运算符弹出并放入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；遇到括号时：如果是左括号“(”，则直接压入s1如果是右括号“)”，则依次弹出s1栈顶的运算符，并放入s2，直到遇到左括号为止，此时将这一对括号丢弃重复步骤2至5，直到表达式的最右边将s1中剩余的运算符依次弹出并放入s2 s2中的元素并输出即为中缀表达式对应的后缀表达式小结：遇数字直接入中转s2 ,若s1为空或者栈顶为左括弧，或者当前扫描的优先级比s1栈顶优先级时高直接入s1栈，否则循环取出比栈顶优先级低的放入中转s2，遇到右括弧时，依次弹出s1栈顶元素放入s2，直到遇到左括弧为止并消除左括弧，最后若s1不为空则将s1剩余元素放入s2，输出s2即为对应的后缀表达式.

package DataStructure.Stack;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


/**
* @author Jerssy
* @version V1.0
* @Description 中缀表达式转后缀表达式
* @create 2021-02-22 11:36
*/
public class CenterToSuffix {


public static void main(String[] args) {
String str="1+((2+348)-6.3*4)-5";
String newStr=str.replaceAll("\\s*|\t|\r|\n","");
System.out.println("后缀表达式："+transformerStr(newStr));
}


private static  String transformerStr(String str){


List transferList= new ArrayList<>();
Stack operatorStack = new Stack<>();
StringBuilder builder= new StringBuilder();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (Character.isDigit(c)||c=='.'){//是数字--ASCI >=48 <=57
builder.append(c);
int lastLen = str.length()-1;
char nextChar= str.charAt(Math.min(i+1,lastLen));
if ((nextChar!='.'&&!Character.isDigit(nextChar)||i==lastLen)){//下一个字符不是数字或者到末尾了
transferList.add(builder.toString());
builder.delete(0,builder.length());
}
}
//是操作符
else if (isOperator(String.valueOf(c))) {
//若当前操作符优先级比栈顶运算符的低的放入transferList;
while (operatorStack.size()!=0&&!isHighPriority(c,operatorStack.peek())){
transferList.add(String.valueOf(operatorStack.pop()));
}
//其他情况(operatorStack为空，当前操作符优先级比栈顶高；栈顶运算符为左括号“(”)则压入operatorStack栈
operatorStack.push(c);
}


else if (c=='(') {
operatorStack.push(c);
}


else if (c==')') {


//如果是右括号“)”，则依次弹出operatorStack栈顶的运算符，并放入transferList，直到遇到左括号为止，此时将这一对括号丢弃
while (!operatorStack.isEmpty()&&operatorStack.peek()!='(') {
transferList.add(String.valueOf(operatorStack.pop()));
}
if (!operatorStack.isEmpty()) {
operatorStack.pop();//消除左括弧
}
}
}


while (!operatorStack.isEmpty()) {//将operatorStack中剩余的运算符依次弹出并放入transferList
transferList.add(String.valueOf(operatorStack.pop()));
}


return String.join(" ",transferList);
}


private static boolean isOperator(String str){


return  "+".equals(str)||"-".equals(str)||"*".equals(str)||"/".equals(str);
}


private static boolean isHighPriority(char operate1, char operate2) {


return getPriority(operate1) > getPriority(operate2);
}


private static int  getPriority(char option){
return switch (option) {
case '+', '-' -> 0;
case '*', '/','%' -> 1;
default -> -1;
};
}
}

相关文章