Java Tutorial
.
Stacks and queues are linear data structures that follow a particular order to add or remove entities.
In this tutorial, you will be introduced to stack and queue in Java. We will cover the critical concepts of stack and queue in Java, highlighting their practical application, implementations, functionalities, and how to develop stack and queue data structures using classes and objects.
Java uses stacks and queues as its fundamental data structures, but they can also be called classes. Both stacks and queues are linear data structures because elements are stored and accessed sequentially.
Understanding their principles and differences is crucial for effective programming and tackling coding interview questions. Let’s learn more about Java stacks and queues and look at Java stack and queue examples.
A stack in Java is a basic data structure that adheres to the Last-In-First-Out (LIFO) concept. It may be pictured as a stack of things, with the most recent item added being the initial one to be taken away. By allowing actions like push (including an element to the top) and pop (by eliminating and restoring the top element), stacks offer an effective approach to organizing and altering data
In Java, stacks are represented by the Stack class, a subclass of the Vector class.
Example:
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
// Create a stack
Stack<Integer> stack = new Stack<>();
// Push an element onto the stack
int element = 42;
stack.push(element);
// Pop the top element from the stack
int topElement = stack.pop();
System.out.println("Popped element: " + topElement);
// Peek at the top element of the stack
int peekElement = stack.peek();
System.out.println("Top element: " + peekElement);
// Check if the stack is empty
boolean isEmpty = stack.isEmpty();
System.out.println("Is stack empty? " + isEmpty);
// Get the size of the stack
int size = stack.size();
System.out.println("Size of the stack: " + size);
}
}In this example, we first create a stack by declaring a variable of type Stack and use the new keyword to create an instance of the Stack class. You can replace DataType with the desired data type for the elements stored in the stack.
Then, we push an element onto the stack using the push() method to add an element to the top. We are using Integer as the data type for the stack. We set the element to 42 and push it onto the stack.
Finally, we use the pop() method to remove and retrieve the top element from the stack. The removed element is returned by this method, and the result is printed to the console.
Several methods are available to modify and access stack elements in the Java Stack class. Among the most common methods are:
1. push(element): Adds a new element to the stack's top.
2. pop(): Removes and returns the topmost element in the stack.
3. peek(): Returns the topmost stack element without deleting it.
4. empty(): Returns a boolean result that determines if the stack is empty.
5. size(): Gives the stack's element count.
Stacks check for balanced parentheses, match XML and HTML tags, and validate code syntax.
A stack allows the evaluation of expressions, especially infix, postfix, and prefix expressions. A stack can convert infix expressions to postfix or prefix forms.
Stacks are frequently used by backtracking algorithms, including depth-first search (DFS), to retain track of visited nodes and return to earlier stages during exploration.
Here is a real-world application (back-button functionality) of Java stacks:
In this example, the BrowserBackButton class represents the functionality of a browser's back button. The pageStack stack stores the URLs of visited pages. The visitPage() method adds a new page URL to the stack when a page is visited. The goBack() method pops the top URL from the stack and simulates navigating back to the previous page. If the stack is empty, it indicates no pages left to go back to.
In the main() method, we create an instance of BrowserBackButton and simulate visiting different web pages. Then, we call the goBack() method multiple times to simulate pressing the back button and navigating to previous pages. Finally, we try to go back when there are no more pages in the history, which shows the appropriate message.
import java.util.Stack;
public class BrowserBackButton {
private Stack<String> pageStack;
public BrowserBackButton() {
pageStack = new Stack<>();
}
public void visitPage(String url) {
// Add the URL to the stack when a new page is visited
pageStack.push(url);
System.out.println("Visited page: " + url);
}
public void goBack() {
if (!pageStack.isEmpty()) {
String previousPage = pageStack.pop();
System.out.println("Navigating back to: " + previousPage);
} else {
System.out.println("Cannot go back. No pages in history.");
}
}
public static void main(String[] args) {
BrowserBackButton browser = new BrowserBackButton();
// Visit different web pages
browser.visitPage("https://www.example.com");
browser.visitPage("https://www.example.com/page1");
browser.visitPage("https://www.example.com/page2");
// Press the back button to navigate back
browser.goBack();
browser.goBack();
browser.goBack();
browser.goBack(); // Trying to go back when no pages are left
}
}A queue is a basic data structure representing a group of elements in a predetermined sequence. It adheres to the First-In-First-Out (FIFO) principle, which states that the first element added is also the first one taken out. And this is where the difference between stack and queue (in data structure terms) comes into the picture — while queue follows FIFO, stack follows LIFO data structure type.
In Java, we can use the Queue interface to represent a queue. Several classes implement the Queue interface in the Java Collections Framework, such as LinkedList and ArrayDeque.
Example:
import java.util.Queue;
import java.util.LinkedList;
public class QueueExample {
public static void main(String[] args) {
// Create a queue
Queue<Integer> queue = new LinkedList<>();
// Add an element to the queue
int element = 42;
queue.add(element);
// Remove the element from the front of the queue
int frontElement = queue.remove();
System.out.println("Removed element: " + frontElement);
// Peek at the element from the front of the queue
int peekElement = queue.peek();
System.out.println("Front element: " + peekElement);
// Check if the queue is empty
boolean isEmpty = queue.isEmpty();
System.out.println("Is queue empty? " + isEmpty);
// Get the size of the queue
int size = queue.size();
System.out.println("Size of the queue: " + size);
}
}In this example, we first create a queue by declaring a variable of type Queue and use a class that implements the Queue interface. Then, we will use Integer as the data type for the queue. We set the element to the value 42 and add it to the queue using the add() method.
Finally, we will remove the element from the front of the queue using the remove() method to remove and retrieve the element from the front. The removed element is returned by this method, and we print the results to the console.
Java's Queue interface offers several ways to interact with queues. Here are a few of the common methods:
1. add(element): Adds a piece to the rear of the queue.
2. remove(): Removes and returns the element at the front of the queue.
3. isEmpty(): Checks if the queue is empty and returns a boolean value.
4. size(): Returns the number of elements in the queue.
1. Task Scheduling: Tasks are scheduled and managed systematically using queues.
2. Breadth-First Search (BFS): Implementing BFS algorithms for traversing graphs or trees requires queues.
3. Multi-threaded Synchronization: Thread-safe access is made possible through queues, which aid in resource sharing and synchronization across several threads.
Here is a real-world application (task scheduling) of Java queues:
In this example, the TaskScheduler class represents a task scheduling system. The taskQueue queue stores the incoming tasks. The enqueueTask() method adds a new task to the end of the queue. The processTasks() method continuously dequeues and processes tasks from the front of the queue until the queue becomes empty. Each task is simulated by a delay of 1 second.
In the main() method, we create an instance of TaskScheduler and enqueue multiple tasks. Then, we call the processTasks() method to start processing the tasks in the order they were enqueued.
import java.util.Queue;
import java.util.LinkedList;
public class TaskScheduler {
private Queue<String> taskQueue;
public TaskScheduler() {
taskQueue = new LinkedList<>();
}
public void enqueueTask(String task) {
// Enqueue a new task to the end of the queue
taskQueue.add(task);
System.out.println("Enqueued task: " + task);
}
public void processTasks() {
while (!taskQueue.isEmpty()) {
String task = taskQueue.remove();
System.out.println("Processing task: " + task);
// Simulate some processing time
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println("All tasks processed.");
}
public static void main(String[] args) {
TaskScheduler scheduler = new TaskScheduler();
// Enqueue tasks
scheduler.enqueueTask("Task 1");
scheduler.enqueueTask("Task 2");
scheduler.enqueueTask("Task 3");
// Process tasks in the order they were enqueued
scheduler.processTasks();
}
}In Java, queues can be implemented using the java.util.Queue interface or its subclasses. Here are some common types of queues:
1. LinkedList Queue: It provides efficient insertion and removal of components at both ends of the queue
2. ArrayDeque Queue: It provides dynamic array-based operations for adding and removing elements.
3. Priority Queue: It orders elements based on their natural ordering or a custom comparator, allowing for removal based on priority.
4. Blocking Queue: Provides additional blocking and synchronization operations for thread safety.
5. Synchronous Queue: It enables simultaneous element passing by acting as a meeting point between two threads.
Stack | Queue | |
1. | Stack is a data structure in Java. | Queue is also a data structure in Java. |
2. | It stores elements of the same type. | Similar elements are also stored there. |
3. | Both follow a specific order for adding and removing elements. | Both follow a specific order for adding and removing elements. |
4. | It allows adding (push/enqueue) and removing (pop/dequeue). | It also provides methods for adding elements (push/enqueue) and removing elements (pop/dequeue). |
5. | It can be used in various algorithms and applications. | It is also used in many algorithms and programs. |
Stack | Queue | |
1. | Follows the Last-In-First-Out (LIFO) principle. | Follows the First-In-First-Out (FIFO) principle. |
2. | Elements are added and removed from the top (end) of the stack. | Elements are added at the rear (end) and removed from the front (start) of the queue. |
3. | Examples of Stacks include function call stack and undo/redo functionality. | Examples in Queue include task scheduling and message passing. |
4. | Only the top element is accessible and removable at a time. | Both the front and rear elements are accessible and removable. |
5. | There is no easy way to access or eliminate middle-of-the-stack items. | When objects are in the middle of the line, it is difficult to access or remove them. |
Stacks and queues are essential Java data structures with specific functions. Counting function calls, doing undos and redos, and evaluating expressions are popular uses for stacks. Queues, on the other hand, are helpful for sequential data management, message passing, breadth-first search, and job scheduling.
By understanding its features, applications, and implementations, you can use stack and queue in Java to arrange and modify data methodically and efficiently.
1. Are stacks and queues thread-safe in Java?
There are thread-safe substitutes for Java's standard implementations of stacks and queues, such as java.util.Stack and java.util.LinkedList, which are not thread-safe by default.
2. Are there any limitations to the size of a stack or a queue in Java?
In Java, the size of a stack or queue is normally constrained by the amount of memory available on the machine, although certain particular implementations could have additional size restrictions.
3. How do I choose between using a stack or a queue in Java?
Java allows you to use either a stack or a queue depending on the needs of your application and whether you need to retain the order of insertion (queue) or prioritize the order of the items (stack).
Leave a Reply
Your email address will not be published. Required fields are marked *