Stack & Queue

Problem 1: Implement Stack using Queues

Explanation:

Implement a stack using only queues.

Approach:

1. Single Queue with Reversal:
   • Push elements into the queue.
   • Reverse the order by rotating elements to maintain stack behavior.

Time & Space Complexity:

• Time Complexity: O(n) for push, O(1) for pop.
• Space Complexity: O(n), for storing elements.

Java Implementation:

import java.util.*;

public class StackUsingQueues {
    Queue<Integer> queue = new LinkedList<>();
    
    public void push(int x) {
        queue.offer(x);
        int size = queue.size();
        while (size-- > 1) {
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
    
    public static void main(String[] args) {
        StackUsingQueues stack = new StackUsingQueues();
        stack.push(1);
        stack.push(2);
        System.out.println("Top: " + stack.top()); // Output: 2
        System.out.println("Popped: " + stack.pop()); // Output: 2
        System.out.println("Is Empty: " + stack.empty()); // Output: false
    }
}

Example:

Input:

push(1), push(2), top(), pop(), empty()

Output:

2, 2, false

Edge Cases Considered:

• Popping from an empty stack → Should return an error or handle gracefully.
• Multiple push-pop sequences → Should maintain stack order.
• Checking empty state after operations → Should return correct boolean value.

---

Problem 2: Design Hit Counter

Explanation:

Design a hit counter that counts the number of hits received in the past 300 seconds.

Approach:

1. Queue with Timestamps:
   • Store timestamps of hits in a queue.
   • Remove outdated timestamps when retrieving counts.

Time & Space Complexity:

• Time Complexity: O(1) for hit(), O(n) for getHits() (amortized).
• Space Complexity: O(n), for storing timestamps.

Java Implementation:

import java.util.*;

public class HitCounter {
    private Queue<Integer> hits;
    
    public HitCounter() {
        hits = new LinkedList<>();
    }
    
    public void hit(int timestamp) {
        hits.offer(timestamp);
    }
    
    public int getHits(int timestamp) {
        while (!hits.isEmpty() && hits.peek() <= timestamp - 300) {
            hits.poll();
        }
        return hits.size();
    }
    
    public static void main(String[] args) {
        HitCounter counter = new HitCounter();
        counter.hit(1);
        counter.hit(2);
        counter.hit(3);
        System.out.println("Hits at 4s: " + counter.getHits(4)); // Output: 3
        System.out.println("Hits at 300s: " + counter.getHits(300)); // Output: 3
        System.out.println("Hits at 301s: " + counter.getHits(301)); // Output: 2
    }
}

Example:

Input:

hit(1), hit(2), hit(3), getHits(4), getHits(300), getHits(301)

Output:

3, 3, 2

Edge Cases Considered:

• No hits recorded → Should return 0.
• All hits outside 300s window → Should return 0.
• Frequent hits within 300s → Should return correct count.

---