[C++] two stacks with comments and 3 variations
Intuition:\ntwo stacks are used to move backward into history and forward in to current again, which is the last visit.\n\nvector are used to simulate stack and
**Intuition:**\ntwo stacks are used to move backward into history and forward in to current again, which is the last visit.\n\nvector are used to simulate stack and the rightmost is the top of stack:\n stack1: { backward2, backward1,  cur}, \n stack2: {forward2, forward1}\n \n Version 1: use vector to simulate stack\n```\nclass BrowserHistory {\npublic:  //Time/Space: O(N*steps), O(N); Coding cost: 34 Lines\n    BrowserHistory(string homepage) {\n        visit(homepage);\n    }\n    \n    void visit(string url) {\n        h_.emplace_back(url);        \n        if(!stk2_.empty()) stk2_.clear(); // future is zero\n    }\n    \n    string back(int steps) {        \n        int new_cur = max(0, (int) h_.size() - 1 - steps);        \n        int diff = h_.size() - 1  - new_cur;        \n        while(diff-- > 0){\n            stk2_.emplace_back(h_.back());\n            h_.pop_back();\n        }            \n        return h_.back();\n    }\n    \n    string forward(int steps) {                \n        int diff= min((int) stk2_.size(), steps);                \n        while(diff-- > 0){\n            h_.push_back(stk2_.back());\n            stk2_.pop_back();\n        }                \n        return h_.back();        \n    }\n    \nprivate:\n    vector<string> h_;     // history, backward\n    vector<string> stk2_; // future, foward\n};\n```\n\n\nVersion 2: use stack \n```\nclass BrowserHistory { // 2 stack simulation of history & future\npublic:  //Time/Space: O(N*steps), O(N); Coding cost: 31 Lines\n    BrowserHistory(string homepage) {\n        history_.push(homepage);\n    }\n    \n    void visit(string url) {\n        history_.push(url);\n        future_=stack<string>();\n    }\n    \n    string back(int steps) {        \n        while(steps-- > 0 && history_.size() >=2){\n            future_.push(history_.top());\n            history_.pop();            \n        }\n        return history_.top();\n    }\n    \n    string forward(int steps) {\n        while(steps-- > 0 && !future_.empty()){\n            history_.push(future_.top());\n            future_.pop();\n        }\n        return history_.top();\n    }\n    \nprivate:\n    stack<string> history_;\n    stack<string> future_;\n};\n\n```\n\nVersion 3:  array + 2 points\n```\nclass BrowserHistory {\npublic:  //Time/Space: O(N), O(N); Coding cost: 22 Lines\n    string logs[5000];\n    int p; // pointer to present\n    int t; // pointer to top\n    \n    BrowserHistory(string homepage) {\n        logs[p=t=0] = move(homepage);        \n    }\n    \n    void visit(string url) {\n        logs[t=++p]=move(url);\n    }\n    \n    string back(int steps) {\n        return logs[p=max(0, p-steps)];\n    }\n    \n    string forward(int steps) {\n        return logs[p=min(t, p+steps)];\n    }\n};\n\n```\n
['Stack', 'C']