疯狂数据结构-栈-Java
发布人:shili8
发布时间:2025-01-14 07:07
阅读次数:0
**疯狂数据结构 - 栈**
在计算机科学中,栈是一种基本的抽象数据类型(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 } }
**总结**
在本文中,我们介绍了栈的定义和操作,展示了 Java 中使用链表实现栈的例子。我们还提供了示例代码来演示栈的基本操作。