Introduction to Stack
A stack is a collection of things entered and discarded in the order of last in, first out (LIFO). The term "stack" comes from a stack of plates. So, when we require a dish, we take it (pop) from the top of the stack, and when we wish to add a plate, we also put it (push) at the top. We are unable to add or remove a dish from the center of the stack.
Elements are likely to be added to the top of the stack and can be seen or removed from the top. The middle of the stack cannot be accessed, removed, or added to.
A stack is a fundamental data structure. They are utilized in a variety of applications. The undo mechanism in text editors is one such application. A stack holds all of the modifications. When you undo something, the most recent action is displayed. When you make modifications, they are pushed onto the stack.
You may have noticed the Back and Forward buttons on browsers. Stacks are also used for these tasks.
Besides push() and pop(), we can conduct various operations on the stack. Using peek(), we can see the top piece on the stack, and size() tells us how big the stack is. We may also use the empty() method to see if the stack is empty.
How Do Stacks Work in Java?
The Stack Class in the Java collections framework offers the functionality of the Stack Data structure. The Stack class is an extension of the Vector class.
First, we must import the Java.util.Stack package. This package contains a stack Data Structure, allowing us to create a stack, insert data into it, and use all its other functions.
import java.util.Stack;
Let's examine how we may make a stack. The general syntax for declaring the stack is listed below. Stack is the DataType, much as int is the DataType for the Integer variable. The variable is called **stacks**.
The object type can be Integer, String, Character, Float, etc. The stack can only store one type of data. Text, numbers, and other data cannot be stored on the same stack. While storing numbers, we use the Integer datatype; while keeping text, we use the String datatype.
Stack<Object> stacks;
We use <variable_name> = new stack>() to initialize the stack. The stack is now ready for use.
stacks = new Stack<>();
Example:
Stack<Integer> stack = new Stack<>();
Methods in Java Stack Class
1. push(e): Adds element e to the stack's top.
Syntax:
push(e): Adds element e to the stack's top.
Example:
stacks.push(89);
2. pop(): Removes and returns the stack's top member. If the stack is empty, an exception (EmptyStackException) is thrown.
Syntax:
<stack_name>.pop();
Example:
stacks.pop();
3. peek(): Returns the stack's top member without removing it. If the stack is empty, an exception is thrown.
Syntax:
<stack_name>.peek();
Example:
stacks.peek();
4. size(): This function returns the number of elements in the stack.
Syntax:
<stack_name>.size();
Example:
stacks.peek();
5. empty(): This function returns a Boolean indicating whether or not the stack is empty.
Syntax:
<stack_name>.empty();
Example:
stacks.empty();
Implementation of Stack Using Array in Java
We're creating our stack using classes and methods. It will have the same functionality as the examples above. Because we are storing our data in an array, we named our class ArrayStack.
E defines generic in Angular brackets (>). It allows the user to use any form of data. We can construct a stack of String, Integer, or Character datatypes. It is not restricted to simply Integer values.
We declare a data array to contain the values and a topIndex array to keep track of the top element.
There are two constructor methods, one with user-defined capacity and the other with default capacity. For stacks with no ability specified, the default array capacity is 1000. The top index has been set to -1. In the constructor method, we initialize the data array and topIndex.
The size() method returns the stack's size, which is topIndex+1.
The empty() method determines whether the topIndex is -1, indicating that the stack is empty.
The push() method initially determines whether the stack is complete. If it is full, an Exception is thrown; otherwise, an element is added to the stack, and the topIndex is increased by one.
The peek() method returns the stack's topmost element, data[topIndex]. If the stack is empty, an EmptyStackException is thrown.
Similarly, the pop() method throws an EmptyStackException if the stack is empty or removes the top element, returns its value, and reduces topIndex by one.
Example Code:
import java.util.*;
public class ArrayStack < E > {
public static final int CAPACITY = 1000;
private int topIndex;
private E[] data;
public ArrayStack() {
this(CAPACITY);
}
public ArrayStack(int capacity) {
topIndex = -1;
data = (E[]) new Object[capacity];
}
public int size() {
return (topIndex + 1);
}
public boolean empty() {
return (topIndex == -1);
}
public void push(E e) throws IllegalStateException {
if (size() == data.length) throw new IllegalStateException("Stack is full");
data[++topIndex] = e; // increment topIndex before storing new item
}
public E peek() throws EmptyStackException {
if (empty()) throw new EmptyStackException();
return data[topIndex];
}
public E pop() throws EmptyStackException {
if (empty()) throw new EmptyStackException();
E answer = data[topIndex];
data[topIndex] = null; // dereference to help garbage collection
topIndex--;
return answer;
}
public static void main(String args[]) {
ArrayStack < Integer > mystack = new ArrayStack<>();
mystack.push(9); //a
mystack.push(3); //b
mystack.push(8); //c
System.out.println("The element at the top is:" + mystack.peek());
System.out.println("The element out is: " + mystack.pop());
System.out.println("The size of the stack is: " + mystack.size());
System.out.println("The element out is: " + mystack.pop());
System.out.println("The element at the top is: " + mystack.peek());
mystack.push(10); //i
System.out.println("Is Stack empty : " + mystack.empty()); }
}
Output:
The element at the top is:8
The element output is: 8
The size of the stack is: 2
The element output is : 3
The element at the top is: 9
Is stack empty: false
Benefits of using Stack in Java
Using a stack in Java provides various advantages, making it a handy and fast data structure for managing collections of elements in the Last-In-First-Out (LIFO) sequence. Some of the benefits of using a stack in Java are as follows:
Stacks often feature constant-time (O(1)) insertion and removal operations, making them efficient for managing collections of elements with frequent insertion and removal operations. Elements are inserted at the top of the stack and removed from the top, which may be done constantly regardless of the stack size.
Stacks can be used to implement browser history functionality, where visited URLs are put onto the stack when seen and popped from when the user wants to return. This provides for more effective browsing history and navigation management.
Stacks can be created using arrays or linked lists, allowing for bespoke implementation based on individual application requirements or limitations. This allows for greater flexibility in developing stack processes or functionality based on the application's demands.
Stack in Java Applications
A stack is a linear data structure in Java that follows the Last-In-First-Out (LIFO) principle, which states that the element put last is the first to be removed. Because of their simplicity and efficiency, stacks are widely employed in a variety of applications. Stacks are commonly used in the following Java applications:
Stacks can be used to evaluate arithmetic expressions and postfix expressions. A stack, for example, can contain operators and aid in their precedence and associativity when converting an infix arithmetic statement to a postfix expression.
Stacks can be used to examine expressions for balanced brackets. They can validate expression syntax by correctly matching parentheses, brackets, and brackets.
When a method in Java is called, a new frame on the function call stack is produced to store local variables and other pertinent information. The stack controls the sequence of method calls and their return values, ensuring that when a method completes execution, the correct return address is used.
Introduction to Queue
You must have waited in the queue to turn in your homework to your teacher or in a voting queue. How does it function? The standing individual submits the assignment first and moves to the front of the queue.
The same is true for our Queue data structure in Java. The first piece added to the queue is also removed first. No element may be deleted from the back end or the center of the queue. Furthermore, no element can be inserted from the front or any other place; it must only be added from the back. The first-in, first-out (FIFO) concept is another name for this.
A queue is a collection of objects added to the list's back end and eliminated from the front end. In Java, we can also execute various other actions on a queue. We can observe the element at the front end, determine the queue size, and determine whether the queue is empty.
How Does a Queue Work in Java?
The Queue interface in Java is found in the **java.util** package and extends the Collection Framework. Because Queue is an Interface, it requires a concrete class for declaration, such as LinkedList, PriorityQueue, and so on.
First, we'll pull the queue from the Java Collections Framework. This allows us to declare a queue.
import java.util.Queue;
The queue is a type of data. Our queue's variable name is a queue. This is the queue's declaration. The data type is the object. The queue's elements must all be of the same data type. It could be an integer, a float, a string, a character, or something else.
Queue<Object> queue;
<variable_name >= new LinkedListQueue(); creates the queue. The queue can now store, retrieve, and manipulate data.
queue = new LinkedListQueue<Obj>();
Example:
Queue<Character> queue = new LinkedListQueue<Character>();
Note: Character DataType is utilized in this case. String, Integer, Double, and other data types can also be utilized.
Queue Implementation in Java Using Array
The following section of the article lets us look at the methods for implementing queues in Java.
Using an array, we will now create our class and methods to establish our queue. We have also implemented ArrayQueue as a generic class in the code below. As a result, our queue can handle a variety of data formats.
FrontNode and queueSize were specified as variables. We establish two constructor methods, one with fixed capacity and one with user-defined capacity, just like the stack. We set frontNode and queueSize here.
The index of the back end is given by frontIndex+queueSize.
The enqueue() method first determines whether the queue is full. If it is filled, an exception is thrown. If there is room, it adds the element at the back end and increases the queue size.
The dequeue() method removes a front-end element and decreases the queueSize. If the queue is empty, an Exception is thrown.
The first() method returns the element at the front index and throws an exception if the queue is empty.
Even if there is just one element in the queue, it is not at index 0. Taking (fronIndex+1)%data as an example.length() in dequeue() and (frontIndex+queueSize) in enqueue(), use all of the array's space before declaring it complete.
Example Code:
import java.util.*;
public class ArrayQueue < E > {
private E[] data;
private int frontIndex;
private int queueSize;
public ArrayQueue(int capacity) {
data = (E[]) new Object[capacity];
queueSize = 0;
frontIndex = 0;
}
public ArrayQueue() {
this(1000);
}
public int size() {
return queueSize;
}
public boolean isEmpty() {
return (queueSize == 0);
}
public void enqueue(E e) throws IllegalStateException {
if (queueSize == data.length) throw new IllegalStateException("Queue is full");
int avail = (frontIndex + queueSize) % data.length; // use modular arithmetic
data[avail] = e;
queueSize++;
}
public E first() throws IllegalStateException {
if (queueSize == data.length) throw new IllegalStateException("Queue is empty");
return data[frontIndex];
}
public E dequeue() throws IllegalStateException {
if (queueSize == data.length) throw new IllegalStateException("Queue is empty");
E answer = data[frontIndex];
data[frontIndex] = null; // dereference to help garbage collection
frontIndex = (frontIndex + 1) % data.length;
queueSize--;
return answer;
}
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue();
queue.enqueue(18);
System.out.println("Here element at front : " + queue.first());
System.out.println("Here element removed from front : " + queue.dequeue());
System.out.println("Here queue is Empty : " + queue.isEmpty());
queue.enqueue(79);
queue.enqueue(90);
System.out.println("Here size of the queue : " + queue.size());
System.out.println("Here element removed from front end : " + queue.dequeue());
}
}
Output:
Here element at front:
18
Here element removed from front: 18
Here queue is Empty: true
Here size of the queue: 2
Here element removed from front end: 79
Queue Types in Java
· Circular Queue: The last place in a circular queue is linked back to the first position.
· Input Restricted Queue: Input can only be taken from the back end, and elements can be deleted from both ends.
· Output Restricted Queue: The output can only come from the front end, although elements can come from either end.
· Doubly-ended Queue: Elements can be inserted and withdrawn from both ends of the queue, front and back.
· Priority Queue: A Priority Queue is a collection of components associated with a specific sequence.
Queue in Java Applications
A queue is a linear data structure in Java that adheres to the First-In-First-Out (FIFO) principle, which states that the first added element is the first to be withdrawn. Queues are commonly utilized in a variety of applications to manage components sequentially. Here are some popular queue applications in Java:
Message Queues: Queues can be used to build message queues in distributed systems, allowing numerous processes or threads to communicate by delivering messages to a standard queue. Messages can be added to the queue's end by one process/thread and removed from the front by another, allowing for asynchronous communication and decoupling of sender and receiver.
Task Queues: In Java, Queues can manage a queue of tasks or jobs that must be completed in a specific order. In multi-threaded applications or thread pools, for example, a queue can hold tasks submitted for execution, and threads can retrieve jobs from the queue individually for processing.
Print Spooling: Print spooling can be implemented using queues, in which print jobs are added to a queue and processed in the order they are added. This enables numerous print jobs to be queued and printed one at a time, minimizing congestion and conflicts between multiple print requests.
Benefits of using Queue in Java
A queue in Java has various advantages that make it a valuable and efficient data structure for managing collections of elements in a sequential sequence according to the First-In-First-Out (FIFO) principle. Some of the advantages of using a queue in Java are as follows:
Queues ensure that elements are processed in the order they are added, according to the FIFO principle. This makes queues appropriate for instances where processing order is important, such as message queues, task queues, and request queues. Queues enable organized and sequential processing of elements, guaranteeing that they are processed in the same sequence in which they are added.
Because queues may be quickly extended to handle huge quantities of elements, they are ideal for applications requiring a high rate of incoming requests or tasks. Queues can be implemented using dynamic data structures like linked lists, which can grow and shrink as needed, allowing for efficient memory management and scalability.
Queues can be utilized in a wide range of applications and scenarios, from simple to complicated use cases. They can be used to manage elements of any data type, providing flexibility in dealing with various forms of data. Queues can also be used in conjunction with other data structures or algorithms to achieve more complicated features, such as priority queues or circular queues.
Key Points to Remember
The Stack and Queue data structures are based on fundamental data structures such as an Array or a Linked List.
The Java Collection API includes stack and queue implementations.
The add() and remove() procedures inherited from Collection are supported by the Queue data structure, although they produce exceptions, making them less user-friendly. Thus, Queue methods are employed; they return unique values such as null in unusual circumstances.
Note: Because Stack is a Class and Queue is an Interface, the queue must be declared and initialized with a concrete class.
Conclusion
Finally, stacks and queues are critical Java data structures that efficiently organize collections of elements in precise order. Stacks adhere to the Last-In-First-Out (LIFO) concept, which states that the most recently added element is the first to be removed, whereas queues adhere to the First-In-First-Out (FIFO) principle, which states that the first element added is the first to be released.
Stacks and queues are used in various Java applications, including expression evaluation, parenthesis matching, function call stacks, undo/redo capabilities, browser history, graph traversal, compiler implementations, and many others. They offer efficient solutions for managing components in sequential order, enabling efficient task processing, managing communication across processes or threads, and implementing algorithms in various fields.
Thus, stacks and queues are fundamental data structures in Java that have numerous applications in various areas of software development, providing efficient and effective solutions for managing elements in specific orders and allowing a wide range of functionalities and algorithms to be easily implemented.
Comments