Java 中的堆栈通常指集合框架中实现 List 接口的类。他的工作原理基于堆栈数据结构，用于组织一种类型的内存。它也可能是内存中保存数据的部分，在本文中我们将首先关注 Stack 类，考虑它的方法并给出例子。但是我们也会谈到 Stack 这样的数据结构及其用途。
![Java 堆栈 - 1]()
这是怎么回事？我们有一个一次只能打一个球的瓶子。瓶中的第一个是橙色球，然后是紫色球，最后是绿色球（我向准确知道这些颜色名称的人道歉）。然而，为了从我们的瓶堆栈中提取橙色球，我们需要首先取出最后到达那里的球（绿色球），然后取出倒数第二个球（但是在取出的时候它是最后一个）。
Java 或编程中其他地方的堆栈数据结构有两个最重要的操作，push 和 pop。push 操作将元素插入堆栈，pop 操作从堆栈顶部移除元素。
![Java 堆栈 - 2]()
什么是堆栈数据结构？
首先，我们来快速了解一下什么是栈数据结构。这是一种基于后进先出 (LIFO) 原则的线性数据结构。有点反队列的意思。想象一副扑克牌或一叠书放在一个盒子里。你先放进堆栈的书在底部，我们第一个从盒子里拿出的是在顶部的书，也就是最后放进盒子的那本书。下面的一张 gif 图演示了这个原理。
这是怎么回事？我们有一个一次只能打一个球的瓶子。瓶中的第一个是橙色球，然后是紫色球，最后是绿色球（我向准确知道这些颜色名称的人道歉）。然而，为了从我们的瓶堆栈中提取橙色球，我们需要首先取出最后到达那里的球（绿色球），然后取出倒数第二个球（但是在取出的时候它是最后一个）。
Java 或编程中其他地方的堆栈数据结构有两个最重要的操作，push 和 pop。push 操作将元素插入堆栈，pop 操作从堆栈顶部移除元素。
堆栈数据结构是干什么的？
堆栈最重要的用途之一是组织子程序调用。堆栈上的调用点存储子例程终止后的返回地址（可能还有传递的参数）。随着子例程的每次嵌套（包括递归）调用，新的返回地址被添加到堆栈中。随着子例程的每次返回操作 (return)，返回地址将从堆栈中移除，控制权将转移给它。这个应用程序对编程如此重要，以至于在大多数处理器中，返回堆栈都是在指令集的硬件中实现的。然而，在其他情况下，堆栈必须在更常见的数据结构上建模。集合框架的 Java Stack 类
在 Java Stack 类中是一个来自集合框架的类，该类实现了 List 接口，扩展了 Vector 类。它还实现了接口 Collection、Iterable、Cloneable、Serializable。正如你可能已经猜到的，这个类表示对象的 LIFO 堆栈。 下面是对 Stack 类的构造方法的调用，也就是创建这个类的对象。
Stack<E> stack = new Stack<E>();
Java 堆栈方法
这个类只有一个默认的构造方法和 Vector 类的所有方法。另外，Stack 自己提供 5 种方法：boolean empty() 该方法检查堆栈是否为空。如果堆栈为空，则返回 true，否则返回 false。
Object peek() 该方法返回位于堆栈顶部的元素。
Object pop() 该方法返回位于堆栈顶部的元素并将其移除。
Object push(Object element) 该方法将指定的元素添加到堆栈的顶部。
int search(Object element) 该方法在堆栈中搜索指定的元素。如果找到了所需的元素，则返回它与顶部的“距离”（序列号）。如果找不到元素，则返回 -1。
堆栈代码示例
让我们创建一个如上面的 gif 图片那样工作的程序示例。我们将在堆栈上放三个“球”，橙色、紫色和绿色。我们检查堆栈是否为空。然后，我们将从堆栈中取出球，直到堆栈为空。
import java.util.Stack;
public class myStackTest2 {
public static void main(String[] args)
{
Stack myStack= new Stack<>();
System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
myStack.push("Orange Ball");
myStack.push("Violet Ball");
myStack.push("Green Ball");
//prints elements of the stack
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
while (!myStack.isEmpty()) {
myStack.pop();
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
}
}
}
我的堆栈空了吗？true
堆栈中的元素：[橙色球, 紫色球, 绿色球]
我的堆栈空了吗？false
堆栈中的元素：[橙色球, 紫色球]
我的堆栈空了吗？false
堆栈中的元素：[橙色球]
我的堆栈空了吗？false
堆栈中的元素：[]
我的堆栈空了吗？true
因为 Stack 是从 Vector 类继承而来的，并且实现了 List 接口，所以 Stack 除了为此数据结构提供用于添加和提取元素的经典 push 和 pop 操作之外，还为 List 结构提供了标准的 add() 和 remove() 操作。在示例中，添加元素可以使用 add() 方法以同样的方式实现。但是，你只能在指定了元素的情况下使用 remove() 取出元素，这对堆栈数据结构没有意义。
import java.util.Stack;
public class myStackTest2 {
public static void main(String[] args)
{
Stack myStack= new Stack<>();
System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
myStack.add("Orange Ball");
myStack.add("Violet Ball");
myStack.add("Green Ball");
//prints elements of the stack
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
while (!myStack.isEmpty()) {
myStack.pop();
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
}
}
}
你自己的Stack 实现呢？
你可以使用数组或链表类在 Java 中创建自己的堆栈数据结构。在第一种情况下，一个连续的单元阵列分配后用来在存储器中存储值，这些值在需要时被使用。在第二种情况下，对于堆栈中的每个元素，都有一个内存块是有序的，足以存储值以及对堆栈中上一个和下一个元素的引用。基于数组的实现更简单、更高效、内存效率更高，但它需要事先了解堆栈大小限制，否则可能造成难以发现的错误。基于列表的实现更加健壮，但是效率较低。现在创建一个简单的基于数组的堆栈实现。该实现将包括函数。push — 确保添加元素（在顶部位置）的方法
pop — 提供元素移除（从顶部位置）的方法
readTop — 将返回位于顶部的元素的值的方法
sEmpty — 检查堆栈是否为空的方法
is full — 检查存储堆栈的数组是否已满的方法
import java.util.Arrays;
public class MyStack {
private int maxSize;
private String[] stackArray;
private int top;
public MyStack(int size) {
this.maxSize = size;
stackArray = new String[maxSize];
top = -1;
}
public String push (String element) {
return stackArray[++top] = element;
}
public String pop (String element) {
if (isEmpty())
{
System.out.println("Underflow\nProgram Terminated");
System.exit(-1);
}
System.out.println("Removing " + readTop());
return stackArray[top--];
}
public String readTop() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public void printStack(){
System.out.println(Arrays.toString(stackArray));
}
}
public class myStackTest {
public static void main(String[] args) {
MyStack myStack = new MyStack(3);
System.out.println("Is my stack empty? " + myStack.isEmpty());
myStack.push("Orange Ball");
myStack.push("Violet Ball");
myStack.push("Green Ball");
myStack.printStack();
System.out.println("Is my stack empty? " + myStack.isEmpty());
while (!myStack.isEmpty()) {
myStack.pop(myStack.readTop());
System.out.println("Is my stack empty? " + myStack.isEmpty());
}
}
}
我的堆栈空了吗？true
[橙色求, 紫色球, 绿色球]
我的堆栈空了吗？false
移除绿色球
我的堆栈空了吗？false
移除紫色球
我的堆栈空了吗？false
移除橙色求
我的堆栈空了吗？true
如果仔细观察，top 变量实际上包含了最后一个元素的下标，对对象的引用保留在数组中。所以这个实现需要一些改进。想想最简单的改进方法。
GO TO FULL VERSION