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) 
队列的链表实现
队列用链表实现时，用头指针指向队列的第一个节点，用尾指针指向队列的最后一个节点。
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 
队列的应用场景
（1）银行排队，先来先服务。
（2）多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。
（3）网络爬虫实现网站抓取，就是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析。
相关文章教程推荐：java入门教程
                                                    
                                                
分享本文到 
×用微信扫描并分享
			
微海报分享

猜你喜欢：

java中继承与实现的区别 
java中HashMap和LinkedHashMap的区别 
java中栈的数组和链表实现 
关于JAVA异常类结构的详细讲解（附实例） 
Java之String、StringBuffer和StringBuilder的区别和原理