Shulou(Shulou.com)06/02 Report--

This article mainly introduces "what is the realization principle of Java one-way queue and ring queue". In daily operation, I believe that many people have doubts about the implementation principle of Java one-way queue and ring queue. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the questions of "what is the realization principle of Java one-way queue and ring queue". Next, please follow the editor to study!

Characteristics of the queue

1. It can be implemented in both arrays and linked lists.

two。 Follow the first-in, first-out (FIFO) rule, that is, first-in, first-out data.

3. Belongs to an ordered list.

Illustrating the implementation process:

1. Defines a fixed-length array of length maxSize.

two。 Set two pointers first =-1 (pointing to the first bit of the first data in the queue, which ensures that the header pointer is 0 after the first data is added, the same as the subscript of the array, and used for operation dequeue) and last =-1 (points to the end of the queue for operation queuing).

3. That is, first will increase as a result of out-of-team operations, and last will increase because of joining the team.

Code implementation:

Package queue; public class ArrayQueueTest {public static void main (String [] args) {ArrayQueue arrayQueue = new ArrayQueue (3); arrayQueue.addQueue ("Joan"); arrayQueue.addQueue ("long"); arrayQueue.addQueue ("long"); arrayQueue.showAllQueueData (); System.out.println (arrayQueue.getQueue ());}} class ArrayQueue {private int maxSize / / defines the maximum length of the queue private int first; / / points to the previous position of the queue header! Previous position! Exit direction private int last; / / point to the end of the queue! That is the last data! Private String [] arr; / / create an empty array first. The specific length is unknown and needs to be determined by maxSize. / / the constructor initializes the queue information public ArrayQueue (int maxSize) {this.maxSize = maxSize; this.first =-1; this.last =-1; arr = new String [maxSize];} / / determines whether it is empty public boolean isEmpty () {if (first = = last) {System.out.println ("queue is empty ~"); return true } else {System.out.println ("queue is not empty ~"); return false;}} / / determine whether the queue is full public boolean isFull () {if (last = = maxSize-1) {System.out.println ("queue is full ~"); return true } else {System.out.println ("queue is not full ~"); return false;}} / / queue public void addQueue (String data) {if (last = = maxSize-1) {System.out.println ("queue is full and cannot be added!") ; return;} else {last++; / / add data is only related to the last subscript arr [last] = data; return }} / / dequeue public String getQueue () {if (isEmpty ()) {/ / because the getQueue method is int, it needs to return data, if there is no data, it also needs to return / / if-1 or other data is returned The number that can be misunderstood is-1 or other / / so handle throw new RuntimeException by throwing an exception ("queue is empty, no data ~") } else {first++; return arr [first];}} / / traverse all information about the queue public void showAllQueueData () {if (first = = last) {return;} for (int I = 0; I)

< arr.length; i++) { System.out.println("arr["+i+"]"+"="+arr[i]); } } //获取队列头数据 public String headQueueData(){ if (isEmpty()){ throw new RuntimeException("无数据~~~"); } return arr[++first]; }} 队列缺点： 由于出队操作，使得first指针上移变大，导致数组前面空出来的位置就不能再继续添加数据，即不能再被重复使用，这样一个队列只能使用一次，内存效率太低，所以需要使用环形队列来优化解决。 优化解决--环形队列实现思路 1.first指针初始默认设置为0，指向队列头部，则arr[first] 就是第一个数据。 2.last指针初始默认也为0，但是会随着增加数据而后移。 3.队列满的条件： (last + 1) % maxSize == first last+1是为了让指针后移，而且如果不设置为 last+1 那么一开始的时候last为0 ， last % maxSize == 0，且first也为0，还没加数据就满了。 4.队列为空的条件： first == last 5.由于判断是否满的时候： last+1 ，导致实际上可以装的数据比数组长度少 1 环形队列各步骤及各方法实现讲解 1.队列初始化 ： class CircleArryQueue{ private int maxSize ; //数组长度，即队列最大容量 private int first; //头指针，控制出队操作 private int last; //尾指针，控制入队操作 private int[] arr; //数组类型，可以换其他的。 //构造器初始化信息 public CircleArryQueue(int maxSize){ this.maxSize = maxSize; this.arr = new int[maxSize]; this.first = 0; //这两个可以不加，不叫也是默认为0 this.last = 0; }} 2.判断队列是否为空： public boolean isEmpty(){ //头指针和尾指针一样 则说明为空 return last == first; } 3.判断队列是否满： /**这里的 last+1 主要是为了让指针后移，特别是在队列尾部添加数据的时候，本来用last也可以判断，但*是一开始还没加数据的时候，如果直接用last % maxSize == first，结果是true，所以为了解决指针后*移和判断是否满，用来last+1。其次，因为last+1可能会导致数组指针越界，所以用取模来控制它的范 * 围，同时保证他会在一个固定的范围循环变换，也利于环形队列的实现。*/public boolean isFull(){ return (last + 1) % maxSize == first;} 4.添加数据到队列尾部：入队 public void pushData(int data){ //先判断是否满了 if(isFull()){ System.out.println("队列已经满啦~~"); return; } arr[last] = data; //last+1是为了后移，取模是为了避免指针越界，同时可以让指针循环 last = (last + 1) % maxSize;} 5.取出队首数据：出队 public int popData(){ if (isEmpty()) { //抛异常就可以不用返回数据了 new RuntimeException("队列为空，没有获取到数据~~"); } //要先把first对应的数组数据保存-->

First moves back-- > the returned data int value = arr [first]; / / the operation of first+1 is the same as last+1, and the mode is also first = (first+1)% maxSize; System.out.println (value); return value / / if the first pointer is not saved, the returned data is incorrect / / if the data is returned directly, it is also wrong that the first pointer has not been moved back, so you need to use a third-party variable}

6. Show all the data in the queue:

Public void showAllData () {if (isEmpty ()) {System.out.println ("queue is empty, no data ~"); return;} / / here I is not 0, because it is possible that there has been a popData () operation before, so that firs is not 0, so it is best to use / / first to assign a dynamic value to I, for (int I = first; I)

< first+size() ; i++) { System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]); } 7.获取队列中数据的总个数： public int dataNum(){ //韩顺平老师的教程上是这样写，但是我理解不了..........。 return (last+maxSize-first) % maxSize; } 8.查看队首数据但不弹出： public void seeFirstData(){ return arr[first];} 全部代码整合： package 练习;import java.util.Scanner;public class CircleArryQueue { public static void main(String[] args){ CircleQueue circleQueue = new CircleQueue(4); System.out.println("--------测试环形队列--------"); char key = ' '; Scanner scanner = new Scanner(System.in); boolean flag = true; while (flag){ System.out.println("s(showAllData):查看队列数据"); System.out.println("p(pushData):队尾添加数据"); System.out.println("g(popData):弹出队头数据"); System.out.println("h(seefirstData)：获取队头数据"); System.out.println("e(exit):退出程序"); key = scanner.next().charAt(0); switch (key){ case 's': circleQueue.showAllData(); break; case 'p': System.out.println("输入一个数据："); int obj = scanner.nextInt(); circleQueue.pushData(obj); break; case 'g': circleQueue.popData(); break; case 'h': circleQueue.seeFirstData(); break; case 'e': scanner.close(); flag = false; break; default: break; } } System.out.println("程序结束~~~"); }}class CircleQueue { private int maxSize ; //数组长度，即队列最大容量 private int first; //头指针，控制出队操作 private int last; //尾指针，控制入队操作 private int[] arr; //数组类型，可以换其他的。 //构造器初始化信息 public CircleQueue(int maxSize){ this.maxSize = maxSize; this.arr = new int[maxSize]; this.first = 0; //这两个可以不加，不叫也是默认为0 this.last = 0; } public boolean isEmpty(){ //头指针和尾指针一样 则说明为空 return last == first; }/**这里的 last+1 主要是为了让指针后移，特别是在队列尾部添加数据的时候，本来用last也可以判断但*是一开始还没加数据的时候，如果直接用last % maxSize == first，结果是true，所以为了解决指针*后移和判断是否满，用来last+1。其次，因为last+1可能会导致数组指针越界，所以用取模来控制它*的范围，同时保证他会在一个固定的范围循环变换，也利于环形队列的实现。*/ public boolean isFull(){ return (last + 1) % maxSize == first; } public void pushData(int data){ //先判断是否满了 if(isFull()){ System.out.println("队列已经满啦~~"); return; } arr[last] = data; //last+1是为了后移，取模是为了避免指针越界，同时可以让指针循环 last = (last + 1) % maxSize; } public int popData(){ if (isEmpty()) { //抛异常就可以不用返回数据了 throw new RuntimeException("队列为空，没有获取到数据~~"); } //要先把first对应的数组数据保存-->

First moves back-- > the returned data int value = arr [first]; / / the operation of first+1 is the same as last+1, and the mode is also first = (first+1)% maxSize; System.out.println (value); return value / / if the first pointer is not saved, the returned data is incorrect / / if the data is returned directly, it is also wrong that the first pointer has not been moved back, so you need to use a third-party variable} / / to view all data public void showAllData () {if (isEmpty ()) {System.out.println ("queue is empty, no data ~"). } / / I is not 0 here, because it is possible that there has been a popData () operation before, so it is best to use / / first to assign a dynamic value to I, for (int I = first; I < first+dataNum (); iSize +) {System.out.println ("arr [" + I% maxSize+ "]" + arr [i%maxSize])) }} / / check the number of valid data public int dataNum () {/ / Han Shunping teacher's tutorial says this, but I can't understand it. Return (last+maxSize-first)% maxSize;} / / View the first data of the queue public int seeFirstData () {System.out.println (arr [first]); return arr [first];}} at this point, the study on "what is the implementation principle of Java one-way queue and ring queue" is over, hoping to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.