Java中实现栈数据结构的函数及其应用
栈（Stack）是一种数据结构，是一种线性结构，通常用数组或者链表来实现。栈也称为后进先出的数据结构（Last In First Out），顾名思义，就是最后进入栈的元素，最先退出栈。
Java中可以通过使用数组或者链表来实现栈数据结构。下面分别介绍实现栈数据结构的函数及其应用。
1. 数组实现栈
在 Java 中，我们可以使用数组来实现栈数据结构。具体实现方式如下：
class MyStack {
private int[] arr;
private int top;
public MyStack(int size) {
arr = new int[size];
top = -1;
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == arr.length - 1;
}
public void push(int x) {
if (isFull()) {
System.out.println("Stack Overflow");
return;
}
arr[++top] = x;
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow");
return -1;
}
return arr[top--];
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack Underflow");
return -1;
}
return arr[top];
}
}
其中，arr 是实现栈的数组，top 是栈顶指针。
使用栈，我们可以完成许多操作，例如在算术表达式中，使用栈可以实现中缀表达式转后缀表达式，以及后缀表达式求值等操作。
2. 链表实现栈
除了数组，我们还可以使用链表来实现栈数据结构。具体实现方式如下：
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
next = null;
}
}
class MyStack {
private Node head;
public MyStack() {
head = null;
}
public boolean isEmpty() {
return head == null;
}
public void push(int x) {
Node node = new Node(x);
if (head == null) {
head = node;
return;
}
node.next = head;
head = node;
}
public int pop() {
if (head == null) {
System.out.println("Stack Underflow");
return -1;
}
int data = head.data;
head = head.next;
return data;
}
public int peek() {
if (head == null) {
System.out.println("Stack Underflow");
return -1;
}
return head.data;
}
}
链表实现的栈相对于数组实现的栈来说，更加灵活，它可以随时增加、删除、插入元素，并且没有大小限制。
综上所述，栈是一种较为重要的数据结构，它在日常编程以及算法实现中具有广泛的应用，例如消除递归、表达式转换等。我们可以通过实现栈数据结构来完成各种对应用场景的操作。