数据结构第07节:队列

在计算机科学中,队列是一种抽象数据类型,它遵循先进先出(FIFO)原则,即最先加入队列的元素将是最先被移除的。队列可以用来管理一系列等待处理的任务,例如打印任务队列、任务调度等。在学生成绩管理系统中,队列可以用于管理等待处理的成绩更新请求,或者用于存储等待查询成绩的学生ID列表。

下面,我将以一个简单的学生成绩管理系统中的队列应用为例,用表格形式来详细讲解队列的操作和状态变化。

操作 描述 队列状态
初始化 创建一个空队列 []
入队 (enqueue) 将学生ID添加到队列尾部,例如学生ID: 1001 [1001]
入队 (enqueue) 将学生ID添加到队列尾部,例如学生ID: 1002 [1001, 1002]
入队 (enqueue) 将学生ID添加到队列尾部,例如学生ID: 1003 [1001, 1002, 1003]
出队 (dequeue) 移除并返回队列头部的学生ID 1001
队列状态 移除后队列的状态 [1002, 1003]
出队 (dequeue) 移除并返回队列头部的学生ID 1002
队列状态 移除后队列的状态 [1003]
入队 (enqueue) 将学生ID添加到队列尾部,例如学生ID: 1004 [1003, 1004]
出队 (dequeue) 移除并返回队列头部的学生ID 1003
队列状态 移除后队列的状态 [1004]

通过上述操作,我们可以看到队列是如何按照先进先出的原则进行操作的。当学生ID入队时,它们被添加到队列的末尾;而出队时,总是从队列的头部移除元素,确保最先加入的ID最先被处理。这种机制对于需要按顺序处理多个请求或任务的场景非常有用。

下面是一个使用Java实现的简单队列(基于数组)。这个队列将用于管理学生的ID,模拟学生成绩管理系统中可能用到的队列操作。

public class StudentQueue {
    private int maxSize; // 队列最大容量
    private int front; // 队头
    private int rear; // 队尾
    private int[] queueArray; // 存储队列元素的数组
    private int nItems; // 当前队列中的元素数量

    public StudentQueue(int size) {
        maxSize = size;
        front = 0;
        rear = -1;
        queueArray = new int[maxSize];
        nItems = 0;
    }

    // 入队操作
    public void enqueue(int studentId) {
        if (rear == maxSize - 1) { // 检查队列是否已满
            System.out.println("Queue is full.");
            return;
        }
        rear++; // 移动队尾指针
        queueArray[rear] = studentId; // 在队尾添加元素
        nItems++;
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) { // 检查队列是否为空
            System.out.println("Queue is empty.");
            return -1;
        }
        int temp = queueArray[front]; // 保存队头元素
        front++; // 移动队头指针
        nItems--;
        return temp;
    }

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

    // 打印当前队列状态
    public void printQueue() {
        for (int i = front; i <= rear; i++) {
            System.out.print(queueArray[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        StudentQueue studentQueue = new StudentQueue(5); // 创建一个最大容量为5的队列

        studentQueue.enqueue(1001); // 添加学生ID 1001
        studentQueue.enqueue(1002); // 添加学生ID 1002
        studentQueue.enqueue(1003); // 添加学生ID 1003

        studentQueue.printQueue(); // 打印队列状态

        studentQueue.dequeue(); // 移除并返回队头学生ID

        studentQueue.printQueue(); // 再次打印队列状态

        studentQueue.enqueue(1004); // 添加学生ID 1004

        studentQueue.printQueue(); // 最后打印队列状态
    }
}

在这个示例中,StudentQueue 类实现了基本的队列功能,包括 enqueue (入队),dequeue (出队),isEmpty (检查队列是否为空),以及 printQueue (打印队列状态) 方法。main 方法演示了如何使用这个队列类进行一系列操作。请注意,这个实现假设所有学生ID都是整数,并且队列的大小是固定的。在实际应用中,你可能需要使用更灵活的数据结构,如 Java 的 ArrayList 或者 LinkedList 来实现动态调整大小的队列。
``

让我们继续通过一个更具体的例子来展示Java编程语言的使用。这次我们将创建一个简单的图书管理系统,该系统可以用来添加新书、删除书籍和显示所有书籍的信息。我们将使用面向对象的方法来设计这个系统。

首先,我们定义一个 Book 类,它包含书籍的基本信息,例如书名、作者和ISBN号。然后,我们创建一个 Library 类来管理这些书籍,包括添加、删除和显示书籍列表的功能。

下面是完整的代码实现:

import java.util.ArrayList;
import java.util.List;

// 定义 Book 类
class Book {
    String title;
    String author;
    String isbn;

    public Book(String title, String author, String isbn) {
        this.title = title;
        this.author = author;
        this.isbn = isbn;
    }

    @Override
    public String toString() {
        return "Title: " + title + ", Author: " + author + ", ISBN: " + isbn;
    }
}

// 定义 Library 类
class Library {
    List<Book> books;

    public Library() {
        books = new ArrayList<>();
    }

    // 添加书籍
    public void addBook(Book book) {
        books.add(book);
    }

    // 删除书籍
    public void removeBook(String isbn) {
        books.removeIf(book -> book.isbn.equals(isbn));
    }

    // 显示所有书籍
    public void displayBooks() {
        for (Book book : books) {
            System.out.println(book);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Library library = new Library();

        // 添加几本书籍
        library.addBook(new Book("The Great Gatsby", "F. Scott Fitzgerald", "978-0743273565"));
        library.addBook(new Book("To Kill a Mockingbird", "Harper Lee", "978-0061120084"));
        library.addBook(new Book("1984", "George Orwell", "978-0451524935"));

        // 显示所有书籍
        System.out.println("All Books:");
        library.displayBooks();

        // 删除一本书籍
        library.removeBook("978-0061120084");

        // 再次显示所有书籍
        System.out.println("\nBooks after removal:");
        library.displayBooks();
    }
}

在上述代码中:

  • Book 类包含书名、作者和ISBN三个属性,并重写了 toString() 方法以便于输出书籍信息。
  • Library 类包含一个 books 列表,用于存储 Book 对象。它提供了 addBook() 方法来添加书籍,removeBook() 方法来删除书籍(通过ISBN),以及 displayBooks() 方法来显示所有书籍。
  • Main 类是程序的入口点,它创建了一个 Library 对象,添加了几本书,显示了所有书籍,然后删除了一本书并再次显示书籍列表。

这个简单的图书管理系统展示了如何使用类、对象、集合和面向对象的编程概念来构建一个小型的应用程序。

上一篇:C++类的成员:静态成员变量、静态成员函数、非静态成员变量、非静态成员函数


下一篇:【分布式系统三】监控平台Zabbix对接grafana(截图详细版)