In this article, we will explore Stack and Queue Data Structures in great details. We will first understand the Stack and Queue Data Structures, then look into the key differences between Stack and Queue. Finally, we will discuss the various use-cases of Stack and Queue. So, let’s get started.
What are Stack and Queue in Data Structure ?
Let’s first understand Stack.
What is Stack ?
Stack follows LIFO ie., Last In First Out. In this data structure the elements are arranged in such a way that the last element added will be the first one to pop out of it. In a stack, elements are added and removed from the same end, referred to as the “Top.”
Various operations of a Stack
A stack is a simple data structure that supports a few basic operations:
- Push: This operation adds an element to the top of the stack. The newly added element becomes the new top of the stack.
- Pop: This operation removes the top element from the stack. The element that was previously below the top element becomes the new top.
- Peek (or Top): This operation retrieves the top element of the stack without removing it. It allows you to examine the element at the top without altering the stack’s structure.
- IsEmpty: This operation checks whether the stack is empty or not. If there are no elements in the stack, this operation will return true; otherwise, it returns false.
- Size: This operation returns the number of elements currently present in the stack.
In-Built Java Stack Classes
In Java, you can work with stacks using the built-in java.util.Stack class or java.util.Deque interface, which offers stack operations as well as other functionality.
Using java.util.Stack:
The Stack class is a subclass of Vector and provides methods for the basic stack operations.
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
// Pushing elements onto the stack
stack.push(10);
stack.push(20);
stack.push(30);
// Popping elements from the stack
int poppedElement = stack.pop(); // Removes and returns the top element
// Peeking at the top element without removing it
int topElement = stack.peek();
// Checking if the stack is empty
boolean isEmpty = stack.isEmpty();
// Getting the size of the stack
int size = stack.size();
}
}
Using java.util.Deque (LinkedList):
The LinkedList class implements the Deque interface, which provides stack operations. This approach is more flexible as you can use other methods from the Deque interface if needed.
import java.util.Deque;
import java.util.LinkedList;
public class DequeStackExample {
public static void main(String[] args) {
Deque<Integer> stack = new LinkedList<>();
// Pushing elements onto the stack
stack.push(10);
stack.push(20);
stack.push(30);
// Popping elements from the stack
int poppedElement = stack.pop(); // Removes and returns the top element
// Peeking at the top element without removing it
int topElement = stack.peek();
// Checking if the stack is empty
boolean isEmpty = stack.isEmpty();
// Getting the size of the stack
int size = stack.size();
}
}
Building Custom Stack: Using Array or ArrayList
You can create a custom stack implementation using either an array or an ArrayList in Java. Here’s how you can build a basic stack using both approaches:
Custom Stack using Array:
public class CustomArrayStack<T> {
private Object[] stackArray;
private int size;
private int top;
public CustomArrayStack(int capacity) {
stackArray = new Object[capacity];
size = capacity;
top = -1;
}
public void push(T item) {
if (top == size - 1) {
throw new IllegalStateException("Stack is full");
}
stackArray[++top] = item;
}
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return (T) stackArray[top--];
}
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return (T) stackArray[top];
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
public static void main(String[] args) {
CustomArrayStack<Integer> stack = new CustomArrayStack<>(5);
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println(stack.pop()); // Output: 30
System.out.println(stack.peek()); // Output: 20
System.out.println(stack.size()); // Output: 2
}
}
Custom Stack using ArrayList:
import java.util.ArrayList;
public class CustomArrayListStack<T> {
private ArrayList<T> stackList;
public CustomArrayListStack() {
stackList = new ArrayList<>();
}
public void push(T item) {
stackList.add(item);
}
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stackList.remove(stackList.size() - 1);
}
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stackList.get(stackList.size() - 1);
}
public boolean isEmpty() {
return stackList.isEmpty();
}
public int size() {
return stackList.size();
}
public static void main(String[] args) {
CustomArrayListStack<String> stack = new CustomArrayListStack<>();
stack.push("Apple");
stack.push("Banana");
stack.push("Cherry");
System.out.println(stack.pop()); // Output: Cherry
System.out.println(stack.peek()); // Output: Banana
System.out.println(stack.size()); // Output: 2
}
}
Applications of Stack
Here are some important applications of stacks:
- Function Call Management: Stacks are used in programming languages to manage function calls, storing information about the calling function and allowing the program to return to the correct execution point after the called function completes.
- Expression Evaluation: Stacks play a crucial role in evaluating arithmetic expressions, converting infix expressions to postfix or prefix notation, and then calculating the result.
- Undo Functionality: Stacks can be used to implement undo functionality in applications. Each action can be stored on the stack, allowing the user to reverse actions in the reverse order they were performed.
- Balancing Parentheses: Stacks are used to check and enforce the balanced usage of parentheses, braces, and brackets in code or expressions.
- Backtracking Algorithms: Many backtracking algorithms use stacks to keep track of choices and alternatives, allowing efficient exploration of potential solutions.
- Memory Management: Stacks are used in memory management systems to keep track of allocated memory blocks and their deallocation.
- Parsing and Syntax Analysis: Stacks are used in compilers and parsers to manage and analyze the structure of programming languages, ensuring correct syntax and semantics.
- Depth First Search (DFS): DFS traversal algorithms, including maze-solving and graph traversal, often utilize stacks to manage the exploration of nodes.
- Algorithmic Problem Solving: Stacks can be used in solving problems involving pattern matching, pattern recognition, and rule-based decisions.
Now, let’s look into Queue.
What is Queue ?
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle.
Various Operations of a Queue
In a queue, elements are added at the back (also called the “rear” or “tail”) and removed from the front (also called the “front” or “head”). The element that has been in the queue the longest is the first one to be removed.
The enqueue operation adds an element to the back of the queue, while the dequeue operation removes the front element.
In-Built Java Queue Classes
Java provides several built-in classes and interfaces for implementing queues. Some of the commonly used ones are:
java.util.QueueInterface: This is the base interface for all queue implementations in Java. It provides methods likeadd,offer,remove,poll,element, andpeek. Classes that implement this interface include:java.util.LinkedList: Implements a doubly-linked list, which can be used as a queue.java.util.PriorityQueue: Implements a priority queue, where elements are ordered based on their natural ordering or a provided comparator.
java.util.ArrayDequeClass: This class implements theDequeinterface, which extendsQueue. It can be used as both a queue and a stack. It provides methods likeaddFirst,addLast,removeFirst,removeLast,offerFirst,offerLast,pollFirst, andpollLast.java.util.concurrent.ArrayBlockingQueueClass: This is a bounded blocking queue implementation that uses an array to store elements. It’s part of the Java Concurrency Framework and is suitable for concurrent applications.java.util.concurrent.LinkedBlockingQueueClass: This is an unbounded blocking queue implementation that uses linked nodes to store elements. It’s part of the Java Concurrency Framework and can be used for producer-consumer scenarios.java.util.concurrent.PriorityBlockingQueueClass: This is a blocking priority queue implementation that can be used in concurrent applications. It orders elements based on their natural ordering or a provided comparator.java.util.concurrent.ConcurrentLinkedQueueClass: This class implements a non-blocking, thread-safe queue based on linked nodes. It’s designed for high-concurrency scenarios.java.util.concurrent.DelayQueueClass: This class implements a blocking queue where elements are ordered based on their expiration times. It’s often used for scheduling delayed tasks.
Building Custom Queue in Java
Here’s an example of how you can build a custom queue in Java using an Array as the underlying data structure:
class Queue {
int front, rear, size;
int capacity;
int array[];
public Queue(int capacity) {
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
array = new int[this.capacity];
}
// Queue is full when size becomes equal to the capacity
boolean isFull(Queue queue) {
return (queue.size == queue.capacity);
}
// Queue is empty when size is 0
boolean isEmpty(Queue queue) {
return (queue.size == 0);
}
// Method to add an item to the queue.
// It changes rear and size
void enqueue(int item) {
if (isFull(this)) {
return;
}
this.rear = (this.rear + 1) % this.capacity;
this.array[this.rear] = item;
this.size = this.size + 1;
System.out.println(item + " enqueued to queue");
}
// Method to remove an item from queue.
// It changes front and size
int dequeue() {
if (isEmpty(this)) {
return Integer.MIN_VALUE;
}
int item = this.array[this.front];
this.front = (this.front + 1) % this.capacity;
this.size = this.size - 1;
return item;
}
// Method to get front of queue
int front() {
if (isEmpty(this)) {
return Integer.MIN_VALUE;
}
return this.array[this.front];
}
// Method to get rear of queue
int rear() {
if (isEmpty(this)) {
return Integer.MIN_VALUE;
}
return this.array[this.rear];
}
public static void main(String[] args) {
Queue queue = new Queue(1000);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
System.out.println(queue.dequeue() + " dequeued from queue\n");
System.out.println("Front item is " + queue.front());
System.out.println("Rear item is " + queue.rear());
}
}Output10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 40Applications of a Queue
Here are some important applications of queues:
- Task Scheduling: Queues are used in task scheduling algorithms, where tasks or processes are scheduled to run based on their arrival time or priority.
- Breadth-First Search (BFS): BFS traversal in graph algorithms uses queues to explore nodes level by level, ensuring that nodes at a particular level are processed before moving to the next level.
- Print Job Management: In printer systems, queues are used to manage print jobs. Print requests are placed in a queue and processed in the order they were received.
- Call Center Systems: Queues are utilized in call center systems to hold incoming calls in line until they can be answered by available agents, following the principle of first-come-first-served.
- Buffering: Queues are used as buffers to temporarily hold data or requests, ensuring smoother communication between systems with varying speeds or workloads.
- Bounded Resources Management: In scenarios with limited resources (like thread pools), queues are used to manage access to these resources, preventing resource exhaustion and facilitating fair allocation.
- Simulations: Queues play a key role in simulations of real-world scenarios, such as modeling customer queues in banks or traffic flow at intersections.
- Multi-Consumer, Multi-Producer Systems: In concurrent programming, queues help synchronize communication between multiple producers and consumers, ensuring safe data exchange.
Difference Between Stack and Queue
Let’s now explore the differences between Stack and Queue.
| Feature | Stack | Queue |
|---|---|---|
| Order Principle | LIFO (Last-In-First-Out) | FIFO (First-In-First-Out) |
| Insertion | Top | Back (Rear) |
| Removal | Top | Front (Head) |
| Operations | Push, Pop, Peek | Enqueue, Dequeue, Peek |
| Usage | Function calls, expression evaluation, undo functionality | BFS traversal, task scheduling, print job management |
| Example | Plates in a cafeteria | Customers in a line |
Conclusion : Stack and Queue in Data Structure
In this article, we delved into the concepts of Stack and Queue data structures, exploring their characteristics and functionalities. We first comprehensively understood the nature of Stacks and Queues, emphasizing their order principles – Last-In-First-Out (LIFO) for Stacks and First-In-First-Out (FIFO) for Queues. We delved into the vital operations associated with these structures: Push, Pop, Peek for Stacks, and Enqueue, Dequeue, Peek for Queues. Additionally, we highlighted the built-in Java classes like java.util.Stack and java.util.Deque that facilitate working with Stacks and Queues. Furthermore, we discussed how to build custom implementations of Stacks and Queues using arrays and ArrayLists, demonstrating their code structures.
The article progressed to outline various practical applications of both Stacks and Queues, showcasing their significance across domains. Stacks find application in tasks like function call management, expression evaluation, undo functionality, and more. On the other hand, Queues prove invaluable in areas such as task scheduling, BFS traversal, call center systems, and simulations.
In conclusion, the article has provided an insightful exploration of Stacks and Queues, detailing their definitions, operations, implementations, and practical implications across diverse scenarios.