“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”
Introduction to the
A dequeue is a two-way queue that can insert and fetch data from the head of the queue or from the tail of the queue.
This article will show you how to create a dequeue and the basic operations of a dequeue.
Implementation of bidirectional queue
And normal queue items, two-way queues can insert and delete at the head and tail, respectively, so a dequeue needs to implement these four methods:
- InsertFront (): Inserts data from the dequeue header
- InsertLast (): Inserts data from the end of the dequeue
- DeleteFront (): Deletes data from the dequeue header
- DeleteLast (): Deletes data from the end of the dequeue
We also need a head and a rear to point to the head and tail nodes of the queue.
That is, a queue that implements these four methods is a bidirectional queue. We don’t care how it’s implemented internally.
Let’s take a look at the insert and delete operations in dequeue:
- Insert in the head
- Insert at the tail
- Delete in the header
- Delete at the tail
Two-way queues can also be implemented in a variety of ways, such as circular arrays and linked lists.
Array implementation of a bidirectional queue
Because the array itself is already contextual, so you know that head can get the data behind it, and you know that rear can get the data in front of it.
So in the array implementation, it’s enough to store the index values of head and rear.
We just need to add methods to insert data to the header and delete data to the tail:
// Queue from the head
public void insertFront(int data){
if(isFull()){
System.out.println("Queue is full");
}else{
// Insert ArrayDeque from the header
head = (head + capacity - 1) % capacity;
array[head]= data;
// If the queue is empty before insertion, point real to head
if(rear == -1){ rear = head; }}}// Fetch data from tail
public int deleteLast(a){
int data;
if(isEmpty()){
System.out.println("Queue is empty");
return -1;
}else{
data= array[rear];
// Reset head and real if there is only one element
if(head == rear){
head= -1;
rear = -1;
}else{
rear = (rear + capacity - 1)%capacity;
}
returndata; }}Copy the codeDynamic array implementation of bidirectional queue
Dynamic arrays can dynamically change the size of the array. Here we use multiplication to expand the array.
See how the extension method works:
// Because it is a circular array, there is no simple array copy
private void extendQueue(a){
int newCapacity= capacity*2;
int[] newArray= new int[newCapacity];
// Copy all of them
System.arraycopy(array,0,newArray,0,array.length);
// If rear
if(rear < head){
for(int i=0; i< head; i++){
// reset the data of 0-head
newArray[i]= -1;
// Copy to a new location
newArray[i+capacity]=array[i];
}
// Reset the rear position
rear = rear +capacity;
// Reset capacity and arraycapacity=newCapacity; array=newArray; }}Copy the codeBecause it’s a loop array, we can’t do a simple array copy here, so we need to know where the rear and head are to see if we’re in a loop.
If we enter the loop structure, we need to reset the corresponding field data and copy it into the new array.
The methods for inserting data to the head and deleting data to the tail are the same as the basic queue implementation and are not listed here.
List implementation of bidirectional queues
What’s the problem with using a linked list to implement a two-way queue?
Both head and tail inserts quickly locate the target node. But let’s think about tail deletion.
Tail deletion we need to find the node before the rear node, and place that node in the rear node. This requires us to be able to find its predecessor through the Rear node.
So basic linked lists are no longer enough for us. Here we need to use a bidirectional linked list.
public class LinkedListDeQueue {
/ / the head node
private Node headNode;
/ / rear node
private Node rearNode;
class Node {
int data;
Node next;
Node prev;
//Node's constructor
Node(intd) { data = d; }}public boolean isEmpty(a){
return headNode==null;
}
// From the end of the queue
public void insertLast(int data){
Node newNode= new Node(data);
// Point next of rearNode to the newly inserted node
if(rearNode ! =null){
rearNode.next=newNode;
newNode.prev=rearNode;
}
rearNode=newNode;
if(headNode == null){ headNode=newNode; }}// From the head of the queue
public void insertFront(int data){
if(headNode == null){
headNode= new Node(data);
}else{
Node newNode= newNode(data); newNode.next= headNode; headNode.prev= newNode; headNode= newNode; }}// Delete from team leader
public int deleteFront(a){
int data;
if(isEmpty()){
System.out.println("Queue is empty");
return -1;
}else{
data=headNode.data;
headNode=headNode.next;
headNode.prev=null;
}
return data;
}
// Delete from the queue
public int deleteLast(a){
int data;
if(isEmpty()){
System.out.println("Queue is empty");
return -1;
}else{
data=rearNode.data;
rearNode=rearNode.prev;
rearNode.next=null;
}
returndata; }}Copy the codeEach node in a bidirectional list has two Pointers: next and prev. With these two Pointers, we can quickly locate their next node and their previous node.
Time complexity of bidirectional linked lists
The enQueue and deQueue methods of the above three implementations can almost immediately locate the location of the incoming or outgoing queue, so their time complexity is O(1).
The code address of this article:
learn-algorithm
This article is available at www.flydean.com/13-algorith…
The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!
Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!