Article directory
- 1. Concept
- 2. Use of queues
-
- 2.1 Queue in java standard library
- 2.2 Implementation method
- 2.3 Simulate queue implementation
- 3. Classification of queues
-
- 3.1 Sequential Queue—-Circular Queue
- 3.2 Chain queue—-double-ended queue
- 4.Arraylist
1. Concept
- A special linear table that only allows data insertion operations at one end and deletion data operations at the other end.
- The queue has a first in first out FIFO (First In First Out)
2. Use of queues
2.1 Queue in java standard library
It can be seen that Queue in Java is an interface, and objects need to be instantiated through a class that implements this interface. LinkedList implements the Queue interface and can be instantiated through LinkedList.
Such as Queue queue = new LinkedList<>();
2.2 Implementation method
| Method | Function |
|---|---|
| boolean offer(E e) | Enqueue |
| E poll() | Dequeue |
| peek( ) | Get the opposite element |
| int size() | Get the number of valid elements in the queue |
| boolean isEmpty() | Detect whether the queue is empty |
java code implementation
public class QueueTest {<!-- -->
public static void main(String[] args) {<!-- -->
Queue<Integer> queue=new LinkedList<>();
//Enter the queue
for (int i=1;i<=6;i + + ){<!-- -->
queue.offer(i);
}
System.out.println("Number of elements in the queue:" + queue.size());
System.out.println("Opposite element:" + queue.peek());
//queue.poll();
System.out.println("Dequeue element:" + queue.poll());
for (int i=1;i<=5;i + + ){<!-- -->
queue.poll();
}
System.out.println("Whether the queue is empty:" + queue.isEmpty());
}
}
operation result:
2.3 Simulation implementation queue
- Queues can be implemented using arrays and linked lists.
- Using arrays, enqueuing and dequeuing operations are very simple, but it will cause a lot of waste of space.
- Therefore, a linked list is used to implement the queue
public class MyLinkedListQueue {<!-- -->
/** Construction method */
//Node
static class Node{<!-- -->
public int value;
public Node next;
public Node(int value){<!-- -->
this.value=value;
}
}
public Node head;//head node
public Node last;//last node
public int size;
public MyLinkedListQueue(){<!-- -->
head=null;
last=null;
}
/** Join the team */
public void offer(int value){<!-- -->
Node tempNode=new Node(value);
//When head is empty, it means there are no elements in the column, making the new node the head and tail node.
if (head==null){<!-- -->
head=tempNode;
last=tempNode;
}else {<!-- -->
last.next=tempNode;
last=tempNode;
}
size + + ;
}
/** Determine whether the queue is empty */
public boolean isEmpty(){<!-- -->
return size==0;
}
/** Dequeue */
public int poll(){<!-- -->
//Judge whether it is empty
if (isEmpty()){<!-- -->
throw new RuntimeException("Queue is empty");
}
int value= head.value;
head=head.next;
//If the header is empty, it means there is only one element at the beginning, and then you need to make last empty.
if (head==null){<!-- -->
last=null;
}
size--;
return value;
}
/** Get the opposite element */
public int peek(){<!-- -->
//Judge whether it is empty
if (isEmpty()){<!-- -->
throw new RuntimeException("Queue is empty");
}
return head.value;
}
/** Get the number of elements */
public int size(){<!-- -->
return size;
}
}
3. Classification of queues
3.1 Sequential Queue—-Circular Queue
What is a circular queue?
The circular queue is a sequential storage queue connected end to end. As the name suggests, the circular queue means that the memory of the queue can be recycled.
Why is there a circular queue?
In the sequential queue, the problem of false overflow occurs. The circular queue is for the problem of false overflow. False overflow causes a waste of memory. The circular queue can make effective use of memory.
Implementation of circular queue:
- 1. Empty queue
At the beginning, front is the head pointer of the queue, and rear is the tail pointer of the queue. When the queue is empty, front and rear point to the same position.
- 2. There are elements in the queue
When inserting an element, the rear will move backward as the element is inserted, and the front will not move. If the element is deleted, the rear will move forward, and the front will still not move.
- 3. How to determine whether the circular queue is full? Or is it empty?
Give a counter count
count + + when inserting an element, count – – when deleting an element
Judgment condition when the queue is empty: count == 0
Judgment condition when the queue is full: count=M or (count>0 & amp; & amp; rear==front)
java code implementation:
public class MyCircularQueue {<!-- -->
int[] array;
int front;//define the head node
int rear;//define the tail node
int count;//Define valid nodes
int N;//define the length of the array
//define array
public MyCircularQueue(int k) {<!-- -->
array = new int[k];
N = k;
}
//Check if it is empty
public boolean isEmpty() {<!-- -->
return 0 == count;
}
//Check if it is full
public boolean isFull() {<!-- -->
return count == array.length;
}
//Enter the queue
public boolean enQueue(int value) {<!-- -->
if(isFull()){<!-- -->
return false;
}
array[rear] = value;
rear + + ;
if(rear == N){<!-- -->
rear = 0;
}
count + + ;
return true;
}
//dequeue
public boolean deQueue() {<!-- -->
if(isEmpty()){<!-- -->
return false;
}
front + + ;
front %= N;
count--;
return true;
}
//Return to the head of the queue
public int Front() {<!-- -->
if(isEmpty()){<!-- -->
return -1;
}
return array[front];
}
//Return to the end of the queue
public int Rear() {<!-- -->
if(isEmpty()){<!-- -->
return -1;
}
return array[(rear + N - 1)% N];
}
}
3.2 Chain queue—-double-ended queue
Double-ended queue is also called double ended queue, or deque for short. Double-ended queue does not have restrictions such as queues and stacks. It allows both ends to perform enqueue and dequeue operations, which means that elements can be dequeued and dequeued from the head of the queue. You can also leave and enter the queue from the end of the queue.
java code implementation:
/**
* Simulate the queue---the bottom layer uses a two-way linked list
* In the collection framework, Queue is an interface---the bottom layer uses LinkedList.
*/
public class Queue<E> {<!-- -->
//Doubly linked list node
public static class ListNode<E>{<!-- -->
ListNode<E> next;
ListNode<E> prev;
E value;
ListNode(E value){<!-- -->
this.value = value;
}
}
ListNode<E> first; // Team head
ListNode<E> last; // end of queue
int size = 0;
//Enqueue---Insert a new node into the doubly linked list position
public void offer(E e){<!-- -->
ListNode<E> newNode = new ListNode<>(e);
if(first == null){<!-- -->
first = newNode;
// last = newNode;
}else{<!-- -->
last.next = newNode;
newNode.prev = last;
// last = newNode;
}
last = newNode;
size + + ;
}
// Dequeue---Delete the first node of the doubly linked list
public E poll(){<!-- -->
// 1. The queue is empty
// 2. There is only one element in the queue - there is only one node in the linked list - delete it directly
// 3. There are multiple elements in the queue --- there are multiple nodes in the linked list -- delete the first node
E value = null;
if(first == null){<!-- -->
return null;
}else if(first == last){<!-- -->
last = null;
first = null;
}else{<!-- -->
value = first.value;
first = first.next;
first.prev.next = null;
first.prev = null;
}
--size;
return value;
}
// Get the head element---get the value range of the first node in the linked list
public E peek(){<!-- -->
if(first == null){<!-- -->
return null;
}
return first.value;
}
public int size() {<!-- -->
return size;
}
public boolean isEmpty(){<!-- -->
return first == null;
}
}
4.Arraylist
Reference article:
- Stack and queue (super detailed java implementation)
- Stacks and queues in Java data structures (with illustrations)