java中如何实现队列数组和链表
这篇文章将为大家详细讲解有关java中如何实现队列数组和链表,文章内容质量较高,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。
龙岩网站建设公司成都创新互联,龙岩网站设计制作,有大型网站制作公司丰富经验。已为龙岩近1000家提供企业网站建设服务。企业网站搭建\外贸网站制作要多少钱,请找那个售后服务好的龙岩做网站的公司定做!
队列的介绍
队列是一种先进先出(FIFO)的线性的数据结构,队列的主要操作为入队和出队。
队头:队列的出口端,队尾:队列的入口端,通常在数组中表示为最后入队元素的下一个位置。
在用数组实现时,注意:若队头不断有元素出队,那么队列的可用空间就会变小,所以我们通常用循环队列来实现,此时队尾也可能出现在队头的前面。
队列的数组实现
队列的数组实现这里的队列一般都是循环队列!
特别注意:
(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(); } }
队列的链表实现
队列用链表实现时,用头指针指向队列的第一个节点,用尾指针指向队列的最后一个节点。
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中如何实现队列数组和链表
文章网址:http://pwwzsj.com/article/pjsohe.html