Fundamentals of Stack and Queue Data Structures

Stack Data Structure

Concept

A stack is a specialized linear data structure that permits insertion and deletion operations only at one fixed end, known as the top. The opposite end is called the bottom. Elements in a stack follow the Last-In-First-Out (LIFO) principle. The insertion operation is called pushing, while deletion is called popping. Both operations occur at the top of the stack.

Stack Operations

Stack Implementation Example

import java.util.Stack;public class StackExample {    public static void main(String[] args) {        Stack<Integer> stack = new Stack<>();        stack.push(10);        stack.push(20);        stack.push(30);        stack.push(40);                System.out.println("Stack size: " + stack.size());        System.out.println("Top element: " + stack.peek());        System.out.println("Popped element: " + stack.pop());                if (stack.isEmpty()) {            System.out.println("Stack is empty");        } else {            System.out.println("Current stack size: " + stack.size());       }    }}

Custom Stack Implementation

import java.util.Arrays;public class CustomStack {    private int[] elements;    private int count;        public CustomStack() {        elements = new int[5];    }        public int push(int item) {        ensureCapacity();        elements[count++] = item;        return item;    }        public int pop() {        int item = peek();        count--;        return item;    }        public int peek() {        if (isEmpty()) {            throw new IllegalStateException("Stack is empty");        }        return elements[count - 1];    }        public boolean isEmpty() {        return count == 0;    }        public int size() {        return count;    }        private void ensureCapacity() {        if (count == elements.length) {            elements = Arrays.copyOf(elements, count * 2);       }    }}

Stack vs. Virtual Machine Stack vs. Stack Frame

• Stack: A data structure used for storing data following LIFO principles.
• Virtual Machine Stack: The memory space used by the Java Virtual Machine during program execution.
• Stack Frame: The memory area allocated for each method call, containing information needed for that method's execution.

Queue Data Structure

Concept

A queue is a linear data structure that allows insertion at one end and deletion at the opposite end. The insertion end is called the rear or tail, while the deletion end is called the front or head. Queues follow the First-In-First-Out (FIFO) principle. The insertion operation is called enqueue, and the deletion operation is called dequeue.

Queue Operations

Queue Implementation Example

import java.util.LinkedList;import java.util.Queue;public class QueueExample {    public static void main(String[] args) {        Queue<Integer> queue = new LinkedList<>();        queue.offer(5);        queue.offer(10);        queue.offer(15);        queue.offer(20);        queue.offer(25);                System.out.println("Queue size: " + queue.size());        System.out.println("Front element: " + queue.peek());        System.out.println("Removed element: " + queue.poll());        System.out.println("Next removed element: " + queue.poll());                if (queue.isEmpty()) {            System.out.println("Queue is empty");        } else {            System.out.println("Current queue size: " + queue.size());       }    }}

Queue Implementation Using Linked List

public class LinkedListQueue {    private static class Node {        int data;        Node next;                Node(int data) {            this.data = data;        }    }        private Node front;    private Node rear;    private int size;        public void enqueue(int value) {        Node newNode = new Node(value);        if (isEmpty()) {            front = newNode;            rear = newNode;        } else {            rear.next = newNode;            rear = newNode;        }        size++;    }        public int dequeue() {        if (isEmpty()) {            throw new IllegalStateException("Queue is empty");        }                int value = front.data;        front = front.next;                if (front == null) {            rear = null;        }                size--;        return value;    }        public int peek() {        if (isEmpty()) {            throw new IllegalStateException("Queue is empty");        }        return front.data;    }        public boolean isEmpty() {        return front == null;    }        public int size() {        return size;    }}

Circular Queue

A circular queue is an enhanced version of a linear queue that utilizes a fixed-size array more efficiently by connecting the front and rear ends. This prevents the wastage of space that occurs in a simple linear queue when elements are dequeued.

Circular Queue Implementation

class CircularQueue {    private int front;    private int rear;    private int[] elements;    private int capacity;        public CircularQueue(int k) {        front = 0;        rear = 0;        capacity = k + 1;        elements = new int[capacity];    }        public boolean enqueue(int value) {        if (isFull()) {            return false;        }                elements[rear] = value;        rear = (rear + 1) % capacity;        return true;    }        public boolean dequeue() {        if (isEmpty()) {            return false;        }                front = (front + 1) % capacity;        return true;    }        public int front() {        if (isEmpty()) {            return -1;        }        return elements[front];    }        public int rear() {        if (isEmpty()) {            return -1;        }        return elements[(rear - 1 + capacity) % capacity];    }        public boolean isEmpty() {        return front == rear;    }        public boolean isFull() {        return (rear + 1) % capacity == front;    }}

Double-Ended Queue (Deque)

A double-ended queue (deque) is a generalized form of a queue that allows insertion and deletion operations at both ends. The name "deque" comes from "double-ended queue." This means elements can be added or removed from either the front or the rear of the deque.

In practical applications, the Deque interface is commonly used as it can implement both stack and queue functionalities.

Deque Implementation Examples

import java.util.ArrayDeque;import java.util.Deque;public class DequeExample {    public static void main(String[] args) {        // Array-based deque implementation        Deque<Integer> arrayDeque = new ArrayDeque<>();                // Using deque as a stack        arrayDeque.push(1);  // Add to front        arrayDeque.push(2);        arrayDeque.push(3);                System.out.println("Top element: " + arrayDeque.peek());  // View front        System.out.println("Popped element: " + arrayDeque.pop());  // Remove from front                // Using deque as a queue        arrayDeque.offerLast(4);  // Add to rear        arrayDeque.offerLast(5);                System.out.println("Front element: " + arrayDeque.peekFirst());  // View front        System.out.println("Rear element: " + arrayDeque.peekLast());  // View rear        System.out.println("Removed from front: " + arrayDeque.pollFirst());  // Remove from front        System.out.println("Removed from rear: " + arrayDeque.pollLast());  // Remove from rear    }}