一、栈的简介
栈是一种非常常用的数据结构，它是一种线性结构，具有后进先出（LIFO）的性质，即最后入栈的元素最先出栈。栈通常只允许在栈顶进行插入和删除操作，其它位置均不可访问。
在Java中，栈通常指的是调用栈（call stack），是用来保存函数调用状态的内存区域。在函数调用时，每一个函数都会在栈上开辟一块用于保存该函数的局部变量、参数、返回地址等信息，函数返回时再将对应的信息出栈，使得程序可以回到函数被调用的位置。
二、栈的应用场景
栈作为一种常用的数据结构，在许多场景下都有应用。以下是一些典型的栈的应用场景：
1. 表达式求值
在计算机中，算术表达式往往是以中缀表达式的形式出现的，而计算时往往需要将其转化为后缀表达式，然后通过栈来计算。具体的实现方式是，遍历中缀表达式并依次将各个元素入栈，当遇到操作符时，将前面两个元素出栈，计算后的结果再入栈。最后栈中剩下的元素即为计算后的结果。
2. 括号匹配
在编程中，经常需要判断一个字符串中的括号是否匹配。此时可以利用栈的后进先出的特性，将遇到的左括号依次入栈，遇到右括号时如果栈顶是对应的左括号则弹出，否则说明括号不匹配。
3. 浏览器的前进和后退
当用户在浏览器中访问不同的页面时，浏览器会将每个页面的URL保存在一个历史记录栈中。当用户点击后退按钮时，浏览器将从栈顶弹出一个URL并加载该页面，当用户点击前进按钮时，则将栈顶的URL入栈并打开对应的页面。
/**
* 表达式求值
*
* @param exp 中缀表达式数组
* @return 表达式的计算结果
*/
public static int evaluateExpression(String[] exp) {
Stack stack = new Stack();
for (String s : exp) {
if (isNumber(s)) {
stack.push(Integer.parseInt(s));
} else {
int x = stack.pop();
int y = stack.pop();
switch (s) {
case "+":
stack.push(y + x);
break;
case "-":
stack.push(y - x);
break;
case "*":
stack.push(y * x);
break;
case "/":
stack.push(y / x);
break;
}
}
}
return stack.pop();
}
/**
* 判断字符串是否为数字
*/
private static boolean isNumber(String s) {
try {
Integer.parseInt(s);
return true;
} catch (NumberFormatException e) {
return false;
}
}
三、栈的实现
Java中的栈可以通过继承Vector（或ArrayList）来实现，也可以通过构造一个由数组支持的小容量的堆栈来实现。以下是一个基于链表的栈的实现示例：
/**
* 基于链表的栈的实现
*
* @param 栈中元素的类型
*/
public class LinkedStack<T> {
private Node<T> top; // 栈顶节点
// 入栈操作
public void push(T data) {
Node<T> newNode = new Node<>(data);
newNode.next = top;
top = newNode;
}
// 出栈操作
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
T data = top.data;
top = top.next;
return data;
}
// 获取栈顶元素
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return top.data;
}
// 判断栈是否为空
public boolean isEmpty() {
return top == null;
}
// 栈中节点定义
private static class Node<T> {
T data; // 节点数据
Node<T> next; // 指向下一个节点的引用
Node(T data) {
this.data = data;
}
}
}
原创文章，作者：XJNYZ，如若转载，请注明出处：https://www.506064.com/n/325108.html
微信扫一扫 
支付宝扫一扫 