Java 数据结构之栈与队列

什么是栈？

栈是一种根据先进后出（LIFO）原则的数据结构，即最后压入的元素最先弹出。栈可以用数组或链表实现。栈的两个基本操作是 push（入栈）和 pop（出栈）。

栈的特性

1. 只允许在栈的顶部插入和删除元素。

2. 操作受限只能从一端进行。

3. 元素的插入和删除时间复杂度都为 O(1)。

栈的示例

以下是使用 Java 语言实现栈的示例代码：

public class Stack {
    private int top;
    private int[] data;

    public Stack(int size) {
        data = new int[size];
        top = -1;
    }

    public void push(int item) {
        if (top >= data.length - 1) {
            throw new StackOverflowError();
        }
        data[++top] = item;
    }

    public int pop() {
        if (top < 0) {
            throw new EmptyStackException();
        }
        return data[top--];
    }

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

    public boolean isFull() {
        return top == data.length - 1;
    }
}

什么是队列？

队列是一种根据先进先出（FIFO）原则的数据结构，即最先进入的元素最先弹出。队列可以用数组或链表实现。队列的两个基本操作是 enqueue（入队）和 dequeue（出队）。

队列的特性

1. 只允许在队列的一端插入元素，在另一端删除元素。

2. 操作受限只能从两端进行。

3. 元素的插入和删除时间复杂度都为 O(1)。

队列的示例

以下是使用Java 语言实现队列的示例代码：

public class Queue {
    private int[] data;
    private int front;
    private int rear;
    private int size;

    public Queue(int size) {
        this.size = size;
        data = new int[size];
        front = -1;
        rear = -1;
    }

    public void enqueue(int item) {
        if (isFull()) {
            throw new RuntimeException("Queue is full.");
        }
        if (isEmpty()) {
            front = 0;
        }
        data[++rear] = item;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty.");
        }
        int item = data[front];
        if (front == rear) {
            front = -1;
            rear = -1;
        } else {
            front++;
        }
        return item;
    }

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

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

如何选择栈或队列？

栈和队列是基本的数据结构，有着不同的特点和适用场景。在选择使用栈或队列时，需要根据具体的问题需求而定。

1. 当需要实现”后进先出“时，优先考虑使用栈。

2. 当需要实现”先进先出“时，优先考虑使用队列。

3. 当需要实现某功能时，如果既可使用栈，又可使用队列，则可以综合考虑其时间复杂度、空间复杂度、代码的易读性等因素，选择更合适的数据结构。

栈和队列的应用

1. 栈的应用：函数调用的存储管理、表达式转换与求值、计算机内存中的操作系统堆栈、迭代计算、浏览器中的历史记录等。

2. 队列的应用：缓存队列、进程调度等。

总结

本文介绍了 Java 数据结构中的栈和队列。栈和队列是常用的基本数据结构，在编写计算机程序时得到广泛的应用和实践。理解栈和队列的特性及实现方式，可以帮助理清计算机程序的逻辑结构，提高编程能力和实践能力。