Java 数据结构教程

Java 数据结构 - 堆栈类

堆栈是一种抽象数据类型 (ADT)，在大多数编程语言中常用。它被称为堆栈，因为它表现得像现实世界中的堆栈，例如——一副扑克牌或一堆盘子等。

现实世界的堆栈只允许在一端进行操作。例如，我们只能在堆栈顶部放置或移除卡片或盘子。同样，堆栈 ADT 也只允许在一端进行所有数据操作。在任何给定时间，我们只能访问堆栈的顶部元素。

此功能使其成为后进先出 (LIFO) 数据结构。LIFO 代表后进先出。这里，最后放置（插入或添加）的元素首先被访问。在堆栈术语中，插入操作称为PUSH操作，删除操作称为POP操作。

堆栈表示

下图描述了一个堆栈及其操作：

堆栈可以通过数组、结构、指针和链表来实现。堆栈可以是固定大小的，也可以具有动态调整大小的功能。在这里，我们将使用数组来实现堆栈，这使得它成为一个固定大小的堆栈实现。

堆栈类

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

Stack 只定义了默认构造函数，它创建一个空堆栈。Stack 包括 Vector 定义的所有方法，并添加了一些它自己的方法。

Stack( )

除了从其父类 Vector 继承的方法外，Stack 还定义了以下方法：

序号	方法和描述
1	boolean empty() 测试此堆栈是否为空。如果堆栈为空，则返回 true；如果堆栈包含元素，则返回 false。
2	Object peek( ) 返回堆栈顶部的元素，但不将其移除。
3	Object pop( ) 返回堆栈顶部的元素，并在过程中将其移除。
4	Object push(Object element) 将元素压入堆栈。元素也会被返回。
5	int search(Object element) 在堆栈中搜索元素。如果找到，则返回其距堆栈顶部的偏移量。否则，返回 -1。

示例

以下程序演示了此集合支持的几种方法：

在线演示

import java.util.*;
public class StackDemo {
   static void showpush(Stack st, int a) {
      st.push(new Integer(a));
      System.out.println("push(" + a + ")");
      System.out.println("stack: " + st);
   }

   static void showpop(Stack st) {
      System.out.print("pop -> ");
      Integer a = (Integer) st.pop();
      System.out.println(a);
      System.out.println("stack: " + st);
   }

   public static void main(String args[]) {
      Stack st = new Stack();
      System.out.println("stack: " + st);
      showpush(st, 42);
      showpush(st, 66);
      showpush(st, 99);
      showpop(st);
      showpop(st);
      showpop(st);
      
      try {
         showpop(st);
      } catch (EmptyStackException e) {
         System.out.println("empty stack");
      }
   }
}

输出

stack: [ ]
push(42)
stack: [42]
push(66)
stack: [42, 66]
push(99)
stack: [42, 66, 99]
pop -> 99
stack: [42, 66]
pop -> 66
stack: [42]
pop -> 42
stack: [ ]
pop -> empty stack

打印页面