DAY 58: Mastering Stacks & Queues – Theory, Implementation & Applications | Stacks & Queues

---

🚀 Introduction

Welcome to Day 58 of my DSA Journey!
After completing around 30 practice problems on Linked List, I’ve now moved on to another fundamental and widely used data structure in problem-solving — Stacks & Queues.

Over the past 3 days, I focused on understanding their theory, key operations, properties, applications, and different ways of implementation using arrays and linked lists.

I’m documenting this journey publicly to stay consistent, track my progress, and also help others who are starting their DSA preparation from scratch.

👉 Feel free to follow me on Twitter for real-time updates, problem breakdowns, and coding insights!

📅 Here’s What I Covered Over the Last 3 Days:

Day 55

• Stack
• Key Operations
• Properties of Stack
• Applications of Stack
• Implementation using Array
• Implementation using Linked List

Day 56

• Queue
• Queue Terminologies
• Types of Queue
• Applications of Queue

Day 57

• Queue Implementation using Array
• Queue Implementation using Linked List

Now, let’s dive deeper into each of these concepts 👇

---

1. Stack

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
This means the element that is inserted last will be the first one to be removed — just like a stack of plates, where you can only take or add from the top.

Key Operations in Stack:

1. push(x) → Insert an element x at the top of the stack.

   • Time Complexity: O(1)

2. pop() → Remove and return the top element from the stack.

   • Time Complexity: O(1)

3. peek()/top() → Retrieve (but do not remove) the top element.

   • Time Complexity: O(1)

4. isEmpty() → Check if the stack is empty.

   • Time Complexity: O(1)

5. isFull() → Check if the stack is full (in case of array-based implementation).

   • Time Complexity: `O(1)

Properties of Stack:

• Order: Follows LIFO (Last In, First Out).
• Access: Only the top element is accessible directly.
• Dynamic Size: Can grow/shrink dynamically in linked list implementation.
• Restricted Operations: Unlike arrays/lists, insertion and deletion happen only at one end (top).

Applications of Stack:

• Expression Evaluation: Used in evaluating postfix and prefix expressions.
• Parentheses Matching: Check for balanced brackets in expressions.
• Undo Mechanism: Most text editors use stacks to implement undo/redo operations.
• Backtracking: Algorithms like maze solving, N-Queens, etc., use stacks.
• Function Calls: System uses a call stack to keep track of function calls.
• Browser History: Stores visited pages, where backtracking uses stack operations.

Stack Implementation in Java:

Stacks can be implemented in multiple ways in Java

1. Using Java’s Built-in Library (Stack class)
2. Using Array
3. Using Linked List

Stack Implementation using Java Library:

Java provides a built-in Stack class inside the java.util package.

import java.util.Stack;

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

        // Push elements
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Peek top element
        System.out.println("Top Element: " + stack.peek()); // 30

        // Pop element
        System.out.println("Popped: " + stack.pop()); // 30

        // Check if empty
        System.out.println("Is Empty: " + stack.isEmpty());
    }
}

Easiest to use, but limited for learning internal workings. That’s why we implement stacks manually using arrays and linked lists.

Stack Implementation using Array:

public class StackUsingArray {
    private final int[] arr;
    private static final int DEFAULT_SIZE = 10;
    private int top;

    public StackUsingArray() {
        this(DEFAULT_SIZE);
    }

    public StackUsingArray(int size) {
        this.arr = new int[size];
        this.top = -1;
    }

    public void push(int value) throws StackException {
        if (isFull()) {
            throw new StackException("Stack is Full");
        }
        arr[++top] = value;
    }

    public int pop() throws StackException {
        if (isEmpty()) {
            throw new StackException("Stack is Empty");
        }
        return arr[top--];
    }

    public int peek() throws StackException {
        if (isEmpty()) {
            throw new StackException("Stack is Empty");
        }
        return arr[top];
    }

    public int size() {
        return top + 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == arr.length - 1;
    }
}

Explanation:

• push() → Inserts at top.
• pop() → Removes from top.
• peek() → Retrieves the top element.
• isEmpty() and isFull() → Handle boundary checks.

Time Complexity:

• Push → O(1)
• Pop → O(1)

Stack Implementation using Linked List:

public class StackUsingLL {
    private Node top;
    private int size;

    private static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public StackUsingLL() {
        this.size = 0;
    }

    public void push(int item) {
        Node node = new Node(item);
        node.next = top;
        top = node;
        size++;
    }

    public int pop() throws StackException {
        if (top == null) {
            throw new StackException("Stack is Empty");
        }
        int item = top.value;
        top = top.next;
        size--;
        return item;
    }

    public int peek() throws StackException {
        if (top == null) {
            throw new StackException("Stack is Empty");
        }
        return top.value;
    }

    public int getSize() {
        return size;
    }
}

Explanation:

• Each element is wrapped in a Node (value + pointer).
• push() → Insert at head (O(1)).
• pop() → Remove from head (O(1)).
• peek() → Returns top element.
• getSize() → Tracks stack size.

Advantages over Array-based:

• No fixed size (dynamic memory).
• No need to check isFull().

Final Thoughts on Stack:

The Stack is one of the most fundamental data structures in computer science.
It follows the LIFO (Last In, First Out) principle, making it ideal for problems where the most recent element needs to be accessed first.

• With Array-based implementation, we get constant-time operations but must handle a fixed size.
• With Linked List-based implementation, we gain flexibility with dynamic memory but at the cost of extra memory for pointers.
• Using Java’s built-in Stack class can simplify usage in real-world projects.

Mastering stacks builds a solid foundation for solving advanced problems like expression evaluation, recursion stack simulation, backtracking, and browser history management.

With Stack covered, I’m now ready to explore the next important structure in my journey — Queue.

---

2. Queue

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle.
The element inserted first is the first one to be removed, just like people standing in a real-world queue (e.g., ticket counter).

Key Operations in Queue:

1. enqueue(x) → Insert an element x at the rear of the queue.
   Time Complexity: O(1)

2. dequeue() → Remove and return the front element of the queue.
   Time Complexity: O(1)

3. peek()/front() → Get the element at the front without removing it.
   Time Complexity: O(1)

4. isEmpty() → Check if the queue is empty.
   Time Complexity: O(1)

5. isFull() → Check if the queue is full (for array-based implementation).
   Time Complexity: O(1)

Types of Queue:

1. Simple Queue (Linear Queue) → Follows FIFO strictly.
2. Circular Queue → Reuses empty space using modulo (%) to connect rear to front.
3. Double-Ended Queue (Deque) → Insertion and deletion allowed from both ends.
4. Priority Queue → Each element has a priority; higher priority elements are dequeued first.

Applications of Queue:

• CPU Scheduling → Processes waiting in ready queue.
• Disk Scheduling → Handling I/O requests.
• Print Spooler → Jobs are printed in the order they arrive.
• Call Center Systems → Customers are served in the order of arrival.
• Breadth-First Search (BFS) → Queue is used for level-order traversal in graphs/trees.

Queue Implementation in Java :

Queues can be implemented in multiple ways

1. Using Java Collections Framework (Library)
2. Using Array (Circular Queue Implementation)
3. Using Linked List

Implement Queue Using Java Library:

Java provides the Queue interface inside the Collections Framework.
The most common implementation is LinkedList or ArrayDeque.

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

        // Enqueue
        queue.add(10);
        queue.add(20);
        queue.add(30);

        // Dequeue
        System.out.println(queue.remove()); // 10

        // Peek
        System.out.println(queue.peek());   // 20

        // Size
        System.out.println(queue.size());   // 2
    }
}

Explanation:

• add() → Insert element at rear.
• remove() → Delete element from front.
• peek() → Retrieve front element without removing.

Time Complexity:

• Enqueue (add) → O(1)
• Dequeue (remove) → O(1)
• Peek → O(1)

Implement Queue Using Array (Circular Queue):

package com.ritik.queue;

public class QueueUsingArray {
    private final int[] arr;
    private static final int DEFAULT_SIZE = 10;
    private int front;
    private int rear;
    private int size;

    public QueueUsingArray() {
        this(DEFAULT_SIZE);
    }

    public QueueUsingArray(int size) {
        this.arr = new int[size];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    public void add(int item) throws QueueException {
        if(isFull()){
            throw new QueueException("Queue is Full");
        }

        arr[rear] = item;
        size++;
        rear = (rear + 1) % arr.length;
    }

    public int remove() throws QueueException{
        if(isEmpty()){
            throw new QueueException("Queue is Empty");
        }
        int item = arr[front];
        size--;
        front = (front + 1) % arr.length;

        return item;
    }

    public int peek() throws QueueException{
        if(isEmpty()){
            throw new QueueException("Queue is Empty");
        }
        return arr[front];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == arr.length;
    }
}

Explanation:

• Uses circular logic with (rear + 1) % arr.length.
• Prevents wastage of space when elements are dequeued.

Time Complexity:

• Enqueue → O(1)
• Dequeue → O(1)
• Peek → O(1)

Implement Queue Using Linked List:

package com.ritik.queue;

public class QueueUsingLL {
    private Node front;
    private Node rear;
    private int size;

    private static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public QueueUsingLL() {
        this.size = 0;
    }

    public void add(int item) {
        Node node = new Node(item);

        if(front == null && rear == null) {
            front = node;
            rear = node;
        } else {
            rear.next = node;
            rear = node;
        }

        size++;
    }

    public int remove() throws QueueException {
        if(isEmpty()){
            throw new QueueException("Queue is Empty");
        }
        int item = front.value;
        front = front.next;
        size--;

        if(front == null) {
            rear = null;
        }

        return item;
    }

    public int peek() throws QueueException{
        if(isEmpty()){
            throw new QueueException("Queue is Empty");
        }
        return front.value;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return front == null;
    }
}

Explanation:

• Each element is wrapped inside a Node.
• add() inserts at the rear, remove() deletes from the front.
• No fixed size → dynamically grows.
• No need for isFull().

Time Complexity:

• Enqueue → O(1)
• Dequeue → O(1)
• Peek → O(1)

Final Thoughts on Queue:

The Queue is one of the most fundamental data structures in computer science.
It operates on the FIFO (First In, First Out) principle, making it ideal for scenarios like scheduling, buffering, and resource management.

• With array-based implementation, we achieve constant-time operations using circular logic.
• With linked list implementation, we eliminate fixed-size limitations and achieve dynamic growth.
• Core operations like enqueue, dequeue, and peek are all efficient, running in O(1) time.

Mastering queues not only builds a solid foundation for DSA but also prepares me for advanced topics like Deque, Priority Queue, and Sliding Window problems.

---

3. What's next

I’m excited to keep growing and sharing along the way! Here’s what’s coming up:

• Posting new blog updates every 3 days to share what I’m learning and building.
• Alongside mastering DSA concepts, I’m also documenting my web development journey — check out my ongoing Web dev Journey Blog for ReactJS concepts, UI projects, Codes, and more.
• Sharing regular progress and insights on X (Twitter) — feel free to follow me there and join the conversation!

Thanks for being part of this journey!

---

4. Conclusion

Over the past three days, diving deep into Stacks and Queues has been a rewarding experience.
Both of these data structures may look simple at first glance, but they form the backbone of countless real-world applications — from expression evaluation and undo mechanisms (Stack) to CPU scheduling and BFS traversal (Queue).

Key Takeaways:

• Stack works on the LIFO principle, making it ideal for problems where the most recent element needs priority.
• Queue works on the FIFO principle, best suited for sequential processing and scheduling.
• Implementing them using arrays and linked lists gave me not just theoretical clarity, but also practical insights into how data structures manage memory and performance.

With these foundations in place, I feel more confident tackling advanced variations like Deque, Priority Queue, and Concurrent Queues, which I’ll explore in upcoming blogs.

This journey is not just about solving problems, but about building the mindset of breaking down concepts step by step and strengthening my problem-solving muscle.

👉 If you’re on a similar journey, stay consistent, code daily, and don’t shy away from challenging problems. Every step makes you a better problem solver.

Thanks for reading! 🙌
Follow me here (and on Twitter) for more updates as I continue my DSA journey 🚀.