DAY 61: Implement Stack & Queue Variations + Solve Valid Parentheses | Stacks & Queues

---

🚀 Introduction

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

Over the past 3 days, I implemented Stack using Queue and Queue using Stacks, and also solved a classic problem — Valid Parentheses.

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 58

• Implement Stack using 2 Queues
• Implement Stack using 1 Queue

Day 59

• Implement Queue using Stacks (Dequeue Costly Method)
• Implement Queue using Stacks (Amortized (O(1)) Method)

Day 60

• Valid Parentheses

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

---

1. Implement Stack using 2 Queues

In this approach, we use two queues (q1 and q2) to simulate the behavior of a stack.
The push operation is costly, while pop and peek are efficient.

Key Idea:

• Always maintain the most recent element at the front of q1.
• To achieve this, when a new element is pushed:
  1. Add it to q2.
  2. Move all elements of q1 into q2.
  3. Swap the references of q1 and q2.

This ensures that the newest element always comes to the front of q1, so that pop() and peek() work in O(1) time.

Code Implementation:

public class StackUsingTwoQueue {
    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public StackUsingTwoQueue() {
        this.q1 = new LinkedList<>();
        this.q2 = new LinkedList<>();
    }

    public void push(int item) {
        // add item in q2
        q2.add(item);

        // Move all items from q1 to q2
        while(!q1.isEmpty()){
            q2.add(q1.remove());
        }

        // Swap q1 and q2
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public int pop() {
        return q1.remove();
    }

    public int peek() {
        return q1.peek();
    }

    public boolean isEmpty() {
        return q1.isEmpty();
    }
}

• push(item) → O(n) (since all elements from q1 are shifted to q2).
• pop() → O(1), just remove from q1.
• peek() → O(1), just fetch the front of q1.
• isEmpty() → O(1), checks if q1 is empty.

Time Complexity

• Push → O(n)
• Pop → O(1)
• Peek → O(1)
• isEmpty → O(1)

Takeaway

This implementation demonstrates how queues (FIFO) can be manipulated to behave like stacks (LIFO).
Here, we made the push operation costly to keep pop and peek efficient.

---

2. Implement Stack using 1 Queue

In this approach, we use a single queue to implement stack behavior.
The main trick is to rotate the queue after every push so that the newly added element always comes to the front — ensuring LIFO (Last-In-First-Out) order.

How It Works?

push(item)

• Add the new element to the queue.
• Rotate the queue elements (shift previous elements behind the newly added one).
• Ensures the latest pushed element is always at the front.

pop()

• Simply remove from the front of the queue → behaves like stack’s pop.

peek()

• Return the front element → behaves like stack’s top.

isEmpty()

• Check if the queue is empty.

Code Implementation:

public class StackUsingQueue {
    Queue<Integer> queue;

    public StackUsingQueue() {
        this.queue = new LinkedList<>();
    }

    public void push(int item) {
        int size = queue.size();
        queue.add(item);

        // Rotate the queue to bring the new element at front
        for (int i = 1; i <= size; i++) {
            queue.add(queue.peek());
            queue.remove();
        }
    }

    public int pop() {
       return queue.remove();
    }

    public int peek() {
        return queue.peek();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }
}

Time Complexity:

• Push → O(n) (rotation of elements)
• Pop → O(1)
• Peek → O(1)
• isEmpty → O(1)

Takeaway:

This method shows how we can use a single queue to achieve stack functionality.
Here, push is costly because we rotate elements after every insertion, while pop and peek remain efficient.

---

3. Implement Queue using Stacks (Dequeue Costly Method)

In this approach, we use two stacks (first and second) to implement a queue (FIFO) behavior.
Here, the remove (dequeue) operation is made costly, while add (enqueue) is efficient.

How It Works?

add(item)

• Simply push the element into the first stack.

remove()

1. Transfer all elements from first to second.
2. Pop the top element from second → this is the front of the queue.
3. Move the remaining elements back from second to first.

peek()

1. Transfer all elements from first to second.
2. Fetch the top element from second (front of the queue).
3. Move elements back to first.

isEmpty()

• Return true if the first stack is empty.

Code Implementation:

public class QueueUsingStacks {
    private final Stack<Integer> first;
    private final Stack<Integer> second;

    public QueueUsingStacks() {
        this.first = new Stack<>();
        this.second = new Stack<>();
    }

    public void add(int item) {
        first.push(item);
    }

    // Dequeue Costly
    public int remove() {
        while(!first.isEmpty()){
            second.push(first.pop());
        }

        int removedItem = second.pop();

        while(!second.isEmpty()){
            first.push(second.pop());
        }

        return removedItem;
    }

    public int peek() {
        while (!first.isEmpty()){
            second.push(first.pop());
        }
        int item = second.peek();
        while(!second.isEmpty()){
            first.push(second.pop());
        }

        return item;

    }

    public boolean isEmpty() {
        return first.isEmpty();
    }

}

Time Complexity:

• add → O(1) (just push into stack)
• remove → O(n) (transfer between stacks twice)
• peek → O(n) (similar transfer logic as remove)
• isEmpty → O(1)

Takeaway:

This method makes dequeue (remove) costly while keeping enqueue (add) efficient.
It clearly demonstrates how stacks (LIFO) can be manipulated to behave like queues (FIFO) by reversing order during removal.

---

4. Implement Queue using Stacks (Amortized O(1) Method)

This is a more optimized approach to implement a queue (FIFO) using two stacks (s1 and s2).
Here, both remove (dequeue) and peek operations are amortized O(1), making it much more efficient than the Dequeue Costly Method.

How It Works?

add(item)

• Always push the new element into stack s1.

remove()

1. If s2 is empty, transfer all elements from s1 to s2.
2. Pop the top element from s2 → this is the front of the queue.
3. If both stacks are empty, throw an exception (Queue is Empty).

peek()

1. If s2 is empty, transfer all elements from s1 to s2.
2. Return the top element of s2 (front of the queue).
3. If both stacks are empty, throw an exception (Queue is Empty).

isEmpty()

• Return true if both s1 and s2 are empty.

Code Implementation:

public class QueueUsingStacks {
    private final Stack<Integer> s1;
    private final Stack<Integer> s2;

    public QueueUsingStacks() {
        this.s1 = new Stack<>();
        this.s2 = new Stack<>();
    }

    public void add(int item) {
        s1.push(item);
    }

    public int remove() {
        if(s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        if(s2.isEmpty()) {
            throw new RuntimeException("Queue is Empty");
        }

        return s2.pop();
    }

    public int peek() {
        if(s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        if(s2.isEmpty()) {
            throw new RuntimeException("Queue is Empty");
        }

        return s2.peek();
    }

    public boolean isEmpty() {
        return s1.isEmpty() && s2.isEmpty();
    }

}

Time Complexity:

• add → O(1) (just push into s1)
• remove → Amortized O(1)
  • Each element is moved from s1 → s2 only once, so total cost is spread across all operations.
• peek → Amortized O(1) (same reasoning as remove)
• isEmpty → O(1)

Takeaway:

This method provides an efficient queue implementation using two stacks:

• Enqueue (add) is always O(1).
• Dequeue (remove) and peek are amortized O(1).

This is the most widely used technique for implementing a queue using stacks because it balances efficiency with simplicity.

---

5. Valid Parentheses

Given a string containing only the characters (, ), {, }, [ and ], determine if the input string is valid.

A string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example:

Input: "()[{}()]"
Output: true
Explanation:

• '(' matches ')'
• '[' matches ']'
• '{' matches '}'
• '(' matches ')'

The order of closure is correct, so the string is valid.

Approach:

• Use a stack to keep track of opening brackets.
• Traverse the string character by character:
  • If it’s an opening bracket ((, {, [), push it onto the stack.
  • If it’s a closing bracket (), }, ]):
    • Check if the stack is empty → if yes, return false.
    • Pop the top element and check if it matches the current closing bracket.
    • If it doesn’t match, return false.
• After processing all characters, check if the stack is empty:
  • If yes, the string is valid.
  • If not, there are unmatched brackets → return false.

Code Implementation:

public static boolean isValid(String str) {
    Stack<Character> stack = new Stack<>();

    for(int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);

        // Push opening brackets
        if(ch == '(' || ch == '{' || ch == '[') {
            stack.push(ch);
        }

        // Handle closing brackets
        if(ch == ')' || ch == '}' || ch == ']') {
            if(stack.isEmpty()) return false; // unmatched closing

            char top = stack.pop();
            if((ch == ')' && top != '(') || 
               (ch == '}' && top != '{') || 
               (ch == ']' && top != '[')) {
                return false; // mismatched pair
            }
        }
    }

    // If stack is empty, all brackets matched
    return stack.isEmpty();
}

Time & Space Complexity:

• Time Complexity: O(n) → Traverse the string once.
• Space Complexity: O(n) → Stack stores opening brackets in the worst case.

Final Thoughts:

• This problem perfectly demonstrates the use of stack for matching problems.
• Always remember: push opening brackets, pop and match for closing brackets.
• It’s a common interview question and a great example of LIFO property in action.

---

6. 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!

---

7. Conclusion

In this blog, I explored some fundamental yet highly practical stack and queue problems that frequently appear in coding interviews and competitive programming:

• Implementing Stack using Queues (both 1 and 2 queue methods)
• Implementing Queue using Stacks (Dequeue Costly & Amortized O(1) methods)
• Valid Parentheses problem using stack

Through these exercises, I learned how LIFO and FIFO principles can be simulated across different data structures, how to make certain operations costly or efficient depending on the scenario, and how amortized analysis can help optimize time complexity.

By practicing these problems, I strengthened both my problem-solving skills and my understanding of data structure fundamentals, which are critical for interviews and real-world applications.

I will continue experimenting with variations, analyzing complexity, and documenting my journey — this is how mastery is built!

👉 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 🚀.