Array and linked list implementation of queue in java

Introduction to Queue

Queue is a first-in-first-out (FIFO) linear data structure. The main operation of the queue is to join the queue. and dequeue.

Head of the queue: the exit end of the queue, tail of the queue: the entrance end of the queue, usually represented in the array as the next position of the last element entered into the queue.

When implementing with an array, please note: If elements continue to be dequeued at the head of the queue, the available space of the queue will become smaller, so we usually use a circular queue to implement it, and at this time the tail of the queue will also May appear in front of the leader of the line.

Recommended related learning video tutorials: java learning

Queue array implementation

Queue array implementation here The queue is generally a circular queue!

Special note:

(1) The judgment condition when the queue is full is (queue tail subscript 1) % array length = queue head subscript

(2) The position pointed by the queue tail pointer has one vacancy, so the maximum capacity of the queue is 1 less than the array length.

public class MyQueue {
    private int[] array;
    private int front;
    private int rear;
    public MyQueue(int capacity){
        array = new int[capacity];
    }
 
    /*
    入队时，只需判断队列是否已满，若队列已满，则抛出异常，其他情况（包括队列为空）都正常插入
     */
    public void enQueue(int data) throws Exception{
        if((rear+1) % array.length  == front)
            throw new Exception("队列已满，不能入队！");
        array[rear] = data;
        rear = (rear+1) % array.length;
    }
 
    /*
    出队时，判断队列是否为空，若队列为空，抛出异常
     */
    public int deQueue() throws Exception{
        if(front == rear)
            throw new Exception("队列为空，不能出队！");
        int temp = array[front];
        front = (front+1) % array.length;
        return temp;
    }
 
//    public void output(){
//        for(int i = front; ((i+1) % array.length) <= rear; i++){
//一直在循环输出，严重错误！不能把取模判断语句写在条件里面！
//            i %= array.length;
//            System.out.println(array[i]);
//        }
//    }
 
    public void output(){
        for(int i = front; i != rear; i = (i+1) % array.length){
            System.out.println(array[i]);
        }
    }
    public static void main(String[] args) throws Exception{
        MyQueue myQueue = new MyQueue(5);//长度为5的队列只能插入4个元素
        myQueue.enQueue(1);
        myQueue.enQueue(3);
        myQueue.enQueue(2);
        myQueue.enQueue(4);
        myQueue.deQueue();
        myQueue.deQueue();
        myQueue.enQueue(5);
        myQueue.enQueue(6);
        myQueue.output();
    }
 
}

Linked list implementation of queue

When the queue is implemented with a linked list, use the head pointer to point to the first node of the queue, and use The tail pointer points to the last node of the queue.

public class MyQueue_LinkList {
    private static class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }
 
    private Node front;
    private Node rear;
    private int size;//队列中实际元素的个数
    private int maxsize;
 
    public MyQueue_LinkList(int capacity){
        maxsize = capacity;
    }
 
    public void enQueue(int data) throws Exception{
        if(size >= maxsize)
            throw new Exception("队列已满，无法入队");
        Node insertedNode = new Node(data);
        if(size == 0){
            front = insertedNode;
            rear = insertedNode;
        }
        else{
            rear.next = insertedNode;
            rear = insertedNode;
        }
        size++;
    }
 
    public int deQueue() throws Exception{
        if(front == null)
            throw new Exception("队列为空，无法出队！");
        int temp;
        if(front == rear)//队列中只有一个节点
            rear = null;
        temp = front.data;
        front = front.next;
        size--;
        return temp;
    }
 
    public void output(){
        Node temp = front;
        for(int i = 0 ; i < size; i++){
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
 
    public static void main(String[] args) throws Exception{
        MyQueue_LinkList myQueue_linkList = new MyQueue_LinkList(5);
        myQueue_linkList.enQueue(1);
        myQueue_linkList.enQueue(3);
        myQueue_linkList.enQueue(2);
        myQueue_linkList.deQueue();
        myQueue_linkList.deQueue();
        myQueue_linkList.enQueue(5);
        myQueue_linkList.enQueue(7);
        myQueue_linkList.output();
 
    }
}

Queue application scenarios

(1) Bank queue, first come first served.

(2) In multi-threading, the waiting queue competing for fair locks determines the order of threads in the queue according to the access sequence.

(3) The web crawler implements website crawling by storing the website URLs to be crawled in the queue, and then crawling and parsing them in the order in which they are stored in the queue.

Recommended related articles and tutorials: java introductory tutorial

The above is the detailed content of Array and linked list implementation of queue in java. For more information, please follow other related articles on the PHP Chinese website!