Stacks and Queues in Java

In computer science, stacks and queues are two fundamental data structures used to store and manage data. Stacks and queues are both linear data structures, meaning they store data in a linear fashion and all data is arranged sequentially. Stack and queue operations are also known as Last-In-First-Out (LIFO) and First-In-First-Out (FIFO) respectively.

Stacks are an example of a data structure that follows the LIFO principle. In a stack, data is inserted (or pushed) and removed (or popped) from the same end, known as the top of the stack. Queues, on the other hand, follow the FIFO principle, meaning that data is inserted (or enqueued) at one end, known as the rear of the queue, and removed (or dequeued) from the other end, known as the front of the queue.

In this article, we will discuss the basics of stacks and queues, including their implementation using arrays and classes, their use of the Java Collections Framework, and their applications.

Implementing Stacks and Queues with Arrays

Arrays are the simplest data structure for implementing stacks and queues. We can use a single array to represent both a stack and a queue. Each element in the array can represent either a single item in the stack or queue, or a combination of items if the stack or queue is composed of multiple data types.

To implement a stack with an array, we must first define the size of the array. We can then use a special variable, often called the “top” of the stack, to keep track of the array index of the topmost item in the stack.

For example, consider the following array:

int[] stack = new int[10];
int top = -1;

The array `stack` is initialized with 10 elements, and the variable `top` is initialized to -1, indicating that the stack is empty. To add an item to the top of the stack, we simply increment the `top` variable and assign the item to the corresponding array element, as shown below:

top++;
stack[top] = item;

To remove an item from the top of the stack, we simply retrieve the item from the array element at the `top` index, and then decrement the `top` variable, as shown below:

int item = stack[top];
top--;

Implementing a queue with an array is very similar. We must first define the size of the array. We then use two special variables, often called the “front” and “rear” of the queue, to keep track of the array indices of the frontmost and rearmost items in the queue, respectively.

For example, consider the following array:

int[] queue = new int[10];
int front = 0;
int rear = -1;

The array `queue` is initialized with 10 elements, and the variables `front` and `rear` are initialized to 0 and -1, respectively, indicating that the queue is empty. To add an item to the rear of the queue, we simply increment the `rear` variable and assign the item to the corresponding array element, as shown below:

rear++;
queue[rear] = item;

To remove an item from the front of the queue, we simply retrieve the item from the array element at the `front` index, and then increment the `front` variable, as shown below:

int item = queue[front];
front++;

Implementing Stacks and Queues with Classes

In addition to using arrays, we can also implement stacks and queues using classes in Java. A stack class can be implemented as a subclass of a List interface, such as ArrayList or Vector, or as a standalone class. Similarly, a queue class can be implemented as a subclass of a Deque interface, such as ArrayDeque or LinkedList, or as a standalone class.

To implement a stack as a subclass of a List interface, we must first define the class and extend it from the appropriate List interface. We can then override the push and pop methods to add and remove items from the stack, as shown below:

public class Stack extends ArrayList<Integer> {

    // push item to top of stack
    public void push(Integer item) {
        super.add(item);
    }

    // pop item from top of stack
    public Integer pop() {
        return super.remove(super.size() - 1);
    }
}

To implement a queue as a subclass of a Deque interface, we must first define the class and extend it from the appropriate Deque interface. We can then override the enqueue and dequeue methods to add and remove items from the queue, as shown below:

public class Queue extends LinkedList<Integer> {

    // enqueue item at rear of queue
    public void enqueue(Integer item) {
        super.addLast(item);
    }

    // dequeue item from front of queue
    public Integer dequeue() {
        return super.removeFirst();
    }
}

Using the Collections Framework for Stacks and Queues

The Java Collections Framework provides several classes for implementing stacks and queues. The Stack class implements the LIFO principle, while the Queue class implements the FIFO principle. Both classes are subclasses of the Collection interface, which provides several methods for adding, removing, and manipulating elements in the collection.

The Stack and Queue classes also provide several additional methods for manipulating elements, such as the push and pop methods for Stack, and the enqueue and dequeue methods for Queue.

For example, consider the following code:

Stack<Integer> stack = new Stack<>();

// add element to top of stack
stack.push(1);

// remove element from top of stack
int item = stack.pop();

Queue<Integer> queue = new Queue<>();

// add element to rear of queue
queue.enqueue(1);

// remove element from front of queue
int item = queue.dequeue();

Applications of Stacks and Queues

Stacks and queues are used in a variety of applications, including memory management, scheduling, and expression evaluation.

Stacks are commonly used in memory management, where they are used to store the return address of functions. They are also used to store the state of a program during a function call.

Queues are commonly used for scheduling tasks and managing resources. For example, a queue can be used to manage the order in which tasks are executed.

Stacks and queues are also used in expression evaluation, such as arithmetic or boolean expressions. Stacks are used to store the operands of an expression, while queues are used to store the operators of an expression.

Conclusion

In this article, we have discussed the basics of stacks and queues, including their implementation using arrays and classes, their use of the Java Collections Framework, and their applications. We have seen that stacks and queues are both linear data structures that are used to store and manage data in a linear fashion. We have also seen that stacks and queues can be implemented using either arrays or classes, and that the Java Collections Framework provides several classes for implementing stacks and queues. Finally, we have discussed some of the common applications of stacks and queues.

Exercises

public static void printStack(Stack<Integer> stack) {
    while (!stack.isEmpty()) {
        System.out.println(stack.pop());
    }
}

public static void printQueue(Queue<Integer> queue) {
    while (!queue.isEmpty()) {
        System.out.println(queue.dequeue());
    }
}

public static void printStackAndQueue(Stack<Integer> stack, Queue<Integer> queue) {
    while (!stack.isEmpty()) {
        System.out.println(stack.pop());
    }
    while (!queue.isEmpty()) {
        System.out.println(queue.dequeue());
    }
}

public static void reverseStack(Stack<Integer> stack) {
    Stack<Integer> tempStack = new Stack<>();
    while (!stack.isEmpty()) {
        tempStack.push(stack.pop());
    }
    while (!tempStack.isEmpty()) {
        stack.push(tempStack.pop());
    }
}

public static void reverseQueue(Queue<Integer> queue) {
    Stack<Integer> tempStack = new Stack<>();
    while (!queue.isEmpty()) {
        tempStack.push(queue.dequeue());
    }
    while (!tempStack.isEmpty()) {
        queue.enqueue(tempStack.pop());
    }
}