Introduction
A queue is an abstract data structure that is open on both ends. One end is used to insert or enqueue an element while the other end is used to remove or dequeue the element. there are various techniques to implement a Queue such as Linked List based queue or an array-based queue. The queue is a FIFO – First In First Out data structure.
The Queue Data Structure can be implemented in various ways such as using Arrays or a Linked List. Queue is a famous Linear Data Structure that is used in a variety of applications. It is mainly used to manage Data Flow and Tasks within an application. It is also used in Event-Driven simulations such as Bank Queues, Ticket Queues, Landing queues, or any other Queue simulation. It is also used in Graph-based algorithms for local storage and other intermediate processing. While implementing the queue based on an underlying array, we can insert the new elements at the end of the array and pop from the front of the array.
Example
Create Queue : Queue is Empty
Enqueue 5:
Queue is: 5
Enqueue 7:
Queue is: 5 7
Enqueue 1:
Queue is: 5 7 1
Dequeue: 5
Queue is: 7 1
Enqueue 8:
Queue is: 7 1 8
Enqueue 3:
Queue is: 7 1 8 3
Dequeue: 7
Queue is: 1 8 3
Dequeue: 1
Queue is: 8 3
Enqueue 5:
Queue is: 5
Enqueue 7:
Queue is: 5 7
Enqueue 1:
Queue is: 5 7 1
Dequeue: 5
Queue is: 7 1
Enqueue 8:
Queue is: 7 1 8
Enqueue 3:
Queue is: 7 1 8 3
Dequeue: 7
Queue is: 1 8 3
Dequeue: 1
Queue is: 8 3
Queue Time Complexity
- The Enqueue function is O(N) as we are inserting at the end of the Linked List or we can achieve O(1) by adding tail pointer.
- the Dequeue function is O(1) in the best case (Single element in the queue), otherwise it is O(N) because we have to shift the elements towards the left.
- Peek: The Peek Function takes O(1) time accessing element at the front of the queue.
- Search: The Search is linear os it takes is O(1) in best case and O(N) in average and worst cases.
- Space complexity is O(N) where N is the number of elements stored in the Queue. The memory is dynamically allocated.
Node.java
/**
* The <code>Node</code> Class that will manage the data and reference to the
* next node.
*
* @author CodingHelpLine
* WEB: https://codinghelpline.org
*/
public class Node {
private int data; // data
private Node next; // keep reference to next node.
/**
* Constructor to create a Node with a data assigned to the instance field.
*
* @param data
*/
public Node(int data) {
this.data = data;
this.next = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
* The <code>Node</code> Class that will manage the data and reference to the
* next node.
*
* @author CodingHelpLine
* WEB: https://codinghelpline.org
*/
public class Node {
private int data; // data
private Node next; // keep reference to next node.
/**
* Constructor to create a Node with a data assigned to the instance field.
*
* @param data
*/
public Node(int data) {
this.data = data;
this.next = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
Queue.java
/**
* The <code>Queue</code> Class to implement a Linked List Base Queue.
*
* @author CodingHelpLine
* WEB: https://codinghelpline.org
*/
public class Queue {
// Here we implement the queue.
private Node head;
// count of elements
private int count;
/**
* Default constructor - to setup empty queue
*/
public Queue() {
head = null;
count = 0;
}
/**
* Enqueue at the end of the queue.
*
* O(N) for any insertion
* O(1) if the queue is empty
*
* @param data
*/
public void enqueue(int data) {
Node node = new Node(data);
// Insert at the end of the queue
if(this.isEmpty()) {
head = node;
} else {
// Move to the end of the queue
Node current = head;
while(current.getNext() != null) {
current = current.getNext();
}
current.setNext(node);
}
count++;
}
/**
* Remove from the front and return it.
* O(1)
* Remove from front and return.
*
* @return front element
*/
public int dequeue() {
// check empty
if(this.isEmpty()) {
System.out.println("Queue is empty");
return Integer.MAX_VALUE;
}
int data = head.getData();
head = head.getNext();
count--;
return data;
}
/**
* Check front element of the queue.
*
* O(1)
*
* @return front element
*/
public int peek() {
if(this.isEmpty()) {
return Integer.MAX_VALUE;
}
return head.getData();
}
/**
* Get the number of elements within the queue.
*
* O(1)
*
* @return size of queue
*/
public int size() {
return count;
}
/**
* Check the queue is empty or not.
*
* O(1)
*
* @return indicate queue is empty
*/
public boolean isEmpty() {
return head == null;
}
/**
* Display the Queue.
*
* O(1) Best Case
* O(N) Average and Worst cases.
*
*/
public void print() {
if(this.isEmpty()) {
System.out.println("The Queue is Empty");
return;
}
Node current = head;
System.out.printf("[%d", current.getData());
current = current.getNext();
while(current != null) {
System.out.printf(", %d", current.getData());
current = current.getNext();
}
System.out.println("]");
}
}
* The <code>Queue</code> Class to implement a Linked List Base Queue.
*
* @author CodingHelpLine
* WEB: https://codinghelpline.org
*/
public class Queue {
// Here we implement the queue.
private Node head;
// count of elements
private int count;
/**
* Default constructor - to setup empty queue
*/
public Queue() {
head = null;
count = 0;
}
/**
* Enqueue at the end of the queue.
*
* O(N) for any insertion
* O(1) if the queue is empty
*
* @param data
*/
public void enqueue(int data) {
Node node = new Node(data);
// Insert at the end of the queue
if(this.isEmpty()) {
head = node;
} else {
// Move to the end of the queue
Node current = head;
while(current.getNext() != null) {
current = current.getNext();
}
current.setNext(node);
}
count++;
}
/**
* Remove from the front and return it.
* O(1)
* Remove from front and return.
*
* @return front element
*/
public int dequeue() {
// check empty
if(this.isEmpty()) {
System.out.println("Queue is empty");
return Integer.MAX_VALUE;
}
int data = head.getData();
head = head.getNext();
count--;
return data;
}
/**
* Check front element of the queue.
*
* O(1)
*
* @return front element
*/
public int peek() {
if(this.isEmpty()) {
return Integer.MAX_VALUE;
}
return head.getData();
}
/**
* Get the number of elements within the queue.
*
* O(1)
*
* @return size of queue
*/
public int size() {
return count;
}
/**
* Check the queue is empty or not.
*
* O(1)
*
* @return indicate queue is empty
*/
public boolean isEmpty() {
return head == null;
}
/**
* Display the Queue.
*
* O(1) Best Case
* O(N) Average and Worst cases.
*
*/
public void print() {
if(this.isEmpty()) {
System.out.println("The Queue is Empty");
return;
}
Node current = head;
System.out.printf("[%d", current.getData());
current = current.getNext();
while(current != null) {
System.out.printf(", %d", current.getData());
current = current.getNext();
}
System.out.println("]");
}
}
LinkedQueueApp.java
/**
* Program to test the functionality of Linked List Based Queue Implementation.
*
* @author CodingHelpLine
* WEB: https://codinghelpline.org
*/
public class LinkedQueueApp {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// Object
Queue queue = new Queue();
// Enqueue few numbers
queue.enqueue(2); // [2]
queue.print();
queue.enqueue(9); // [2, 9]
queue.print();
queue.enqueue(18); // [2, 9, 18]
queue.print();
queue.enqueue(3); // [2, 9, 18, 3]
queue.print();
queue.enqueue(11); // [2, 9, 18, 3, 11]
queue.print();
// Removal - dequeue
while(!queue.isEmpty()) {
System.out.printf("Front Element removed: %d%n", queue.dequeue());
queue.print();
}
}
}
* Program to test the functionality of Linked List Based Queue Implementation.
*
* @author CodingHelpLine
* WEB: https://codinghelpline.org
*/
public class LinkedQueueApp {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// Object
Queue queue = new Queue();
// Enqueue few numbers
queue.enqueue(2); // [2]
queue.print();
queue.enqueue(9); // [2, 9]
queue.print();
queue.enqueue(18); // [2, 9, 18]
queue.print();
queue.enqueue(3); // [2, 9, 18, 3]
queue.print();
queue.enqueue(11); // [2, 9, 18, 3, 11]
queue.print();
// Removal - dequeue
while(!queue.isEmpty()) {
System.out.printf("Front Element removed: %d%n", queue.dequeue());
queue.print();
}
}
}
Views: 9