# 1472. Design Browser History
###### tags: `Leetcode` `Medium` `Bloomberg`
Link: https://leetcode.com/problems/design-browser-history/
## 思路
### 一个ArrayList 所有操作的时间复杂度都是O(1)
用curr记录现在的位置，end记录最后一个有效位置
### 双栈
每次back，都把pop出来的放进forward里面
每次forward，都把pop出来的放进back里面
如果back size=1 说明只剩下homepage了，就不用再pop了
如果forward size = 0, 也不需要再pop
如果visit来了，就清空forward
## Code
### List

class BrowserHistory:

    def __init__(self, homepage: str):
        self.history = [homepage]
        self.curr = 0
        self.end = 0

    def visit(self, url: str) -> None:
        if self.curr+1>=len(self.history):
            self.history.append(url)
        else:
            self.history[self.curr+1] = url
        self.curr += 1
        self.end = self.curr

    def back(self, steps: int) -> str:
        self.curr = 0 if self.curr<=steps else self.curr-steps
        return self.history[self.curr]

    def forward(self, steps: int) -> str:
        self.curr = self.end if self.curr+steps>=self.end else self.curr+steps
        return self.history[self.curr]

class BrowserHistory {
    List<String> history;
    int curr;
    int end;
    public BrowserHistory(String homepage) {
        history = new ArrayList<>();
        history.add(homepage);
        curr = 0;
        end = 0;
    }
    
    public void visit(String url) {
        if(history.size()-1<=curr){
            history.add(url);
            curr+=1;
        }
        else{
            history.set(++curr, url);
        }
        end = curr;
    }
    
    public String back(int steps) {
        curr = curr-steps>=0?curr-steps:0;
        return history.get(curr);
    }
    
    public String forward(int steps) {
        curr = curr+steps>=end?end:curr+steps;
        return history.get(curr);
    }
}

### 双栈

class BrowserHistory {
    Stack<String> bck;
    Stack<String> fward;
    public BrowserHistory(String homepage) {
        bck = new Stack();
        fward = new Stack();
        bck.push(homepage);
    }
    
    public void visit(String url) {
        bck.push(url);
        while(fward.size()!=0){
            fward.pop();
        }
    }
    
    public String back(int steps) {
        for(int i = 0;i < steps;i++){
            if(bck.size()!=1){
                fward.push(bck.pop());
            }
        }
        return bck.peek();
    }
    
    public String forward(int steps) {
        for(int i = 0;i < steps;i++){
            if(fward.size()!=0){
                bck.push(fward.pop());
            }
        }
        return bck.peek();
    }
}