数据结构之队列 - 实现及应用 |21xrx.com

数据结构之队列 - 实现及应用

2023-06-18 04:45:58 深夜i 13 0

Java 队列数组链表进程调度多线程编程 Web应用

队列是一种常用的数据结构，它具有“先进先出”的特点。在Java中，队列的实现方式有多种，本文将介绍用数组及链表两种方式实现队列，并探讨它们的应用。

一、用数组实现队列

数组是一种顺序存储结构，所以通常用数组来实现队列时，需要考虑判断队列是否已满。以下是数组实现队列的Java代码：

public class ArrayQueue {
  private int[] arr;
  private int front; // 队头
  private int rear; // 队尾
  private int maxsize; // 队列最大容量
  public ArrayQueue(int maxsize) {
    this.maxsize = maxsize;
    arr = new int[maxsize];
    front = -1; // 头指针初始为-1
    rear = -1; // 尾指针初始为-1
  }
  public boolean isFull()
    return rear == maxsize - 1;
  
  public boolean isEmpty()
    return front == rear;
  
  public void add(int n) {
    if (isFull()) {
      throw new RuntimeException("队列已满，无法添加！");
    }
    rear++;
    arr[rear] = n;
  }
  public int get() {
    if (isEmpty()) {
      throw new RuntimeException("队列为空，无法取值！");
    }
    front++;
    return arr[front];
  }
}

二、用链表实现队列

链表是一种动态存储结构，因此用链表来实现队列时，不需要考虑队列是否已满的问题。以下是链表实现队列的Java代码：

public class LinkedQueue {
  private Node front; // 队头指针
  private Node rear; // 队尾指针
  public LinkedQueue()
    front = null; // 头指针初始为null
    rear = null; // 尾指针初始为null
  
  public boolean isEmpty()
    return front == null;
  
  public void add(int n) {
    Node newNode = new Node(n);
    if (rear == null)
      front = newNode;
     else
      rear.next = newNode;
    
    rear = newNode;
  }
  public int get() {
    if (isEmpty()) {
      throw new RuntimeException("队列为空，无法取值！");
    }
    int result = front.getData();
    front = front.next;
    if (front == null)
      rear = null;
    
    return result;
  }
  private static class Node {
    private int data; // 数据域
    private Node next; // 指针域
    public Node(int data)
      this.data = data;
      next = null;
    
    public int getData()
      return data;
    
  }
}

三、应用场景

队列的应用非常广泛，以下列举几个常见的应用场景：

1. 在操作系统中，进程调度通常采用队列的方式。将执行的进程插入队列中，然后按照“先进先出”的原则进行调度。

2. 在多线程编程中，任务队列用于存储将要执行的任务。每个线程从队列中取出任务进行执行，这样能够避免任务之间的冲突。

3. 在Web应用中，请求队列用于处理高并发的请求。将请求存入队列中，然后逐个进行处理，这样能够控制请求的处理速度，避免服务器崩溃。

四、关键词

Java、队列、数组、链表、进程调度、多线程编程、Web应用。

上一篇: idea打包java可执行jar包

下一篇: 如何解决C语言中使用未初始化的局部变量

评论区

相似文章