Two Stacks vs. List
Two stacks (first solution) are natural fit for this problem. It\'s easier to implement during the contest. Using a single list (second solution) is faster, but
Two stacks (first solution) are natural fit for this problem. It\'s easier to implement during the contest. Using a single list (second solution) is faster, but it\'s a bit trickier to maintain the current position.\n\n> One thing that is unclear is what should we do if we visit exactly the same url. In the real browser, that would not create a history item. But for this problem we are supposed to do. They should better clarify that int the description!\n\n**Two Stacks**\nThe top of the first stack is the first element in the back history. And the top of the other stack - first element of the forward history. Move urls from one stack to another as you go back and forward.\n\n```cpp\nstack<string> h_back, h_forward;\nstring cur;\nBrowserHistory(string homepage) { cur = homepage; }\nvoid visit(string url) {\n    h_forward = stack<string>();\n    h_back.push(cur);\n    cur = url;\n}\nstring back(int steps) {\n    while (--steps >= 0 && !h_back.empty()) {\n        h_forward.push(cur);\n        cur = h_back.top();\n        h_back.pop();\n    }\n    return cur;\n}\nstring forward(int steps) {\n    while (--steps >= 0 && !h_forward.empty()) {\n        h_back.push(cur);\n        cur = h_forward.top();\n        h_forward.pop();\n    }\n    return cur;\n}\n```\n**List**\n```cpp\nvector<string> history;\nint pos = 0;\nBrowserHistory(string homepage) { history.push_back(homepage); }\nvoid visit(string url) {\n    ++pos;\n    history.resize(pos);\n    history.push_back(url);\n}\nstring back(int steps) {\n    pos = max(0, pos - steps);\n    return history[pos];\n}\nstring forward(int steps) {\n    pos = min((int)history.size() - 1, pos + steps);\n    return history[pos];\n}\n```
[]