CodeGym /Java 博客 /China /Java 堆栈
作者
Milan Vucic
Programming Tutor at Codementor.io

Java 堆栈

已在 China 群组中发布
Java 中的堆栈通常指集合框架中实现 List 接口的类。他的工作原理基于堆栈数据结构,用于组织一种类型的内存。它也可能是内存中保存数据的部分,在本文中我们将首先关注 Stack 类,考虑它的方法并给出例子。但是我们也会谈到 Stack 这样的数据结构及其用途。

什么是堆栈数据结构?

首先,我们来快速了解一下什么是栈数据结构。这是一种基于后进先出 (LIFO) 原则的线性数据结构。有点反队列的意思。想象一副扑克牌或一叠书放在一个盒子里。你先放进堆栈的书在底部,我们第一个从盒子里拿出的是在顶部的书,也就是最后放进盒子的那本书。下面的一张 gif 图演示了这个原理。 Java 堆栈 - 1这是怎么回事?我们有一个一次只能打一个球的瓶子。瓶中的第一个是橙色球,然后是紫色球,最后是绿色球(我向准确知道这些颜色名称的人道歉)。然而,为了从我们的瓶堆栈中提取橙色球,我们需要首先取出最后到达那里的球(绿色球),然后取出倒数第二个球(但是在取出的时候它是最后一个)。 Java 或编程中其他地方的堆栈数据结构有两个最重要的操作,pushpop。push 操作将元素插入堆栈,pop 操作从堆栈顶部移除元素。

堆栈数据结构是干什么的?

堆栈最重要的用途之一是组织子程序调用。堆栈上的调用点存储子例程终止后的返回地址(可能还有传递的参数)。随着子例程的每次嵌套(包括递归)调用,新的返回地址被添加到堆栈中。随着子例程的每次返回操作 (return),返回地址将从堆栈中移除,控制权将转移给它。这个应用程序对编程如此重要,以至于在大多数处理器中,返回堆栈都是在指令集的硬件中实现的。然而,在其他情况下,堆栈必须在更常见的数据结构上建模。

集合框架的 Java Stack 类

在 Java Stack 类中是一个来自集合框架的类,该类实现了 List 接口,扩展了 Vector 类。它还实现了接口 Collection、Iterable、Cloneable、Serializable。正如你可能已经猜到的,这个类表示对象的 LIFO 堆栈。 下面是对 Stack 类的构造方法的调用,也就是创建这个类的对象。

Stack<E> stack = new Stack<E>();
其中 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 变量实际上包含了最后一个元素的下标,对对象的引用保留在数组中。所以这个实现需要一些改进。想想最简单的改进方法。 Java 堆栈 - 2

该不该用 Java 堆栈?

事实上,Java Stack 和它的 Vector 父类一样,是一个遗留类。相反,通常使用 ArrayList 类。Vector 同步时 ArrayList 不同步。这意味着 Vector 一次只有一个线程可以访问代码,而 ArrayList 可以处理多个线程。此外,ArrayList 效率更高也更快。所以你很可能只会在遗留代码中看到这个类。但是 Stack 数据结构在编程中使用得非常频繁。
评论
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION