Bidirectional sequential queue ArrayDeque and bidirectional chain queue LinkedList, JDK has been included, omitted here. ArrayDeque includes sequential stack and sequential queue, while LinkedList contains chain stack and chain queue. Both ArrayDeque and LinkedList are thread-insecure. PriorityQueue priority queue is also in the JDK.
1. Implementation of sequential queues
package lang;import java.io.Serializable;import java.util.Arrays;/** * @ClassName: ArrayQueue * @Description: Sequential queue* @date January 20, 2014 at 3:46:19 pm * @param <T> */public class ArrayQueue<T> implements Serializable{ /** * @Fields serialVersionUID : TODO */ private static final long serialVersionUID = 7333344126529379197L; private int DEFAULT_SIZE = 10; private int capacity;//Save the length of the array private Object[] elementData;//Define an array to save elements of the sequential queue private int front = 0;//Fleet head private int rear = 0;//Terminal team//Create empty sequential queue public ArrayQueue() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //Create sequential queue public ArrayQueue(T element) { this(); elementData[0] = element; rear++; } public ArrayQueue(int initSize) { elementData = new Object[initSize]; } /** * Create an order queue with an array of specified length* @param element Specify the first element in the order queue* @param initSize Specify the length of the underlying array of the order queue*/ public ArrayQueue(T element, int initSize) { this.capacity = initSize; elementData = new Object[capacity]; elementData[0] = element; rear++; } /** * @Title: size * @Description: Get the size of the sequential queue* @return */ public int size() { return rear - front; } /** * @Title: offer * @Description: Enqueue* @param element */ public void offer(T element) { ensureCapacity(rear + 1); elementData[rear++] = element; } private void ensureCapacity(int minCapacity) { //If the original length of the array is less than the current required length int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { int newCapacity = (oldCapacity * 3) / 2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } } /** * @Title: poll * @Description: Dequeue* @return */ public T poll() { if (isEmpty()) { throw new IndexOutOfBoundsException("Empty queue exception"); } //Retain the value of the element on the front end of the queue T oldValue = (T) elementData[front]; //Release the element on the front end of the queue elementData[front++] = null; return oldValue; } /** * @Title: peek * @Description: Return the top element of the queue, but does not delete the top element of the queue* @return */ public T peek() { if (isEmpty()) { throw new IndexOutOfBoundsException("Empty queue exception"); } return (T) elementData[front]; } /** * @Title: isEmpty * @Description: Determine whether the order queue is an empty queue* @return */ public boolean isEmpty() { return rear == front; } /** * @Title: clear * @Description: Clear the order queue*/ public void clear() { // Assign all elements of the underlying array to null Arrays.fill(elementData, null); front = 0; rear = 0; } public String toString() { if (isEmpty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (int i = front; i < rear; i++) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } }}2. Implementation of chain queues
package lang;import java.io.Serializable;/** * @ClassName: LinkQueue * @Description: Chain Queue* @date January 21, 2014 at 3:24:38 pm * @param <T> */public class LinkQueue<T> implements Serializable{ /** * @Fields serialVersionUID : TODO */ private static final long serialVersionUID = -6726728595616312615L; //Define an internal class Node, and the Node instance represents the node of the chain queue. private class Node { private T data;//Save the data of the node private Node next;//Reference to the next node//Constructor without parameters public Node() { } //Constructor for initializing all attributes public Node(T data, Node next) { this.data = data; this.next = next; } } private Node front;//Save the head node of the chain queue private Node rear;//Save the tail node of the chain queue private int size;//Save the number of nodes already included in the chain queue/** * <p>Title: LinkQueue </p> * <p>Description: Create an empty chain queue</p> */ public LinkQueue() { //Empty chain queue, front and rear are both null front = null; rear = null; } /** * <p>Title: LinkQueue </p> * <p>Description: Create a chain queue by specifying data elements, which has only one element in the chain queue</p> */ public LinkQueue(T element) { front = new Node(element, null); //Only one node, front and rear point to the node rear = front; size++; } /** * @Title: size * @Description: Get the size of the sequential queue* @return */ public int size() { return size; } /** * @Title: offer * @Description: Enqueue* @param element */ public void offer(T element) { //If the chain queue is still an empty chain queue if (front == null) { front = new Node(element, null); rear = front;//There is only one node, front and rear point to the node} else { Node newNode = new Node(element, null);//Create a new node.next = newNode;//Let the next of the tail node point to the newly added node rear = newNode;//Taking a new node as the new tail node} size++; } /** * @Title: poll * @Description: Dequeue* @return */ public T poll() { Node oldFront = front; front = front.next; oldFront.next = null; size--; return oldFront.data; } /** * @Title: peek * @Description: Return the top element of the queue, but not delete the top element of the queue* @return */ public T peek() { return rear.data; } /** * @Title: isEmpty * @Description: Determine whether the order queue is an empty queue* @return */ public boolean isEmpty() { return size == 0; } /** * @Title: clear * @Description: Clear the order queue*/ public void clear() { // Assign the front and rear nodes as null front = null; rear = null; size = 0; } public String toString() { //When the chain queue is an empty chain queue if (isEmpty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = front; current != null; current = current.next) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } } public static void main(String[] args) { LinkQueue<String> queue = new LinkQueue<String>("aaaa"); //Add two elements queue.offer("bbbb"); queue.offer("cccc"); System.out.println(queue); //Croute queue.poll() after deleting an element; System.out.println("Delete queue after an element: " + queue); //Add an element again queue.offer("dddd"); System.out.println("Add the queue after an element again: " + queue); //Add an element again queue.poll(); //Add an element again queue.offer("eeee"); System.out.println(queue); }}3. Implementation of circular queues
package lang;import java.io.Serializable;import java.util.Arrays;/** * @ClassName: LoopQueue * @Description: LoopQueue * @date January 20, 2014 at 3:47:14 pm */public class LoopQueue<T> implements Serializable{ /** * @Fields serialVersionUID : TODO */ private static final long serialVersionUID = -3670496550272478781L; private int DEFAULT_SIZE = 10; private int capacity;//Save the length of the array private Object[] elementData;//Define an array to save the elements of the loop queue private int front = 0;//Fleet head private int rear = 0;//Terminal team//Create empty loop queue with the default array length public LoopQueue() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //Create a loop queue with an initialization element public LoopQueue(T element) { this(); elementData[0] = element; rear++; } /** * Create a loop queue with an array of specified length* @param element Specify the first element in the loop queue* @param initSize Specify the length of the underlying array of the loop queue*/ public LoopQueue(T element, int initSize) { this.capacity = initSize; elementData = new Object[capacity]; elementData[0] = element; rear++; } //Get the size of the loop queue public int size() { if (isEmpty()) { return 0; } return rear > front ? rear - front : capacity - (front - rear); } //Insert the queue public void add(T element) { if (rear == front && elementData[front] != null) { throw new IndexOutOfBoundsException("Exception whose queue is full"); } elementData[rear++] = element; //If the rear has reached the end, turn the head back = rear == capacity ? 0 : rear; } //Remove the queue public T remove() { if (isEmpty()) { throw new IndexOutOfBoundsException("Empty queue exception"); } //Retain the value of the element on the rear end of the queue T oldValue = (T) elementData[front]; //Release the element on the rear end of the queue elementData[front++] = null; //If front has reached the end, then turn front = front == capacity ? 0 : front; return oldValue; } //Return the top element of the queue, but do not delete the top element of the queue public T element() { if (isEmpty()) { throw new IndexOutOfBoundsException("Empty queue exception"); } return (T) elementData[front]; } //Determine whether the loop queue is an empty queue public boolean isEmpty() { //rear==front and the element at the rear is null return rear == front && elementData[rear] == null; } //Clear the loop queue public void clear() { // Assign all elements of the underlying array to null Arrays.fill(elementData, null); front = 0; rear = 0; } public String toString() { if (isEmpty()) { return "[]"; } else { //If front < rear, the valid element is the element between front and rear if (front < rear) { StringBuilder sb = new StringBuilder("["); for (int i = front; i < rear; i++) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } //If front >= rear, the valid element is else between front->capacity and 0->front { StringBuilder sb = new StringBuilder("["); for (int i = front; i < capacity; i++) { sb.append(elementData[i].toString() + ", "); } for (int i = 0; i < rear; i++) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } } } public static void main(String[] args) { LoopQueue<String> queue = new LoopQueue<String>("aaaa", 3); //Add two elements queue.add("bbbb"); queue.add("cccc"); //At this time the queue is full System.out.println(queue); //After deleting an element, the queue can add another element queue.remove(); System.out.println("The queue after deleting an element: " + queue); //Add an element again, and the queue is full again queue.add("dddd"); System.out.println(queue); System.out.println(queue); System.out.println(queue); //After deleting an element, the queue can add another element queue.remove(); //Add an element again, and the queue is full again queue.add("eeee"); System.out.println(queue); }}The above java queue implementation method (sequential queue, chain queue, loop queue) is all the content I have shared with you. I hope you can give you a reference and I hope you can support Wulin.com more.