java数据结构与算法之栈（Stack）设计与实现

栈（Stack）是一种常见的数据结构，它是一种只允许在一端进行插入和删除操作的线性表，这一端被称为栈顶。栈的特点是后进先出（Last-In-First-Out，简称 LIFO），即最后压入栈的元素最先弹出。

在 Java 中，可以使用数组或链表来实现栈。下面分别介绍数组和链表实现栈的方法。

1. 数组实现栈

数组实现栈时，需要定义一个数组和一个指针 top，top 指向栈顶。栈中的元素从数组的末尾开始存储，每当有一个元素入栈时，top 指针加 1；每当有一个元素出栈时，top 指针减 1。

以下是一个基于数组实现的栈的示例代码：

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 指针指向原来的头节点；每当有一个元素出栈时，头节点指针向下移动一个位置。

以下是一个基于链表实现的栈的示例代码：

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;
        }
    }
}

以上是两种常见的栈的实现方法，它们在效率和空间占用上略有差别，具体实现应根据具体情况选择。