Stack, queue and deque explained in Java

A stack is a data structure that operates on a last-in, first-out (LIFO) basis. This means that elements are added to and removed from the top of the stack. Stacks are often used to store data temporarily during the execution of a program, or to reverse the order of items.

In Java, the java.util.Stack class provides a implementation of a stack data structure. The Stack class extends the Vector class and provides a number of additional methods for working with stacks. Here are some common methods of the Stack class:

• push(): Pushes an element onto the top of the stack.
• pop(): Removes and returns the element at the top of the stack.
• peek(): Returns the element at the top of the stack without removing it.
• isEmpty(): Returns true if the stack is empty.
• search(): Returns the position of an element in the stack, where the top of the stack is considered position 1.

Here is an example of how you might use the Stack class:

import java.util.Stack;

public class Main {
  public static void main(String[] args) {
    Stack<Integer> stack = new Stack<>();

    // Push elements onto the stack
    stack.push(5);
    stack.push(2);
    stack.push(7);
    stack.push(1);
    stack.push(3);

    System.out.println(stack);  // [5, 2, 7, 1, 3]

    // Pop an element from the stack
    int popped = stack.pop();
    System.out.println(popped);  // 3
    System.out.println(stack);  // [5, 2, 7, 1]

    // Peek at the top element of the stack
    int top = stack.peek();
    System.out.println(top);  // 1
    System.out.println(stack);  // [5, 2, 7, 1]

    // Check if the stack is empty
    boolean empty = stack.isEmpty();
    System.out.println(empty);  // false

    // Search for an element in the stack
    int position = stack.search(2);
    System.out.println(position);  // 2
  }
}

A queue is a data structure that operates on a first-in, first-out (FIFO) basis. This means that elements are added to the end of the queue and removed from the front of the queue. Queues are often used to store data that needs to be processed in a specific order, or to store data that will be used by multiple consumers.

In Java, the java.util.Queue interface and the java.util.LinkedList class provide implementations of a queue data structure. The Queue interface extends the Collection interface and provides a number of additional methods for working with queues. Here are some common methods of the Queue interface:

• offer(): Adds an element to the end of the queue.
• poll(): Removes and returns the element at the front of the queue, or returns null if the queue is empty.
• peek(): Returns the element at the front of the queue without removing it, or returns null if the queue is empty.

Here is an example of how you might use the LinkedList class as a queue:

import java.util.LinkedList;
import java.util.Queue;

public class Main {
  public static void main(String[] args) {
    Queue<Integer> queue = new LinkedList<>();

    // Offer elements to the queue
    queue.offer(5);
    queue.offer(2);
    queue.offer(7);
    queue.offer(1);
    queue.offer(3);

    System.out.println(queue);  // [5, 2, 7, 1, 3]

    // Poll an element from the queue
    int polled = queue.poll();
    System.out.println(polled);  // 5
    System.out.println(queue);  // [2, 7, 1, 3]

    // Peek at the element at the front of the queue
    int front = queue.peek();
    System.out.println(front);  // 2
    System.out.println(queue);  // [2, 7, 1, 3]
  }
}

A deque (short for "double-ended queue") is a data structure that allows you to add and remove elements from either end of the deque. Deques are often used when you need to efficiently add and remove elements from both ends of a sequence, or when you need to be able to access both the front and back of the sequence.

In Java, the java.util.Deque interface and the java.util.LinkedList class provide implementations of a deque data structure. The Deque interface extends the Queue interface and provides a number of additional methods for working with deques. Here are some common methods of the Deque interface:

• addFirst(): Adds an element to the front of the deque.
• addLast(): Adds an element to the end of the deque.
• offerFirst(): Adds an element to the front of the deque, returning true if the operation was successful.
• offerLast(): Adds an element to the end of the deque, returning true if the operation was successful.
• removeFirst(): Removes and returns the element at the front of the deque, or throws an exception if the deque is empty.
• removeLast(): Removes and returns the element at the end of the deque, or throws an exception if the deque is empty.
• pollFirst(): Removes and returns the element at the front of the deque, or returns null if the deque is empty.
• pollLast(): Removes and returns the element at the end of the deque, or returns null if the deque is empty.
• peekFirst(): Returns the element at the front of the deque without removing it, or returns null if the deque is empty.
• peekLast(): Returns the element at the end of the deque without removing it, or returns null if the deque is empty.

Here is an example of how you might use the LinkedList class as a deque:

import java.util.Deque;
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    Deque<Integer> deque = new LinkedList<>();

    // Add elements to the deque
    deque.addFirst(5);
    deque.addLast(2);
    deque.addFirst(7);
    deque.addLast(1);
    deque.addFirst(3);

    System.out.println(deque);  // [3, 7, 5, 2, 1]

    // Remove elements from the deque
    int removed = deque.removeFirst();
    System.out.println(removed);  // 3
    System.out.println(deque);  // [7, 5, 2, 1]

    removed = deque.removeLast();
    System.out.println(removed);  // 1
    System.out.println(deque);  // [7, 5, 2]

    // Peek at the elements at the front and back of the deque
    int front = deque.peekFirst();
    int back = deque.peekLast();
    System.out.println(front);  // 7
    System