Design Browser History

Two Stacks of Pages — The pages behind and ahead of the open one; back and forward move them one step at a time.

class BrowserHistory {
    vector<string> behind, ahead;             // the pages before and after the open one, the nearest last
    string open;
public:
    BrowserHistory(string homepage) : open(homepage) {
    }

    void visit(string url) {
        behind.push_back(open);
        open = url;
        ahead.clear();                        // the pages that were ahead are forgotten
    }

    string back(int steps) {
        while (steps-- > 0 && !behind.empty()) {   // one page at a time
            ahead.push_back(open);
            open = behind.back();
            behind.pop_back();
        }
        return open;
    }

    string forward(int steps) {
        while (steps-- > 0 && !ahead.empty()) {
            behind.push_back(open);
            open = ahead.back();
            ahead.pop_back();
        }
        return open;
    }
};

class BrowserHistory:
    def __init__(self, homepage: str):
        self.behind = []                      # the pages before the open one, the nearest last
        self.ahead = []                       # the pages after it, the nearest last
        self.open = homepage

    def visit(self, url: str) -> None:
        self.behind.append(self.open)
        self.open = url
        self.ahead.clear()                    # the pages that were ahead are forgotten

    def back(self, steps: int) -> str:
        while steps and self.behind:          # one page at a time
            self.ahead.append(self.open)
            self.open = self.behind.pop()
            steps -= 1
        return self.open

    def forward(self, steps: int) -> str:
        while steps and self.ahead:
            self.behind.append(self.open)
            self.open = self.ahead.pop()
            steps -= 1
        return self.open

class BrowserHistory {
    private final Deque<String> behind = new ArrayDeque<>(), ahead = new ArrayDeque<>();   // the nearest on top
    private String open;

    public BrowserHistory(String homepage) {
        open = homepage;
    }

    public void visit(String url) {
        behind.push(open);
        open = url;
        ahead.clear();                           // the pages that were ahead are forgotten
    }

    public String back(int steps) {
        while (steps-- > 0 && !behind.isEmpty()) {   // one page at a time
            ahead.push(open);
            open = behind.pop();
        }
        return open;
    }

    public String forward(int steps) {
        while (steps-- > 0 && !ahead.isEmpty()) {
            behind.push(open);
            open = ahead.pop();
        }
        return open;
    }
}

var BrowserHistory = function(homepage) {
    this.behind = [];                         // the pages before the open one, the nearest last
    this.ahead = [];                          // the pages after it, the nearest last
    this.open = homepage;
};

BrowserHistory.prototype.visit = function(url) {
    this.behind.push(this.open);
    this.open = url;
    this.ahead = [];                          // the pages that were ahead are forgotten
};

BrowserHistory.prototype.back = function(steps) {
    while (steps-- > 0 && this.behind.length) {   // one page at a time
        this.ahead.push(this.open);
        this.open = this.behind.pop();
    }
    return this.open;
};

BrowserHistory.prototype.forward = function(steps) {
    while (steps-- > 0 && this.ahead.length) {
        this.behind.push(this.open);
        this.open = this.ahead.pop();
    }
    return this.open;
};

A Cursor Over an Array — back and forward move the cursor; a visit writes after it and moves the end mark.

class BrowserHistory {
    vector<string> pages;                     // pages up to end are the history; pages[at] is open
    int at = 0, end = 1;
public:
    BrowserHistory(string homepage) : pages{homepage} {
    }

    void visit(string url) {
        at++;
        if (at == (int) pages.size()) pages.push_back(url);
        else pages[at] = url;
        end = at + 1;                         // every forward page is cut off
    }

    string back(int steps) {
        at = max(0, at - steps);
        return pages[at];
    }

    string forward(int steps) {
        at = min(end - 1, at + steps);
        return pages[at];
    }
};

class BrowserHistory:
    def __init__(self, homepage: str):
        self.pages = [homepage]               # pages[:end] is the history; pages[at] is open
        self.at, self.end = 0, 1

    def visit(self, url: str) -> None:
        self.at += 1
        if self.at == len(self.pages):
            self.pages.append(url)
        else:
            self.pages[self.at] = url
        self.end = self.at + 1                # every forward page is cut off

    def back(self, steps: int) -> str:
        self.at = max(0, self.at - steps)
        return self.pages[self.at]

    def forward(self, steps: int) -> str:
        self.at = min(self.end - 1, self.at + steps)
        return self.pages[self.at]

class BrowserHistory {
    private final List<String> pages = new ArrayList<>();   // pages up to end are the history; pages[at] is open
    private int at = 0, end = 1;

    public BrowserHistory(String homepage) {
        pages.add(homepage);
    }

    public void visit(String url) {
        at++;
        if (at == pages.size()) pages.add(url);
        else pages.set(at, url);
        end = at + 1;                            // every forward page is cut off
    }

    public String back(int steps) {
        at = Math.max(0, at - steps);
        return pages.get(at);
    }

    public String forward(int steps) {
        at = Math.min(end - 1, at + steps);
        return pages.get(at);
    }
}

class BrowserHistory {
    constructor(homepage) {
        this.pages = [homepage];              // pages up to end are the history; pages[at] is open
        this.at = 0;
        this.end = 1;
    }

    visit(url) {
        this.at++;
        this.pages[this.at] = url;
        this.end = this.at + 1;               // every forward page is cut off
    }

    back(steps) {
        this.at = Math.max(0, this.at - steps);
        return this.pages[this.at];
    }

    forward(steps) {
        this.at = Math.min(this.end - 1, this.at + steps);
        return this.pages[this.at];
    }
}