1. Write it in front
The queues in the data structure should be more familiar, which is first-in-first-out. Because of order, they are named as queues. It is like queuing. Inserting a new node at the end of the front, deleting the node at the first.jdk collection framework also provides a Queue interface. This interface represents a queue. Sequential queues: ArrayBlockingQueue, LinkedBlockingQueue. (The above two are foot-color queues) and the other is ConcurentLinkedQueue.
The underlying implementation consists of two types of combined lists. The implementation of arrays will have disadvantages, which will cause false fullness. At the beginning, when the queue is empty, the reference variables of the first reference variable to the tail are null. As the queue elements are deleted, front+1 will occur, and the rear equals the capacity of the underlying array. In the sequential storage structure, front always saves the index of the elements that are about to be out of the queue in the queue, and the rear always saves the index of the elements that are about to be entered into the queue. The number of elements in the queue is rear-front. In the sequential queue, the underlying layer is an array, so the saved data elements will not change, and only the two reference variables, rear and front, are changed.
What can be used to effectively utilize space using chain storage here is that the reference variables take up extra space.
Common operations for queues:
1: Initialization
2: Return the length of the queue
3: Add elements
4: Delete elements
5: Access the header element
6: Access the queue's pair-tail elements
7: Determine whether the queue is empty
8: Clear the queue
2. Custom implementation
The source code display is clear, so there is no need to introduce it
public class LinkedQueue<T>{//Custom chain queue-Use non-static internal classes to represent the data node of the chain queue private class Node{//Denote the data node of the chain queue private T data;//Reference to the next node private Node next; @SuppressWarnings("unused") public Node(){ }public Node(T data,Node next){ this.data=data; this.next=next; }}//Define the reference to the head and tail of the chain queue private Node front; private Node rear; //Define the size of the chain stack private int size; //Create an empty chain-to-column public LinkedQueue(){ front=null; rear=null;}//Create a chain-pair column with a certain element, and only one node public LinkedQueue(T element){front=new Node(element,null);//Point to the same element rear=front;size++;}//Return the size of the chain queue public int length(){return size;}//Return the element with the right header in the chain queue, and do not delete the header element public T elementFront(){if(!empty()){ return front.data;}else{ return null; }}//Access the last element of the queue public T elementRear(){if(!empty()){ return rear.data; }else{ return null; } }//Return whether the current chain pair queue is empty public boolean empty(){ return size==0; }//Clear a chain queue public void clear(){ front=null; rear=null; size=0;}//Insert a node in the chain queue--pair public void add(T element){ //If the chain pair column is empty, create a new node if(front==null){ rear=new Node(element,null); front=rear; }else{ //Dynamicly create a new node Node newRear=new Node(element,null); rear.next=newRear; rear=newRear; }size++;}//Delete a node in the chain queue and return the deleted node public T remove(){ Node oldFront=front; front=front.next; oldFront.next=null; size--; return oldFront.data;}//Return the queue public String toString(){ //If the chain queue is empty chain queue is if(empty()){ return "[]"; }else{ StringBuilder sBuilder=new StringBuilder("["); for(Node current=front;current!=null;current=current.next){ sBuilder.append(current.data.toString()+",");} int len=sBuilder.length(); return sBuilder.delete(len-1, len).append("]").toString();}}public static void main(String[] args) { LinkedQueue<String> lQueue=new LinkedQueue<String>(); lQueue.add("aaa"); lQueue.add("bbb"); lQueue.add("ccc"); lQueue.add("ddd");System.out.println("Returns the value of the head node of the queue:"+lQueue.elementFront());System.out.println("Returns the value of the tail node of the queue:"+lQueue.elementRear());System.out.println(lQueue.length());System.out.println(lQueue);}}Running results:
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.