Java函数实现栈和队列数据结构的详细介绍和应用示例

栈和队列是两种常用的数据结构，它们分别用于解决不同的问题。本文将详细介绍Java中栈和队列的功能及其实现方法，并给出一些应用示例。

栈是一种后进先出（Last-In-First-Out，简称LIFO）的数据结构，类似于我们日常生活中的栈。在Java中，可以使用数组或者链表来实现栈。

数组实现栈：

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

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
        top = -1;
    }

    public void push(int value) {
        if (top == maxSize - 1) {
            throw new StackOverflowError("Stack is full");
        }
        stack[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return stack[top];
    }

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

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

链表实现栈：

public class LinkedListStack {
    private Node top;

    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 EmptyStackException();
        }
        int value = top.value;
        top = top.next;
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.value;
    }

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

    private static class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }
    }
}

栈的应用示例：

1. 表达式求值：将中缀表达式转换为后缀表达式，并利用栈进行计算。

2. 括号匹配：利用栈判断括号是否匹配。

队列是一种先进先出（First-In-First-Out，简称FIFO）的数据结构，类似于我们日常生活中的排队。在Java中，可以使用数组或者链表来实现队列。

数组实现队列：

public class ArrayQueue {
    private int maxSize;
    private int[] queue;
    private int front;
    private int rear;

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        queue = new int[maxSize];
        front = -1;
        rear = -1;
    }

    public void enqueue(int value) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        queue[++rear] = value;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return queue[++front];
    }

    public int peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return queue[front + 1];
    }

    public boolean isEmpty() {
        return front == rear;
    }

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

链表实现队列：

public class LinkedListQueue {
    private Node front;
    private Node rear;

    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        int value = front.value;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return front.value;
    }

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

    private static class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }
    }
}

队列的应用示例：

1. 广度优先搜索（BFS）：在图或树中使用队列来实现BFS算法。

2. 算法调度：使用队列按顺序执行多个任务。

通过以上的介绍和示例，我们可以看到栈和队列的使用场景和优势。在实际的应用开发中，栈和队列是非常有用的数据结构，通过合理地利用栈和队列，可以更好地解决问题。