疯狂数据结构-栈-Java

**疯狂数据结构 - 栈**

在计算机科学中，栈是一种基本的抽象数据类型（ADT），它遵循后进先出（LIFO）的原则。也就是说，在栈中最后添加的元素将首先被移除。

**栈的定义和操作**

栈可以看作一个垂直的线性表，顶部是栈顶，底部是栈底。栈中的元素遵循后进先出（LIFO）的原则，即在栈中最后添加的元素将首先被移除。

栈支持以下基本操作：

* **push（x）：** 将元素 x 添加到栈顶。
* **pop（）：** 移除栈顶元素，并返回该元素的值。如果栈为空，则抛出异常。
* **peek（）：** 返回栈顶元素的值，但不移除该元素。如果栈为空，则抛出异常。
* **isEmpty（）：** 检查栈是否为空。如果栈为空，则返回 true，否则返回 false。

**Java 中的栈实现**

在 Java 中，我们可以使用数组或链表来实现栈。这里我们将使用一个链表来实现栈。

javapublic class Stack {
 private Node top; // 栈顶元素 public Stack() {
 this.top = null;
 }

 // 添加元素到栈顶 public void push(int value) {
 Node newNode = new Node(value);
 if (top == null) {
 top = newNode;
 } else {
 newNode.next = top;
 top = newNode;
 }
 }

 // 移除栈顶元素并返回其值 public int pop() {
 if (isEmpty()) {
 throw new RuntimeException("Stack is empty");
 }
 int value = top.value;
 Node temp = top;
 top = top.next;
 temp.next = null; //释放内存 return value;
 }

 // 返回栈顶元素的值，但不移除该元素 public int peek() {
 if (isEmpty()) {
 throw new RuntimeException("Stack is empty");
 }
 return top.value;
 }

 // 检查栈是否为空 public boolean isEmpty() {
 return top == null;
 }

 private static class Node {
 int value; // 元素值 Node next; // 下一个元素 public Node(int value) {
 this.value = value;
 this.next = null;
 }
 }
}

javapublic class Main {
 public static void main(String[] args) {
 Stack stack = new Stack();

 // 添加元素到栈顶 stack.push(1);
 stack.push(2);
 stack.push(3);

 System.out.println("Stack size: " + (stack.isEmpty() ?0 : stack.top.value)); // 输出：3 // 移除栈顶元素并返回其值 int value = stack.pop();
 System.out.println("Popped element: " + value); // 输出：3 System.out.println("Stack size: " + (stack.isEmpty() ?0 : stack.top.value)); // 输出：2 // 返回栈顶元素的值，但不移除该元素 int peekValue = stack.peek();
 System.out.println("Peeked element: " + peekValue); // 输出：2 System.out.println("Stack size: " + (stack.isEmpty() ?0 : stack.top.value)); // 输出：2 }
}