Key differences between Stack and Queue

Stack

Stack is a linear data structure that follows a particular order in which operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). This means the last element added to the stack will be the first one to be removed. Stacks are used in a variety of applications such as expression evaluation, backtracking algorithms, and maintaining function calls (the call stack) in most programming environments. Operations primarily include push (adding an element to the top of the stack), pop (removing the top element), and peek (viewing the top element without removing it). Stacks can be implemented using arrays, linked lists, or even other data structures.

Functions of Stack:

• Push:

Adds an element to the top of the stack. This is the primary way to insert data into the stack.

• Pop:

Removes the element on the top of the stack, effectively the most recently added element, and returns it. This operation changes the state of the stack.

• Peek or Top:

Returns the element at the top of the stack without removing it, allowing inspection of the current LIFO element.

• isEmpty:

Checks if the stack is empty. This is useful to avoid errors like underflow when attempting to pop or peek elements from an empty stack.

• isFull (if applicable):

Depending on the implementation, especially in a fixed-size stack (like when using an array), this function checks if the stack has reached its maximum capacity.

• Size or Count:

Returns the number of elements currently on the stack. This helps in understanding the stack’s current state.

• Clear:

Empties all elements from the stack, resetting it to an empty state.

• Display or Print:

Outputs all elements of the stack, typically from top to bottom, enabling visualization of its content.

Example of Stack:

This example includes basic operations such as push, pop, peek, and checking if the stack is empty.

class Stack {

    private int arr[];

    private int top;

    private int capacity;

    // Constructor to initialize the stack

    Stack(int size) {

        arr = new int[size];

        capacity = size;

        top = -1;

    }

    // Add elements into stack

    public void push(int x) {

        if (isFull()) {

            System.out.println(“Stack OverFlow”);

            System.exit(1);

        }

        System.out.println(“Inserting ” + x);

        arr[++top] = x;

    }

    // Remove element from stack and return removed value

    public int pop() {

        if (isEmpty()) {

            System.out.println(“Stack UnderFlow”);

            System.exit(1);

        }

        return arr[top–];

    }

    // Utility function to return top element in a stack

    public int peek() {

        if (!isEmpty()) {

            return arr[top];

        } else {

            System.exit(1);

        }

        return -1;

    }

    // Utility function to check if the stack is empty or not

    public boolean isEmpty() {

        return top == -1;

    }

    // Utility function to check if the stack is full or not

    public boolean isFull() {

        return top == capacity – 1;

    }

    public static void main(String[] args) {

        Stack stack = new Stack(3);

        stack.push(1);    // Inserting 1 in the stack

        stack.push(2);    // Inserting 2 in the stack

        System.out.println(“Top element is: ” + stack.peek());

        stack.pop();      // removing the top element (2)

        System.out.println(“Top element is: ” + stack.peek());

        stack.push(3);    // Inserting 3 in the stack

        System.out.println(“The stack size is ” + (stack.top + 1));

        stack.pop();      // removing the top element (3)

        stack.pop();      // removing the top element (1)

        if (stack.isEmpty()) {

            System.out.println(“The stack is empty”);

        } else {

            System.out.println(“The stack is not empty”);

        }

    }

}

This code defines a Stack class that manages integer elements. The stack operations ensure that elements are added and removed following the LIFO principle. The class provides methods to push data onto the stack, pop data off the stack, peek at the data at the top of the stack without removing it, and check if the stack is empty or full. The example also includes a simple main method that demonstrates these operations in action, showcasing how a stack can be utilized in a practical scenario.

Queue

queue is a linear data structure that operates in a First In First Out (FIFO) manner, where the first element added is the first to be removed. This sequence helps in managing data elements in order of their arrival, making queues ideal for scenarios like processing tasks, handling asynchronous data transfers, and buffering in various systems. Essential operations in a queue include enqueue (adding an element to the end of the queue), dequeue (removing the element at the front), and peek (viewing the front element without removing it). Queues can be implemented using arrays, linked lists, or more complex forms such as circular buffers. They are fundamental in managing resources in computing environments, networking, and operating systems.

Functions of Queue:

• Enqueue:

Adds an element to the end of the queue. This operation involves adding a new element at the rear of the queue.

• Dequeue:

Removes the element at the front of the queue and returns it. This operation is essential for retrieving and removing the oldest element that has been in the queue the longest.

• Peek or Front:

Returns the front element of the queue without removing it. This allows you to view the element at the front of the queue without modifying the queue.

• IsEmpty:

Checks if the queue is empty. This function is crucial for avoiding errors such as underflow when attempting to dequeue from an empty queue.

• IsFull (for a fixed-size queue):

Checks if the queue is full. This is important for avoiding overflow errors in queues with limited capacity.

• Size:

Returns the number of elements currently in the queue. This can be used to monitor how many items are currently stored and manage capacity efficiently.

• Clear:

Removes all elements from the queue. This operation is useful when resetting the queue or when the stored data is no longer needed.

• Iterator:

Provides a way to iterate over the elements in the queue, usually from the front to the rear. This can be useful for reading all elements without removing them.

Example of Queue:

Below is a simple example of how to use a queue in Java, utilizing the LinkedList class which implements the Queue interface. This example demonstrates basic queue operations such as enqueueing (adding), dequeueing (removing), and peeking at the front element.

import java.util.LinkedList;

import java.util.Queue;

public class QueueExample {

    public static void main(String[] args) {

        // Creating a Queue using the LinkedList class

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

        // Adding elements to the Queue (Enqueue)

        queue.add(10); // Add first element

        queue.add(20); // Add second element

        queue.add(30); // Add third element

        // Displaying the initial Queue

        System.out.println(“Initial Queue: ” + queue);

        // Removing elements from the Queue (Dequeue)

        System.out.println(“Removed element: ” + queue.remove()); // Removes 10

        // Displaying the Queue after one element is removed

        System.out.println(“Queue after removal: ” + queue);

        // Peeking at the front element of the Queue

        System.out.println(“Front element: ” + queue.peek()); // Shows 20 without removing it

        // Final state of the Queue

        System.out.println(“Final Queue: ” + queue);

    }

}

Output

Initial Queue: [10, 20, 30]

Removed element: 10

Queue after removal: [20, 30]

Front element: 20

Final Queue: [20, 30]

This example uses LinkedList as the queue implementation. We perform several operations:

• Add/Enqueue:

Elements are added to the back of the queue.

• Remove/Dequeue:

Elements are removed from the front of the queue, starting with the first element that was added.

• Peek:

Retrieves the front element of the queue without removing it, useful for checking the first element to be processed next.

Key differences between Stack and Queue

Key Similarities between Stack and Queue

• Sequential Access:

Both stacks and queues store elements in a sequential order, although the access pattern for removal and inspection might differ.

• Dynamic Size:

In many implementations, both stacks and queues can grow dynamically as more elements are added, depending on the system’s memory constraints and the implementation details.

• Support for Basic Operations:

Both data structures support basic operations such as adding and removing elements, though the specific methods (push/pop for stack and enqueue/dequeue for queue) and order of operations differ.

• Implementation in Java Collections Framework:

Stacks and queues are both part of the Java Collections Framework, allowing them to integrate seamlessly with other data structures and algorithms provided by Java.

• Usage in Algorithmic Problems:

Both are used extensively in solving various computer science problems and algorithmic challenges such as traversals, scheduling, resource allocation, and more.

• Can Use Linked Lists:

Both stacks and queues can be implemented using linked lists, which provides dynamic sizing and efficient operations.

• Interface Implementation:

In Java, both stacks and queues can implement the Iterable interface, which allows for traversing the elements.