数据结构——队列和栈（介绍、类型、Java手搓实现循环队列）

我是一个计算机专业研0的学生卡蒙Camel🐫🐫🐫（刚保研）
记录每天学习过程（主要学习Java、python、人工智能），总结知识点（内容来自：自我总结+网上借鉴）
希望大家能一起发现问题和补充，也欢迎讨论👏👏👏

队列

队列介绍

队列（Queue）是一种遵循先进先出原则（FIFO, First In First Out）的数据结构（可以用数组或者链表实现），意味着最早添加到队列中的元素将是最先被移除的。这种特性使得队列在很多场景中非常有用，例如任务调度、缓冲处理等。

访问：O（n）//最坏情况
插入删除：O（1）//后端插入前端删除元素

队列类型

使用数组实现举例：

1. 线性队列(Linear Queue)

最简单的队列形式，具有固定的前端和后端。

2. 循环队列(Circular Queue)

一种优化后的线性队列，其中最后一个位置连接到第一个位置，形成环形结构，从而更高效地利用存储空间。

3. 优先队列(Priority Queue)

队列中的每个元素都有一个关联的优先级，出队时总是移除具有最高优先级的元素（一般使用堆实现）。Java 中提供了 PriorityQueue 类来实现这一功能。

4. 双端队列(Deque, Double-ended Queue)

允许在两端进行插入和删除操作，既可以在前端也可以在后端执行入队和出队操作。Java 提供了 Deque 接口以及它的多个实现类如 ArrayDeque 和 LinkedList。

自定义循环队列Java代码手搓实现🖊️

/**
 * @author:Camel
 * @date:2025/1/17
 * @description:循环队列
 */
public class CircularQueue<T> {
    private T[] elements; // 存储队列元素的数组
    private int front;    // 队首指针
    private int rear;     // 队尾指针
    private int capacity; // 队列的最大容量
    private int count;    // 当前队列中的元素数量

    // 构造函数初始化
    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.front = 0;
        this.rear = -1;
        this.count = 0;
        this.elements = (T[]) new Object[capacity];
    }

    // 入队操作
    public boolean enqueue(T element) {
        if (isFull()) {
            return false; // 队列已满
        }
        rear = (rear + 1) % capacity;
        elements[rear] = element;
        count++;
        return true;
    }

    // 出队操作
    public T dequeue() {
        if (isEmpty()) {
            return null; // 队列为空
        }
        T item = elements[front];
        elements[front] = null; // 可选：帮助垃圾回收
        front = (front + 1) % capacity;
        count--;
        return item;
    }

    // 查看队首元素
    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return elements[front];
    }

    // 检查队列是否为空
    public boolean isEmpty() {
        return count == 0;
    }

    // 检查队列是否已满
    public boolean isFull() {
        return count == capacity;
    }

    // 获取队列大小
    public int size() {
        return count;
    }

    // 打印队列内容
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        for (int i = 0, index = front; i < count; i++, index = (index + 1) % capacity) {
            System.out.print(elements[index] + " ");
        }
        System.out.println();
    }
}

Java中的Queue

Queue接口：

栈介绍

栈和队列相似，只不过栈按照 后进先出（LIFO, Last In First Out） 的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。

栈常用一维数组或链表来实现，用数组实现的栈叫作 顺序栈 ，用链表实现的栈叫作 链式栈 。