JS算法探险之栈(Stack)

栈（Stack）是一种常见的数据结构，它是一种只允许在一端进行插入和删除操作的线性表，这一端被称为栈顶。栈的特点是后进先出（Last-In-First-Out，简称 LIFO），即最后压入栈的元素最先弹出。 在 Java 中，可以使用数组或链表来实现栈。下面分别介绍数组和链表实现栈的方法。 1. 数组实现栈 数组实现栈时，需要定义一个数组和一个指针 top，top 指向栈顶。栈中的元素从数组的末尾开始存储，每当有一个元素入栈时，top 指针加 1；每当有一个元素出栈时，top 指针减 1。 以下是一个基于数组实现的栈的示例代码： ```java public class ArrayStack { private int[] stack; // 栈数组 private int top; // 栈顶指针 public ArrayStack(int size) { stack = new int[size]; top = -1; // 初始化栈顶指针为 -1 } // 判断栈是否为空 public boolean isEmpty() { return top == -1; } // 判断栈是否已满 public boolean isFull() { return top == stack.length - 1; } // 入栈 public void push(int data) { if (isFull()) { System.out.println("栈已满，无法入栈。"); return; } stack[++top] = data; } // 出栈 public int pop() { if (isEmpty()) { System.out.println("栈为空，无法出栈。"); return -1; } return stack[top--]; } // 获取栈顶元素 public int peek() { if (isEmpty()) { System.out.println("栈为空，无法获取栈顶元素。"); return -1; } return stack[top]; } } ``` 2. 链表实现栈 链表实现栈时，需要定义一个链表头节点和一个指针 top，top 指向栈顶。每当有一个元素入栈时，该元素成为新的头节点，其 next 指针指向原来的头节点；每当有一个元素出栈时，头节点指针向下移动一个位置。 以下是一个基于链表实现的栈的示例代码： ```java public class LinkedStack { private Node top; // 栈顶指针 public LinkedStack() { top = null; // 初始化栈顶指针为 null } // 判断栈是否为空 public boolean isEmpty() { return top == null; } // 入栈 public void push(int data) { Node newNode = new Node(data); newNode.next = top; top = newNode; } // 出栈 public int pop() { if (isEmpty()) { System.out.println("栈为空，无法出栈。"); return -1; } int data = top.data; top = top.next; return data; } // 获取栈顶元素 public int peek() { if (isEmpty()) { System.out.println("栈为空，无法获取栈顶元素。"); return -1; } return top.data; } private class Node { private int data; private Node next; public Node(int data) { this.data = data; this.next = null; } } } ``` 以上是两种常见的栈的实现方法，它们在效率和空间占用上略有差别，具体实现应根据具体情况选择。