Various operations on the Queue using Stack in Java
The Java Collections Framework's core data structures are the Stack and Queue. They are used to store and retrieve identical data in a presentation sequence. These two linear data structures are Stack and Queue.
The Last In First Out (LIFO) principle governs the Stack functions. Queuing employs the First In First Out (FIFO) principle.
Java Stack
A stack is a collection of elements that are added and removed in the sequence of "Last In First Out" (LIFO). The name "stack" comes from a stack of plates. An immovable plate in the middle of the Stack cannot be moved. Therefore, we remove plates from the top of the Stack as we require them and add plates by pushing them up to the top of the Stack.
Components are likely to be positioned near the top of the Stack, where they may be viewed and removed. The center of the Stack cannot be added, removed, or recovered.
A Stack is a basic data structure. Changes are pushed into the Stack as you make them. Each modification is kept in a stack. They have several applications. The undo function in text editors is one example of such use. When you undo anything, the most recent action is displayed.
You must also be familiar with browsers' Back and Forward buttons. The use of stacks is also involved in these procedures.
More than push() and pop, there are other actions we may carry out on the Stack (). Using the methods peek() and size(), we can determine the size of the Stack and view the topmost element in the Stack. Additionally, we can use the empty() function to see if the Stack is empty.
The best way to implement stacks in Java
The Java collections framework's Stack Class provides access to the features of the Stack Data structure. The Stack class is an extension of the Vector class.
Importing the Java.util. A stack package is the first step. This package includes the Stack Data Structure, which enables us to establish a stack, add data, and utilize all of the Stack's other features.
import java.util.Stack;
Let's experiment with stack creation. Stack is a DataType, similar to how int is used for integer variables. The variable has the name "stacks". The basic syntax for declaring the Stack is listed below.
The object may be a character, string, Integer, float, or other type. Only one kind of data may be stored in the Stack. Text, integers, and other objects cannot be stored in the same Stack. We use the Integer datatype to store numbers and the String datatype to store text.
Stack<Object> stacks;
By using <variable name> = new Stack>(), the Stack is initialized. The Stack is currently ready for usage.
stacks = new Stack<>();
Program
Stack< Integer> stack = new Stack <>(); //Program using the integer data type stack.
Methods in the Stack Class
1. push(y): stacks element y and moves it to the top.
<stack_name>.push(<varible_name>);
Explanation
stacks.push(32);
2. pop(): top element of the Stack is taken out and returned. A warning is issued if the Stack is empty (EmptyStackException).
<stack name>.pop();
Explanation
stacks.pop();
3. peek(): without deleting it, returns the Stack's highest member. If the Stack is empty, an exception is thrown.
<stack name>.peek();
Explanation
stacks.peek();
4. size(): returns the number of stack items.
<stack name>.size();
Explanation
stacks.size();
5. empty(): A Boolean in the response indicates whether the Stack is empty.
<stack name>.empty();
Explanation
stacks.empty();
Java implementation of the Stack using an array
- We are utilizing classes and methods to implement our Stack. The functionality we observed in the instances mentioned above will be present. Since we use Arrays to hold our data, we gave our class the name ArrayStack.
- Our class is Generic since E is enclosed in angular brackets (>). It is not just restricted to integers. It allows the user to use any form of data. We may create a stack using the String, Integer, or Character datatypes.
- The values will be stored in an array called data, and topIndex will be used to monitor a top component.
- The size() function returns topIndex+1, which is the size of the Stack.
- The empty() function determines if the Stack is empty if the topIndex is at -1.
- The push() function determines whether the Stack is full first. If not, it adds a new element to the Stack and raises the topIndex by one unless it is full.
- The data[topIndex] value is returned by the peek() function as the Stack's topmost member. The EmptyStackException is raised when the Stack is empty.
- This function is comparable to the pop() function, which removes the top element, returns its value, and reduces topIndex by one while throwing EmptyStackException if the Stack is empty.
Queue.java
/* The Queue is implemented with a fixed-length array. */
import java.util.*;
public class Queue < E > {
private E[] data; // generic array for storing
// datatypes
private int frontIndex;
private int Sizeofqueue;
public Queue (int capacity) { // creates a queue with a particular capacity
data = (E[]) new Object[capacity]; // safe casting; compiler might issue a warning
Sizeofqueue = 0; // current number of components
frontIndex = 0; // the front element's index
}
public Queue () {
this(1000);
} // creates a queue with the minimal capacity
// methods
/* the number of queue elements is returned. */
public int size() {
return Sizeofqueue;
}
/* determines if the Queue is empty.*/
public boolean isEmpty() {
return (Sizeofqueue == 0);
}
/* places a new element at the end of the line. */
public void enqueue(E e) throws IllegalStateException {
if (Sizeofqueue == data.length) throw new IllegalStateException("Queue is full");
int avail = (frontIndex + Sizeofqueue) % data.length; // utilise modular arithmetic
data[avail] = e;
Sizeofqueue++;
}
/* Returns the first member of the Queue but does not delete it (null if empty).*/
public E first() throws IllegalStateException {
if (Sizeofqueue == data.length) throw new IllegalStateException("Queue is empty");
return data[frontIndex];
}
/* Returns the first member of the Queue but does not delete it (null if empty). */
public E dequeue() throws IllegalStateException {
if (Sizeofqueue == data.length) throw new IllegalStateException("The queue is empty.");
E address = data[frontIndex];
data[frontIndex] = null; // dereference to help garbage collection
frontIndex = (frontIndex + 1) % data.length;
Sizeofqueue--;
return address;
}
public static void main(String[] args) {
Queue queue = new Queue ();
queue.enqueue(24); //p
System.out.println("Element in the front : " + queue.first()); //q
System.out.println("Front element has been removed : " + queue.dequeue()); //r
System.out.println("The queue is empty. : " + queue.isEmpty()); //s
queue.enqueue(52); //t
queue.enqueue(84); //u
System.out.println("The length of the queue : " + queue.size()); //v
System.out.println("A front end component has been removed. : " + queue.dequeue());
//w
}
}
Output
Queue implementation in Java with LinkedList
- For LinkedList-based implementation, the Queueinlinkedlist class was developed. We mention frontNode, rearNode, and queueSize.
- The queueSize parameter is initialised to 0, and the front and rear nodes are initialised to null.
- Dequeue() and first() actions produce an exception if queueSize is zero since there is no data in the Queue. Since we are using LinkedList, there is no constraint on the size of the Queue.
- The rearNode is stored in oldRear when an element is placed into a queue, and the new element is then appended to the rearNode. Finally, rearNode is changed to oldRear.next. As a result, we include a component in Queue's back end.
- While deleting an element, the value of frontNode is stored in a temporary variable. The method sets frontNode to frontNode.next and returns its value.
- frontNode's value is returned by the first() function. The queueSize is returned by the size() function, and the isEmpty() method determines whether the queueSize is 0.
Queueinlinkedlist.java
import java.util.*;
public class Queueinlinkedlist {
private Node frontNode, rearNode;
private int queueSize; // queue length
// an element in a linked list
private class Node {
int data;
Node next;
}
// Initial values for forward and rear in the default constructor are null.; size=0; empty queue
public Queueinlinkedlist() {
frontNode = null;
rearNode = null;
queueSize = 0;
}
//Assure that the Queue is empty.
public boolean isEmpty() {
return (queueSize == 0);
}
// From the head of the line, the item should be removed.
public int dequeue() throws IllegalStateException {
if (isEmpty()) throw new IllegalArgumentException("Empty queue");
int data = frontNode.data;
frontNode = frontNode.next;
if (isEmpty()) {
rearNode = null;
}
queueSize--;
return data;
}
public int first() throws IllegalStateException {
if (isEmpty()) throw new IllegalArgumentException("Empty queue");
return frontNode.data;
}
public int size() {
return queueSize;
}
// You should add data at the end of the queue.
public void enqueue(int data) {
Node oldRear = rearNode;
rearNode = new Node();
rearNode.data = data;
rearNode.next = null;
if (isEmpty()) {
frontNode = rearNode;
} else {
oldRear.next = rearNode;
}
queueSize++;
}
public static void main(String[] args) {
Queueinlinkedlist queue = new Queueinlinkedlist();
queue.enqueue(24);
System.out.println("Element in the front : " + queue.first());
System.out.println("Front element has been deleted : " + queue.dequeue());
System.out.println("Empty queue: " + queue.isEmpty());
queue.enqueue(52);
queue.enqueue(84);
System.out.println("The length of the queue : " + queue.size());
System.out.println("Front element has been deleted : " + queue.dequeue());
}
}
Output:
Java applications for queues
- Operating systems maintain a queue of processes, one of which is ready to start and the rest of which will be processed.
- The operating system schedules the tasks using priority queues.