java中关于队列的数组和链表实现

本文由java入门教程栏目为大家介绍java中关于队列的数组和链表实现,希望可以帮助到有需要的同学。队列是一种先进先出(FIFO)的线性的数据结构,队列的主要操作为入队和出队。

java中关于队列的数组和链表实现

队列的介绍

队列是一种先进先出(FIFO)的线性的数据结构,队列的主要操作为入队和出队。

队头:队列的出口端,队尾:队列的入口端,通常在数组中表示为最后入队元素的下一个位置。

在用数组实现时,注意:若队头不断有元素出队,那么队列的可用空间就会变小,所以我们通常用循环队列来实现,此时队尾也可能出现在队头的前面。

相关学习视频教程推荐:java学习

队列的数组实现

队列的数组实现这里的队列一般都是循环队列!

特别注意:

(1)队列满时的判断条件为(队尾下标+1) % 数组长度 = 队头下标

(2)队尾指针指向的位置空出一位,因此队列最大容量比数组长度小1。

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();
    }
 
}
只听到从山间传来架构君的声音:
郢人逝矣,谁与尽言?。有谁来对上联或下联?

队列的链表实现

队列用链表实现时,用头指针指向队列的第一个节点,用尾指针指向队列的最后一个节点。

此代码由Java架构师必看网-架构君整理
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(); } }

队列的应用场景

(1)银行排队,先来先服务。

(2)多线程中,争夺公平锁的等待队列,就是按照访问顺序来决定线程在队列中的次序的。

(3)网络爬虫实现网站抓取,就是把待抓取的网站URL存入队列中,再按照存入队列的顺序来依次抓取和解析。

相关文章教程推荐:java入门教程

本文来源,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/35545
0

发表评论