Java数据结构学习之栈和队列

什么是栈

栈（stack）是一种线性数据结构，它只能在一端进行插入和删除操作，这一端被称作栈顶（top）。栈的特点是先进后出（FILO，First-In-Last-Out），即最后进入的元素最先被删除。

栈的实现方式

栈可以使用数组或链表来实现。使用数组实现的栈称作顺序栈，使用链表实现的栈称作链式栈。以下是顺序栈的 Java 代码示例：

public class ArrayStack {
    private int[] stack; // 存储栈中元素的数组
    private int top; // 栈顶指针

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

    public void push(int element) {
        if (top == stack.length - 1) {
            throw new RuntimeException("Stack is full");
        }
        top++;
        stack[top] = element;
    }

    public int pop() {
        if (top == -1) {
            throw new RuntimeException("Stack is empty");
        }
        int element = stack[top];
        top--;
        return element;
    }

    public int size() {
        return top + 1;
    }
}

栈的应用举例

一种经典的栈的应用场景是括号匹配。例如，判断一个字符串中的括号是否匹配。可以使用栈来存储左括号，当遇到右括号时，弹出栈顶元素，如果与当前右括号不能匹配，则说明括号不匹配。

另一个栈的应用场景是后缀表达式求值。例如，计算后缀表达式 3 5 + 2 * 的值。这个表达式表示 (3 + 5) * 2，按照运算符的优先级计算，可以使用栈来存储数字，遇到操作符时弹出栈顶元素进行计算，再将结果压入栈中。

什么是队列

队列（queue）也是一种线性数据结构，它与栈类似，但是队列的插入和删除分别在两端进行，插入操作在队尾（rear）进行，删除操作在队头（front）进行。队列的特点是先进先出（FIFO，First-In-First-Out），即先进入的元素先被删除。

队列的实现方式

队列同样可以使用数组或链表来实现。使用数组实现的队列称作顺序队列，使用链表实现的队列称作链式队列。以下是链式队列的 Java 代码示例：

public class LinkedQueue {
    private class Node {
        int element;
        Node next;

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

    private Node front; // 队列头指针
    private Node rear; // 队列尾指针

    public LinkedQueue() {
        front = null;
        rear = null;
    }

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

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

    public int size() {
        int size = 0;
        Node curr = front;
        while (curr != null) {
            size++;
            curr = curr.next;
        }
        return size;
    }
}

队列的应用举例

队列的一个应用场景是生产者-消费者问题。例如，在一个多线程环境下，有一个队列用来存储任务，多个生产者线程往队列中插入任务，多个消费者线程从队列中取出任务进行处理。使用队列可以保证任务的顺序，避免竞争条件。

另一个队列的应用场景是广度优先搜索算法。例如，在一个迷宫问题中，需要寻找出口。可以把每个迷宫的单元格看做一个图中的节点，用队列来存储待处理的节点，按照距离逐层处理。这样可以保证找到的出口一定是离起点最近的出口。

总结

本文介绍了栈和队列两种线性数据结构，以及它们的实现方式和应用场景。栈和队列是编程中常用的基本数据结构，熟练掌握它们的使用可以提高编程效率和代码质量。