232. Implement Queue using Stacks

Problem:

Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, pop, peek, empty):

Implement the MyQueue class:

• void push(int x): Push element x to the back of the queue.
• int pop(): Removes the element from the front of the queue and returns it.
• int peek(): Returns the element at the front of the queue.
• boolean empty(): Returns true if the queue is empty, otehrwise false.

Code:

class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>(); // Stores incoming elements
        outStack = new Stack<>(); // Stores elements to be dequeued
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        transferInToOut();
        return outStack.pop();
    }

    public int peek() {
        transferInToOut();
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void transferInToOut() {
        if (!outStack.isEmpty()) {
            return;
        }
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as follows:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

225. Implement Stack using Queues

Problem:

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, empty):

Implement the MyStack class:

• void push(int x): Push element x to the top of the stack.
• int pop(): Removes and returns the top element of the stack.
• int top(): Returns the top element of the stack.
• boolean empty(): Returns true if the stack is empty, otherwise false.

Code:

class MyStack {
    private Queue<Integer> mainQueue;
    private Queue<Integer> tempQueue;

    public MyStack() {
        mainQueue = new LinkedList<>();
        tempQueue = new LinkedList<>();
    }

    public void push(int x) {
        tempQueue.offer(x);
        while (!mainQueue.isEmpty()) {
            tempQueue.offer(mainQueue.poll());
        }
        // Swap the queues to make tempQueue the new mainQueue
        Queue<Integer> swap = mainQueue;
        mainQueue = tempQueue;
        tempQueue = swap;
    }

    public int pop() {
        return mainQueue.poll();
    }

    public int top() {
        return mainQueue.peek();
    }

    public boolean empty() {
        return mainQueue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

20. Valid Parentheses

Problem:

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

An input 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.
3. Every close bracket has a corresponding open bracket of the same type.

Code:

class Solution {
    public boolean isValid(String s) {
        Stack<Character> bracketStack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                bracketStack.push(')');
            } else if (ch == '[') {
                bracketStack.push(']');
            } else if (ch == '{') {
                bracketStack.push('}');
            } else if (bracketStack.isEmpty() || bracketStack.peek() != ch) {
                return false;
            } else {
                bracketStack.pop();
            }
        }
        return bracketStack.isEmpty();
    }
}

1047. Remove All Adjacent Duplicates In String

Problem:

Given a string S consisting of lowercase English letters, remove all adjacent duplicate characters repeatedly until no more duplicates can be removed. Return the final string after all such duplicate removals. The answer is guaranteed to be unique.

Code:

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> charStack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!charStack.isEmpty() && charStack.peek() == ch) {
                charStack.pop();
            } else {
                charStack.push(ch);
            }
        }
        StringBuilder result = new StringBuilder();
        while (!charStack.isEmpty()) {
            result.append(charStack.pop());
        }
        return result.reverse().toString();
    }
}