How to implement queue insertion and deletion operations in Java

How to implement queue insertion and deletion operations in Java

Queue is a commonly used data structure that follows the first-in-first-out (FIFO) principle. In Java, queues can be implemented using arrays or linked lists. The two implementation methods will be introduced below and code examples will be given.

1. Use arrays to implement queues:

The idea of ​​arrays to implement queues is to use an array as the underlying data structure of the queue, and maintain insertion and deletion by maintaining head and tail pointers. operate.

Code example:

public class ArrayQueue {
    private int[] queueArray;    // 队列数组
    private int front;  // 队头指针
    private int rear;   // 队尾指针
    private int maxSize;    // 队列的最大容量

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

    // 入队操作
    public void enqueue(int data) {
        if (isFull()) {
            throw new IllegalStateException("队列已满，无法入队");
        }
        rear++;
        queueArray[rear] = data;
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法出队");
        }
        int data = queueArray[front];
        front++;
        return data;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return (rear + 1 == front);
    }

    // 判断队列是否已满
    public boolean isFull() {
        return (rear == maxSize - 1);
    }
}

2. Use a linked list to implement a queue:

The idea of ​​a linked list to implement a queue is to maintain a pointer to the head of the queue and a Pointer to the end of the queue to implement insertion and deletion operations. Each time a new element is inserted, it is added to the end of the queue, and the pointer at the end of the queue points to the new element; every time an element is deleted, the pointer at the head of the queue points to the next element.

Code example:

public class LinkedQueue {
    private Node front;    // 队头指针
    private Node rear;     // 队尾指针

    public LinkedQueue() {
        front = null;
        rear = null;
    }

    // 节点类
    private class Node {
        private int data;   // 数据
        private Node next;  // 指向下一个节点的指针

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // 入队操作
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法出队");
        }
        int data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return data;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return (front == null);
    }
}

The above are two ways to implement queue insertion and deletion operations in Java. Using array implementation can improve the efficiency of random access to a certain extent, while using linked list implementation is more flexible and can dynamically adjust the size of the queue. Just choose the appropriate implementation method according to actual needs.

The above is the detailed content of How to implement queue insertion and deletion operations in Java. For more information, please follow other related articles on the PHP Chinese website!