1472. 设计浏览器历史记录

双栈

直觉

一个栈存浏览过的页面，一个栈存放弹出（back）的页面。

class BrowserHistory {
    Stack<String> back = new Stack<>();
    Stack<String> forward = new Stack<>();
    public BrowserHistory(String homepage) {
        back.push(homepage);
    }
    
    public void visit(String url) {
        back.push(url);
        while(!forward.isEmpty()){
            forward.pop();
        }
    }
    
    public String back(int steps) {
        while(steps>0&&back.size()>1){
            forward.push(back.pop());
            steps--;
        }
        return back.peek();
    }
    
    public String forward(int steps) {
        while(steps>0&&!forward.isEmpty()){
            steps--;
            back.push(forward.pop());
        }
        return back.peek();
    }
}

双向链表

直觉

浏览页面直接往链表的当前页面指针后增加节点（抛弃forward）。

class Node {
    String url;
    Node pre, next;

    public Node(String url) {
        this.url = url;
    }
}

class BrowserHistory {
    Node list, cur;

    public BrowserHistory(String homepage) {
        list = new Node(homepage);
        cur = list;
    }

    public void visit(String url) {
        Node newNode = new Node(url);
        cur.next = newNode;
        newNode.pre = cur;
        cur = cur.next;
    }

    public String back(int steps) {
        while (steps > 0 && cur != list) {
            cur = cur.pre;
            steps--;
        }

        return cur.url;
    }

    public String forward(int steps) {
        while (steps > 0 && cur.next != null) {
            cur = cur.next;
            steps--;
        }
        return cur.url;
    }

}

数组

直觉

维护当前指针和结尾指针，浏览时直接在当前指针后的位置填充。

class BrowserHistory {
    String[] list = new String[5000];
    int cur = 0;
    int end = 0;

    public BrowserHistory(String homepage) {
        list[cur] = homepage;
    }

    public void visit(String url) {
        list[++cur] = url;
        end = cur;
    }

    public String back(int steps) {
        while (steps > 0 && cur > 0) {
            steps--;
            cur--;
        }
        return list[cur];
    }

    public String forward(int steps) {
        while (steps > 0 && cur < end) {
            steps--;
            cur++;
        }
        return list[cur];
    }

}