Java教程-Java 栈

Java 栈

栈是一种线性数据结构，用于存储对象的集合。它基于后进先出（LIFO）的原则。Java集合框架提供了许多接口和类来存储对象的集合，其中之一就是Stack类，它提供了push、pop、search等不同的操作。

在本节中，我们将讨论Java的Stack类、其方法，并在Java程序中实现栈数据结构。但在深入了解Java的Stack类之前，让我们快速了解一下栈的工作原理。

栈数据结构有两个最重要的操作，即push和pop。push操作将一个元素插入栈中，而pop操作从栈的顶部移除一个元素。让我们看看它们在栈上是如何工作的。

让我们依次将20、13、89、90、11、45、18推入栈中。

让我们从栈中移除（pop）18、45和11。

空栈： 如果栈中没有元素，则称为空栈。当栈为空时，top变量的值为-1。

当我们将一个元素推入栈时，top的值增加1。在下图中，

• 推入12，top=0
• 推入6，top=1
• 推入9，top=2

当我们从栈中弹出一个元素时，top的值减少1。在下图中，我们弹出了9。

下表显示了top的不同值。

Java Stack类

在Java中，Stack是一个属于Collection框架的类，它扩展了Vector类。它还实现了接口List, Collection, Iterable, Cloneable, Serializable。它表示对象的LIFO（后进先出）栈。在使用Stack类之前，我们必须导入java.util包。Stack类在Collections框架层次结构中排列如下。

Stack类的构造函数

Stack类只包含一个默认构造函数，用于创建一个空栈。

public Stack()

创建栈

如果我们想创建一个栈，首先需要导入java.util包，并创建一个Stack类的对象。

Stack stk = new Stack();

或者

Stack<type> stk = new Stack<>();

其中type表示栈的类型，如Integer、String等。

Stack类的方法

我们可以对栈执行push、pop、peek和search操作。Java的Stack类主要提供了五个方法来执行这些操作。除此之外，它还提供了Java Vector类的所有方法。

方法	修饰符和类型	方法描述
empty()	boolean	该方法检查栈是否为空。
push(E item)	E	该方法将元素推入（插入）栈的顶部。
pop()	E	该方法从栈的顶部移除一个元素，并将该元素作为该函数的返回值返回。
peek()	E	该方法查看栈的顶部元素，但不将其移除。
search(Object o)	int	该方法搜索指定的对象，并返回对象的位置。

Stack类的empty()方法

Stack类的empty()方法检查栈是否为空。如果栈为空，返回true；否则返回false。我们也可以使用Vector类的isEmpty()方法。

语法

public boolean empty()

返回值：如果栈为空，则返回true；否则返回false。

在下面的示例中，我们创建了Stack类的一个实例。然后，我们调用了empty()方法两次。第一次它返回true，因为我们还没有将任何元素推入栈中。然后，我们将元素推入栈中。再次调用empty()方法，它返回false，因为栈不为空。

StackEmptyMethodExample.java

import java.util.Stack; 
public class StackEmptyMethodExample {
   public static void main(String[] args) {
      // 创建一个Stack类的实例
      Stack<Integer> stk= new Stack<>();
      // 检查栈是否为空
      boolean result = stk.empty();
      System.out.println("Is the stack empty? " + result);
      // 将元素推入栈中
      stk.push(78);
      stk.push(113);
      stk.push(90);
      stk.push(120);
      // 打印栈中的元素
      System.out.println("Elements in Stack: " + stk);
      result = stk.empty();
      System.out.println("Is the stack empty? " + result);
   }
}

输出:

Is the stack empty? true
Elements in Stack: [78, 113, 90, 120]
Is the stack empty? false

Stack类的push()方法

该方法将一个元素插入到栈的顶部。它的工作方式与Vector类的addElement(item)方法相同。它接受一个参数item，将其推入栈中。

语法

public E push(E item)

参数：要推入栈顶的元素。

返回值：该方法返回我们作为参数传递的参数。

Stack类的pop()方法

该方法从栈的顶部移除一个对象，并返回该对象。如果栈为空，它会抛出EmptyStackException异常。

语法

public E pop()

返回值：返回栈顶的对象。

让我们在一个Java程序中实现栈，并执行push和pop操作。

StackPushPopExample.java

import java.util.*;
public class StackPushPopExample {
   public static void main(String args[]) {
      // 创建一个Stack类的对象
      Stack<Integer> stk = new Stack<>();
      System.out.println("stack: " + stk);
      // 将元素推入栈中
      pushelmnt(stk, 20);
      pushelmnt(stk, 13);
      pushelmnt(stk, 89);
      pushelmnt(stk, 90);
      pushelmnt(stk, 11);
      pushelmnt(stk, 45);
      pushelmnt(stk, 18);
      // 从栈中弹出元素
      popelmnt(stk);
      popelmnt(stk);
      // 如果栈为空，则抛出异常
      try {
         popelmnt(stk);
      } catch (EmptyStackException e) {
         System.out.println("empty stack");
      }
   }
   // 执行push操作
   static void pushelmnt(Stack stk, int x) {
      // 调用push()方法
      stk.push(new Integer(x));
      System.out.println("push -> " + x);
      // 打印修改后的栈
      System.out.println("stack: " + stk);
   }
   // 执行pop操作
   static void popelmnt(Stack stk) {
      System.out.print("pop -> ");
      // 调用pop()方法
      Integer x = (Integer) stk.pop();
      System.out.println(x);
      // 打印修改后的栈
      System.out.println("stack: " + stk);
   }
}

输出:

stack: []
push -> 20
stack: [20]
push -> 13
stack: [20, 13]
push -> 89
stack: [20, 13, 89]
push -> 90
stack: [20, 13, 89, 90]
push -> 11
stack: [20, 13, 89, 90, 11]
push -> 45
stack: [20, 13, 89, 90, 11, 45]
push -> 18
stack: [20, 13, 89, 90, 11, 45, 18]
pop -> 18
stack: [20, 13, 89, 90, 11, 45]
pop -> 45
stack: [20, 13, 89, 90, 11]
pop -> 11
stack: [20, 13, 89, 90]

Stack类的peek()方法

该方法查看栈顶的元素。如果栈为空，它也会抛出EmptyStackException异常。

语法

public E peek()

返回值：返回栈顶的元素。

让我们看一个peek()方法的例子。

StackPeekMethodExample.java

import java.util.Stack;
public class StackPeekMethodExample {
   public static void main(String[] args) {
      Stack<String> stk = new Stack<>();
      // 将元素推入栈中
      stk.push("Apple");
      stk.push("Grapes");
      stk.push("Mango");
      stk.push("Orange");
      System.out.println("Stack: " + stk);
      // 访问栈顶的元素
      String fruits = stk.peek();
      // 打印栈
      System.out.println("Element at top: " + fruits);
   }
}

输出:

Stack: [Apple, Grapes, Mango, Orange]
栈顶的元素: Orange

Stack类的search()方法

该方法从栈的顶部开始搜索对象。它解析一个我们要搜索的参数，并返回对象在栈中的基于1的位置。栈的最顶部对象被认为是距离为1的位置。

假设o是栈中要搜索的对象。该方法返回离栈顶最近的出现位置距离栈顶的距离。它使用equals()方法在栈中搜索对象。

语法

public int search(Object o)

参数：o是要搜索的目标对象。

返回值：返回对象在栈中距离栈顶的位置。如果返回-1，则表示对象不在栈中。

让我们看一个search()方法的例子。

StackSearchMethodExample.java

import java.util.Stack;
public class StackSearchMethodExample {
   public static void main(String[] args) {
      Stack<String> stk = new Stack<>();
      // 将元素推入栈中
      stk.push("Mac Book");
      stk.push("HP");
      stk.push("DELL");
      stk.push("Asus");
      System.out.println("Stack: " + stk);
      // 搜索一个元素
      int location = stk.search("HP");
      System.out.println("Location of Dell: " + location);
   }
}

使用Iterator()方法

这是Iterator接口的方法。它返回一个迭代器，用于遍历栈中的元素。在使用iterator()方法之前，需要导入java.util.Iterator包。

语法

Iterator<T> iterator()

让我们对栈进行迭代。

StackIterationExample1.java

import java.util.Iterator;
import java.util.Stack;
public class StackIterationExample1 {
   public static void main(String[] args) {
      // 创建Stack类的对象
      Stack stk = new Stack();
      // 将元素推入栈中
      stk.push("BMW");
      stk.push("Audi");
      stk.push("Ferrari");
      stk.push("Bugatti");
      stk.push("Jaguar");
      // 对栈进行迭代
      Iterator iterator = stk.iterator();
      while (iterator.hasNext()) {
         Object values = iterator.next();
         System.out.println(values);
      }
   }
}

输出:

BMW
Audi
Ferrari
Bugatti
Jaguar

使用forEach()方法

Java提供了一个forEach()方法来遍历元素。该方法定义在Iterable和Stream接口中。

语法

default void forEach(Consumer<? super T> action)

让我们使用forEach()方法对栈进行迭代。

StackIterationExample2.java

import java.util.*;
public class StackIterationExample2 {
   public static void main(String[] args) {
      // 创建Stack类的实例
      Stack<Integer> stk = new Stack<>();
      // 将元素推入栈中
      stk.push(119);
      stk.push(203);
      stk.push(988);
      System.out.println("使用forEach()方法对栈进行迭代:");
      // 使用forEach()方法对栈进行迭代
      stk.forEach(n -> {
         System.out.println(n);
      });
   }
}

输出:

使用forEach()方法对栈进行迭代:
119
203
988

使用listIterator()方法

该方法返回一个列表迭代器，用于从列表中的指定位置（按顺序）开始迭代元素。它从栈的顶部向下迭代。

语法

ListIterator<E> listIterator(int index)

参数：*该方法解析一个名为*index的参数。

返回值：该方法返回一个按顺序的列表迭代器。

异常：*如果索引超出范围，则会抛出*IndexOutOfBoundsException。

让我们使用listIterator()方法对栈进行迭代。

StackIterationExample3.java

import java.util.Iterator;
import java.util.ListIterator;
import java.util.Stack;

public class StackIterationExample3 {
   public static void main(String[] args) {
      Stack<Integer> stk = new Stack<>();
      stk.push(119);
      stk.push(203);
      stk.push(988);
      ListIterator<Integer> listIterator = stk.listIterator(stk.size());
      System.out.println("从顶部到底部迭代栈：");
      while (listIterator.hasPrevious()) {
         Integer avg = listIterator.previous();
         System.out.println(avg);
      }
   }
}

输出:

Iteration over the Stack from top to bottom:
988
203
119