The queue is also an abstract data type or a linear data structure, just like stack data structure. The queue implements FIFO i.e. First In First Out. This means that the elements entered first are the ones that are deleted first.
Serving requests on a single shared resource, like a printer, CPU task scheduling, etc.
In real life scenario, Call Center phone systems use Queues to hold people calling them in order, until a service representative is free.
Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e. First come first served.
A single-lane one-way road, where the vehicle enters first, exits first.
Queues at the ticket windows and bus stops.
CPU task scheduling.
In Java, Queue is an interface that is a part of java.util package. The queue interface extends the Java Collection interface.
public interface Queue<E> extends Collection<E>
As the Queue is an interface, it cannot be instantiated. We need some concrete classes to implement the functionality of the Queue interface. Two classes implement the Queue interface i.e. LinkedList and PriorityQueue.
add - Adds element e to the queue at the end (tail) of the queue without violating the restrictions on the capacity. Returns true if success or IllegalStateException if the capacity is exhausted.
peek - Returns the head (front) of the queue without removing it.
element - Performs the same operation as the peek () method. Throws NoSuchElementException when the queue is empty.
remove - Removes the head of the queue and returns it. Throws NoSuchElementException if the queue is empty.
poll - Removes the head of the queue and returns it. If the queue is empty, it returns null.
Offer - Insert the new element e into the queue without violating capacity restrictions.
size - Returns the size or number of elements in the queue.
To use a queue in Java, we must first import the queue interface as follows:
import java.util.queue;
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
//declare a Queue
Queue<String> str_queue = new LinkedList<>();
//initialize the queue with values
str_queue.add("one");
str_queue.add("two");
str_queue.add("three");
str_queue.add("four");
//print the Queue
System.out.println("The Queue contents:" + str_queue);
}
}
The output will be:
The Queue contents:[one, two, three, four]
We can traverse the queue elements either using the for loop or using an iterator.
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
public class TraverseQueue{
public static void main(String[] args) {
//declare a Queue
Queue<String> LL_queue = new LinkedList<>();
//initialize the Queue
LL_queue.add("One");
LL_queue.add("Two");
LL_queue.add("Three");
LL_queue.add("Four");
//traverse the Queue using Iterator
System.out.println("The Queue elements through iterator:");
Iterator iterator = LL_queue.iterator();
while(iterator.hasNext()){
String element = (String) iterator.next();
System.out.print(element + " ");
}
//use new for loop to traverse the Queue
System.out.println("\n\nThe Queue elements using for loop:");
for(Object object : LL_queue) {
String element = (String) object;
System.out.print(element + " ");
}
}
}
The output will be:
The Queue elements through iterator:
One Two Three Four
The Queue elements using for loop:
One Two Three Four
The following program demonstrate some of the methods in Queue.
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample2 {
public static void main(String[] args) {
Queue<Integer> q1 = new LinkedList<Integer>();
//Add elements to the Queue
q1.add(10);
q1.add(20);
q1.add(30);
q1.add(40);
q1.add(50);
System.out.println("Elements in Queue:"+q1);
//remove () method =>removes first element from the queue
System.out.println("Element removed from the queue: "+q1.remove());
//element() => returns head of the queue
System.out.println("Head of the queue: "+q1.element());
//poll () => removes and returns the head
System.out.println("Poll():Returned Head of the queue: "+q1.poll());
//returns head of the queue
System.out.println("peek():Head of the queue: "+q1.peek());
//print the contents of the Queue
System.out.println("Final Queue:"+q1);
}
}
The output will be:
Elements in Queue:[10, 20, 30, 40, 50]
Element removed from the queue: 10
Head of the queue: 20
Poll():Returned Head of the queue: 20
peek():Head of the queue: 30
Final Queue:[30, 40, 50]
To implement queue using Arrays, we first declare an array that will hold n number of queue elements.
The operations in Queue are:
#1) Enqueue: An operation to insert an element in the queue is Enqueue (function queueEnqueue in the program). For inserting an element at the rear end, we need to first check if the queue is full. If it is full, then we cannot insert the element. If rear < n, then we insert the element in the queue.
#2) Dequeue: The operation to delete an element from the queue is Dequeue (function queueDequeue in the program). First, we check whether the queue is empty. For dequeue operation to work, there has to be at least one element in the queue.
#3) Front: This method returns the front of the queue.
#4) Display: This method traverses the queue and displays the elements of the queue.
The following program shows how to implement queue using arrays.
class Queue {
private static int front, rear, capacity;
private static int queue[];
Queue(int size) {
front = rear = 0;
capacity = size;
queue = new int[capacity];
}
// insert an element into the queue
static void queueEnqueue(int item) {
// check if the queue is full
if (capacity == rear) {
System.out.printf("\nQueue is full\n");
return;
}
// insert element at the rear
else {
queue[rear] = item;
rear++;
}
return;
}
//remove an element from the queue
static void queueDequeue() {
// check if queue is empty
if (front == rear) {
System.out.printf("\nQueue is empty\n");
return;
}
// shift elements to the right by one place uptil rear
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
// set queue[rear] to 0
if (rear < capacity)
queue[rear] = 0;
// decrement rear
rear--;
}
return;
}
// print queue elements
static void queueDisplay()
{
int i;
if (front == rear) {
System.out.printf("Queue is Empty\n");
return;
}
// traverse front to rear and print elements
for (i = front; i < rear; i++) {
System.out.printf(" %d = ", queue[i]);
}
return;
}
// print front of queue
static void queueFront() {
if (front == rear) {
System.out.printf("Queue is Empty\n");
return;
}
System.out.printf("\nFront Element of the queue: %d", queue[front]);
return;
}
}
public class QueueArray {
public static void main(String[] args) {
// Create a queue of capacity 4
Queue q = new Queue(4);
System.out.println("Initial Queue:");
// print Queue elements
q.queueDisplay();
// inserting elements in the queue
q.queueEnqueue(10);
q.queueEnqueue(30);
q.queueEnqueue(50);
q.queueEnqueue(70);
// print Queue elements
System.out.println("Queue after Enqueue Operation:");
q.queueDisplay();
// print front of the queue
q.queueFront();
// insert element in the queue
q.queueEnqueue(90);
// print Queue elements
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
System.out.printf("\nQueue after two dequeue operations:");
// print Queue elements
q.queueDisplay();
// print front of the queue
q.queueFront();
}
}
The output will be:
Initial Queue:
Queue is Empty
Queue after Enqueue Operation:
10 = 30 = 50 = 70 =
Front Element of the queue: 10
Queue is full
10 = 30 = 50 = 70 =
Queue after two dequeue operations: 50 = 70 =
Front Element of the queue: 50
LinkedListQueue.java
class LinkedListQueue {
private Node front, rear;
private int queueSize; // queue size
//linked list node
private class Node {
int data;
Node next;
}
//default constructor- initially front & rear are null; size=0; queue is empty
public LinkedListQueue(){
front = null;
rear = null;
queueSize = 0;
}
//check if the queue is empty
public boolean isEmpty(){
return (queueSize == 0);
}
//Remove item from the front of the queue.
public int dequeue(){
int data = front.data;
front = front.next;
if (isEmpty()) {
rear = null;
}
queueSize--;
System.out.println("Element " + data+ " removed from the queue");
return data;
}
//Add data at the rear of the queue.
public void enqueue(int data){
Node oldRear = rear;
rear = new Node();
rear.data = data;
rear.next = null;
if (isEmpty()) {
front = rear;
}
else {
oldRear.next = rear;
}
queueSize++;
System.out.println("Element " + data+ " added to the queue");
}
//print front and rear of the queue
public void print_frontRear() {
System.out.println("Front of the queue:" + front.data
+ " Rear of the queue:" + rear.data);
}
}
QueueExample3.java
public class QueueExample3{
public static void main(String a[]){
LinkedListQueue queue = new LinkedListQueue();
queue.enqueue(6);
queue.enqueue(3);
queue.print_frontRear();
queue.enqueue(12);
queue.enqueue(24);
queue.dequeue();
queue.dequeue();
queue.enqueue(9);
queue.print_frontRear();
}
}
The output will be:
Element 6 added to the queue
Element 3 added to the queue
Front of the queue:6 Rear of the queue:3
Element 12 added to the queue
Element 24 added to the queue
Element 6 removed from the queue
Element 3 removed from the queue
Element 9 added to the queue
Front of the queue:12 Rear of the queue:9
Given the following algorithm:
1. For each test case, read a line of input and do the following:
a. if it is a letter, push onto a stack
b. if it is an asterisk
if there is item in the stack
pop, then enqueue to a queue
2. Output content of the stack and queue as shown in the sample output