java如何实现栈

栈的基本概念

栈是一种遵循后进先出（LIFO）原则的线性数据结构。主要操作包括压栈（push）、弹栈（pop）、查看栈顶元素（peek）以及判断栈是否为空。

使用数组实现栈

数组实现栈简单直观，适合固定大小的栈需求。初始化时需要指定栈的容量。

public class ArrayStack {
    private int maxSize;
    private int[] stackArray;
    private int top;

    public ArrayStack(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1;
    }

    public void push(int value) {
        if (isFull()) {
            throw new RuntimeException("Stack is full");
        }
        stackArray[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stackArray[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stackArray[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }
}

使用链表实现栈

链表实现的栈动态灵活，无需预先指定大小。每个节点包含数据和指向下一个节点的引用。

public class LinkedStack {
    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    private Node top;

    public void push(int value) {
        Node newNode = new Node(value);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        int value = top.data;
        top = top.next;
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
}

使用Java集合框架实现栈

Java的Deque接口及其实现类（如ArrayDeque）提供了高效的栈操作，推荐替代传统的Stack类。

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeStack {
    private Deque<Integer> stack = new ArrayDeque<>();

    public void push(int value) {
        stack.push(value);
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack.pop();
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}

线程安全的栈实现

多线程环境下可使用ConcurrentLinkedDeque或同步包装器保证线程安全。

import java.util.Collections;
import java.util.Stack;

public class SynchronizedStack {
    private Stack<Integer> stack = new Stack<>();

    public synchronized void push(int value) {
        stack.push(value);
    }

    public synchronized int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack.pop();
    }

    public synchronized int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack.peek();
    }

    public synchronized boolean isEmpty() {
        return stack.isEmpty();
    }
}

泛型栈实现

通过泛型可增强栈的通用性，支持多种数据类型。

public class GenericStack<T> {
    private static class Node<T> {
        T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    private Node<T> top;

    public void push(T value) {
        Node<T> newNode = new Node<>(value);
        newNode.next = top;
        top = newNode;
    }

    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        T value = top.data;
        top = top.next;
        return value;
    }

    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
}