Java实现队列的例子

在本文中，星辉小编会给大家介绍Java实现队列。队列是遵循 FIFO(先进先出)原则的线性数据结构。这意味着首先插入的对象将是第一个出来的对象，然后是下一个插入的对象。

队列支持以下核心操作：

入队：在队列的尾部插入一个项目。

出队：从队列的前面移除对象并返回它，从而将队列大小减一。

Peek：返回队列前面的对象而不删除它。

IsEmpty：测试队列是否为空。

大小：返回队列中存在的元素总数。

使用数组的队列实现：

// A class to represent a queue
class Queue
{
    private int[] arr;      // array to store queue elements
    private int front;      // front points to the front element in the queue
    private int rear;       // rear points to the last element in the queue
    private int capacity;   // maximum capacity of the queue
    private int count;      // current size of the queue 
    // Constructor to initialize a queue
    Queue(int size)
    {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
        count = 0;
    } 
    // Utility function to dequeue the front element
    public int dequeue()
    {
        // check for queue underflow
        if (isEmpty())
        {
            System.out.println("Underflow\nProgram Terminated");
            System.exit(-1);
        } 
        int x = arr[front]; 
        System.out.println("Removing " + x); 
        front = (front + 1) % capacity;
        count--; 
        return x;
    } 
    // Utility function to add an item to the queue
    public void enqueue(int item)
    {
        // check for queue overflow
        if (isFull())
        {
            System.out.println("Overflow\nProgram Terminated");
            System.exit(-1);
        } 
        System.out.println("Inserting " + item); 
        rear = (rear + 1) % capacity;
        arr[rear] = item;
        count++;
    } 
    // Utility function to return the front element of the queue
    public int peek()
    {
        if (isEmpty())
        {
            System.out.println("Underflow\nProgram Terminated");
            System.exit(-1);
        }
        return arr[front];
    } 
    // Utility function to return the size of the queue
    public int size() {
        return count;
    } 
    // Utility function to check if the queue is empty or not
    public boolean isEmpty() {
        return (size() == 0);
    } 
    // Utility function to check if the queue is full or not
    public boolean isFull() {
        return (size() == capacity);
    }
} 
class Main
{
    public static void main (String[] args)
    {
        // create a queue of capacity 5
        Queue q = new Queue(5); 
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3); 
        System.out.println("The front element is " + q.peek());
        q.dequeue();
        System.out.println("The front element is " + q.peek()); 
        System.out.println("The queue size is " + q.size()); 
        q.dequeue();
        q.dequeue(); 
        if (q.isEmpty()) {
            System.out.println("The queue is empty");
        }
        else {
            System.out.println("The queue is not empty");
        }
    }
}

输出：

Inserting 1
Inserting 2
Inserting 3
前面的元素是 1
移除 1
前面的元素是 2
队列大小是 2
移除 2
移除 3
队列是空的

enqueue()、dequeue()、peek()和函数 的时间复杂度是常数isEmpty()，size()即O(1)。

使用Queue界面：

Java的库还包含指定队列操作的Queue接口。以下是使用该类的Queue接口示例：LinkedList

import java.util.LinkedList;
import java.util.Queue; 
class Main
{
    public static void main(String[] args)
    {
        Queue<String> queue = new LinkedList<String>(); 
        queue.add("A");     // Insert `A` into the queue
        queue.add("B");     // Insert `B` into the queue
        queue.add("C");     // Insert `C` into the queue
        queue.add("D");     // Insert `D` into the queue 
        // Prints the front of the queue (`A`)
        System.out.println("The front element is " + queue.peek()); 
        queue.remove();     // removing the front element (`A`)
        queue.remove();     // removing the front element (`B`) 
        // Prints the front of the queue (`C`)
        System.out.println("The front element is " + queue.peek()); 
        // Returns the total number of elements present in the queue
        System.out.println("The queue size is " + queue.size()); 
        // check if the queue is empty
        if (queue.isEmpty()) {
            System.out.println("The queue is empty");
        }
        else {
            System.out.println("The queue is not empty");
        }
    }
}

输出：

前面元素是 A
前面元素是 C
队列大小是 2
队列不为空