Real-World Simulation: Browser Back Button

Problem Statement

Write a Java program that simulates a browser’s back button functionality using a stack. The program should allow users to input a list of URLs to push onto the stack, representing page navigation, and print the current page each time the back button is simulated by popping a URL from the stack. The current page is the topmost URL on the stack after each operation. Test the implementation with various sequences of push and pop operations, including edge cases like empty stacks and null inputs. You can visualize this as a stack of visited webpages, where each new page is added to the top, and pressing the back button removes the current page to reveal the previous one.

Input: A sequence of operations, where each operation is either:

Push: Add a URL (string) to the stack (e.g., "https://example.com").
Pop: Simulate the back button by removing the top URL and revealing the new top. Output: For each operation, print the operation performed and the current page (top of the stack) or a message if the stack is empty. Constraints:
Stack size is between 0 and 10^5.
URLs are non-empty strings containing printable ASCII characters, or null (handled gracefully).
The stack may be empty when pop is called. Example:
Input: Operations = [push("page1"), push("page2"), pop, push("page3"), pop]

Output:

Pushed page1, Current page: page1
Pushed page2, Current page: page2
Popped page2, Current page: page1
Pushed page3, Current page: page3
Popped page3, Current page: page1

Explanation: Push adds URLs to the stack; pop removes the top URL, showing the previous one.
Input: Operations = [pop on empty stack]
Output: Popped, Stack empty

Pseudocode

CLASS StringStack
    SET array to new string array of size 1000
    SET top to -1
    
    FUNCTION push(url)
        IF top equals array length - 1 THEN
            RETURN false (stack full)
        ENDIF
        INCREMENT top
        SET array[top] to url
        RETURN true
    ENDFUNCTION
    
    FUNCTION pop()
        IF top equals -1 THEN
            RETURN null (stack empty)
        ENDIF
        SET url to array[top]
        DECREMENT top
        RETURN url
    ENDFUNCTION
    
    FUNCTION peek()
        IF top equals -1 THEN
            RETURN null (stack empty)
        ENDIF
        RETURN array[top]
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN top equals -1
    ENDFUNCTION
ENDCLASS

FUNCTION simulateBrowser(operations)
    CREATE stack as new StringStack
    FOR each operation in operations
        IF operation.type equals "push" THEN
            CALL stack.push(operation.url)
            PRINT pushed url and current page (stack.peek())
        ELSE IF operation.type equals "pop" THEN
            SET popped to stack.pop()
            IF popped is null THEN
                PRINT stack empty message
            ELSE
                PRINT popped url and current page (stack.peek())
            ENDIF
        ENDIF
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences
    FOR each testCase in testCases
        PRINT test case details
        CALL simulateBrowser(testCase)
    ENDFOR
ENDFUNCTION

Algorithm Steps

Define a StringStack class with: a. An array to store URLs (strings), with a top index. b. Methods: push (add URL), pop (remove and return top URL), peek (view top URL), isEmpty (check if empty).
In the simulateBrowser method: a. Create a new StringStack. b. For each operation:
- If "push", push the URL and print the current page (top of stack).
- If "pop", pop the top URL and print the new current page (top of stack) or "Stack empty" if empty.
In the main method, test with sequences of push and pop operations, including empty stacks, single URLs, and null URLs.

Java Implementation

import java.util.*;

public class BrowserBackButtonSimulation {
    // Custom stack implementation for strings
    static class StringStack {
        private String[] array;
        private int top;
        private static final int DEFAULT_SIZE = 1000;

        public StringStack() {
            array = new String[DEFAULT_SIZE];
            top = -1;
        }

        public boolean push(String url) {
            if (top == array.length - 1) {
                return false; // Stack full
            }
            array[++top] = url;
            return true;
        }

        public String pop() {
            if (top == -1) {
                return null; // Stack empty
            }
            return array[top--];
        }

        public String peek() {
            if (top == -1) {
                return null; // Stack empty
            }
            return array[top];
        }

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

    // Helper class for operations
    static class Operation {
        String type;
        String url; // For push operations

        Operation(String type, String url) {
            this.type = type;
            this.url = url;
        }
    }

    // Simulates browser back button functionality
    public void simulateBrowser(List<Operation> operations) {
        StringStack stack = new StringStack();
        for (Operation op : operations) {
            if (op.type.equals("push")) {
                boolean success = stack.push(op.url);
                if (success) {
                    System.out.println("Pushed " + op.url + ", Current page: " + stack.peek());
                } else {
                    System.out.println("Push " + op.url + " failed: Stack full");
                }
            } else if (op.type.equals("pop")) {
                String popped = stack.pop();
                if (popped == null) {
                    System.out.println("Popped, Stack empty");
                } else {
                    System.out.println("Popped " + popped + ", Current page: " + 
                                       (stack.peek() != null ? stack.peek() : "Stack empty"));
                }
            }
        }
    }

    // Main method to test browser simulation
    public static void main(String[] args) {
        BrowserBackButtonSimulation simulator = new BrowserBackButtonSimulation();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal sequence
        List<Operation> case1 = Arrays.asList(
            new Operation("push", "https://page1.com"),
            new Operation("push", "https://page2.com"),
            new Operation("pop", null),
            new Operation("push", "https://page3.com"),
            new Operation("pop", null)
        );
        testCases.add(case1);
        
        // Test case 2: Empty stack
        List<Operation> case2 = Arrays.asList(
            new Operation("pop", null)
        );
        testCases.add(case2);
        
        // Test case 3: Single URL
        List<Operation> case3 = Arrays.asList(
            new Operation("push", "https://single.com"),
            new Operation("pop", null)
        );
        testCases.add(case3);
        
        // Test case 4: Multiple pushes
        List<Operation> case4 = Arrays.asList(
            new Operation("push", "https://site1.com"),
            new Operation("push", "https://site2.com"),
            new Operation("push", "https://site3.com"),
            new Operation("pop", null),
            new Operation("pop", null)
        );
        testCases.add(case4);
        
        // Test case 5: Null URL
        List<Operation> case5 = Arrays.asList(
            new Operation("push", null),
            new Operation("pop", null)
        );
        testCases.add(case5);

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            System.out.println("Test case " + (i + 1) + ":");
            simulator.simulateBrowser(testCases.get(i));
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1:
Pushed https://page1.com, Current page: https://page1.com
Pushed https://page2.com, Current page: https://page2.com
Popped https://page2.com, Current page: https://page1.com
Pushed https://page3.com, Current page: https://page3.com
Popped https://page3.com, Current page: https://page1.com

Test case 2:
Popped, Stack empty

Test case 3:
Pushed https://single.com, Current page: https://single.com
Popped https://single.com, Current page: Stack empty

Test case 4:
Pushed https://site1.com, Current page: https://site1.com
Pushed https://site2.com, Current page: https://site2.com
Pushed https://site3.com, Current page: https://site3.com
Popped https://site3.com, Current page: https://site2.com
Popped https://site2.com, Current page: https://site1.com

Test case 5:
Pushed null, Current page: null
Popped null, Current page: Stack empty

Explanation:

Test case 1: Pushes "page1", "page2", pops to "page1", pushes "page3", pops to "page1".
Test case 2: Pop on empty stack returns "Stack empty".
Test case 3: Pushes single URL, pops to empty stack.
Test case 4: Multiple pushes, then pops back to "site1".
Test case 5: Pushes null URL, pops to empty stack.

How It Works

StringStack:
- Uses an array to store URLs, with top tracking the latest element.
- push: Adds a URL if the stack isn’t full.
- pop: Removes and returns the top URL if not empty.
- peek: Returns the top URL without removing it.
- isEmpty: Checks if the stack is empty.
simulateBrowser:
- Pushes URLs to simulate navigation, prints current page.
- Pops URLs to simulate back button, prints new current page or "Stack empty".
Example Trace (Test case 1):
- Push "page1": stack = ["page1"], current = "page1".
- Push "page2": stack = ["page1", "page2"], current = "page2".
- Pop: Removes "page2", current = "page1".
- Push "page3": stack = ["page1", "page3"], current = "page3".
- Pop: Removes "page3", current = "page1".
Main Method: Tests normal sequences, empty stack, single URL, multiple pushes, and null URL.

Complexity Analysis Table

Operation	Time Complexity	Space Complexity
Push/Pop/Peek	O(1)	O(1)
Full Algorithm	O(n)	O(n)

Note:

n is the number of operations.
Time complexity: O(1) for each push, pop, or peek; O(n) for processing n operations.
Space complexity: O(n) for the stack storing up to n URLs.
Worst case: O(n) time and O(n) space for many push operations.

✅ Tip: Use a stack to simulate browser navigation, as its LIFO nature naturally tracks the history of visited pages. Test with sequences that include multiple pops to verify the back button functionality.

⚠ Warning: Handle null URLs and empty stack cases to avoid unexpected behavior. Ensure the stack size is sufficient to accommodate the input sequence.

Keyboard shortcuts

Java Data Structures and Algorithms for Beginners