Java栈与队列怎么实现

在Java编程中，栈（Stack）和队列（Queue）是两种常见的数据结构，它们分别具有后进先出（Last In First Out，LIFO）和先进先出（First In First Out，FIFO）的特性。栈和队列在实际应用中有着广泛的用途，比如在算法、数据处理和多线程等场景下都能发挥重要作用。本文将介绍Java中栈和队列的实现方式，帮助您理解这两种数据结构的基本原理及应用。

1. Java栈的实现

栈是一种线性数据结构，它按照后进先出的原则管理数据。在Java中，可以使用数组或链表来实现栈。

1.1 数组实现栈

使用数组实现栈是最简单直观的方式之一。我们可以创建一个固定大小的数组，同时维护一个栈顶指针（top）来表示当前栈顶的位置。

public class ArrayStack {
    private int[] array;
    private int top;
    private int capacity;

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

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

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

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

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

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

1.2 链表实现栈

使用链表实现栈也是一种常见的方式，相比数组实现更具灵活性。我们可以定义一个链表节点类，并维护一个指向栈顶的指针。

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

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

    private Node top;

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

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

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

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

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

2. Java队列的实现

队列是一种线性数据结构，它按照先进先出的原则管理数据。在Java中，可以使用数组或链表来实现队列。

2.1 数组实现队列

使用数组实现队列时，需要维护一个前端指针（front）和一个后端指针（rear）。

public class ArrayQueue {
    private int[] array;
    private int front;
    private int rear;
    private int capacity;

    public ArrayQueue(int capacity) {
        this.array = new int[capacity];
        this.front = 0;
        this.rear = -1;
        this.capacity = capacity;
    }

    public void enqueue(int item) {
        if (rear == capacity - 1) {
            throw new RuntimeException("Queue is full.");
        }
        array[++rear] = item;
    }

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

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty.");
        }
        return array[front];
    }

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

    public int size() {
        return rear - front + 1;
    }
}

2.2 链表实现队列

使用链表实现队列时，只需维护一个前端指针（front）和一个后端指针（rear）即可。

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

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

    private Node front;
    private Node rear;

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

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

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

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

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

3. 栈与队列的应用

栈和队列在编程中有着广泛的应用。栈常用于实现递归算法、表达式求值、括号匹配和浏览器历史记录等场景。队列常用于实现广度优先搜索（BFS）、任务调度、消息队列和缓冲区管理等场景。

结论

栈和队列是两种常见的数据结构，在Java中可以用数组或链表来实现。栈的后进先出特性使其适用于某些算法和数据处理场景，而队列的先进先出特性则使其在其他场景下发挥重要作用。了解栈和队列的实现方式和应用场景，可以帮助我们在编程中更加灵活地运用这两种数据结构，提高程序的效率和可维护性。