[Rust] two stacks & stack + index
Intuition\nThe first thought anyone likely has is this is something that can be solved with a stack in some way.\n\n# Approach Two Stacks\nTwo stacks are create
# Intuition\nThe first thought anyone likely has is this is something that can be solved with a stack in some way.\n\n# Approach Two Stacks\nTwo stacks are created: a `backward` stack that can be used to navigate backward, and a `forward` stack that can be used to navigate forward.\n\nThere will always be at least one item on the `backward` stack, which will be the homepage URL.\n\nWhen going back to previous URL\'s, the items on the `backward` stack are popped and pushed onto the `forward` stack. Going forward is the opposite, assuming the `forward` stack isn\'t cleared by interjecting a new URL via `visit()`.\n\n# Complexity\n- Time complexity: $O(1)$ for `visit()`, and $O(steps)$ for `back()` and `forward()`.\n- Space complexity: $O(n)$ where $n$ the number of URL\'s visited.\n\n# Code\n```rust\nstruct BrowserHistory {\n    backward : Vec<String>,\n    forward  : Vec<String>,\n}\n\nimpl BrowserHistory {\n\n    fn new(homepage: String) -> Self {\n        Self{ backward: vec![homepage], forward: vec![] }\n    }\n    \n    fn visit(&mut self, url: String) {\n        self.backward.push(url);\n        self.forward.clear();\n    }\n    \n    fn back(&mut self, steps: i32) -> String {\n        for _ in 0..steps.min(self.backward.len() as i32 - 1) {\n            self.forward.push(self.backward.pop().unwrap());\n        }\n        self.backward.last().unwrap().clone()\n    }\n    \n    fn forward(&mut self, steps: i32) -> String {\n        for _ in 0..steps.min(self.forward.len() as i32) {\n            self.backward.push(self.forward.pop().unwrap());\n        }\n        self.backward.last().unwrap().clone()\n    }\n}\n```\n\n# Approach Stack and Index\nThis approach is similar, but has better time-complexity for a couple methods. Instead of popping items off a stack to go backward, an index is decremented. Going forward it\'s incremented.\n\nWhenever a new URL is visited, the stack is truncated and the new URL is pushed.\n\nThe home page should always be at the bottom of the stack; so to prevent it from being popped, the value of `self.index` can\'t decrement any lower than `0`. And `index + 1` is used to determine where to truncate the stack when `visit()` is called.\n\n`usize::saturating_sub()` is conveniently used to ensure that no matter how many steps back we reduce `self.index` by, it can go no lower than `0` (it would actually roll over if allowed to decrement past 0).\n\n# Complexity\n- Time complexity: $O(1)$ for `visit()`, `back()` and `forward()`.\n- Space complexity: $O(n)$.\n\n# Code\n\n```rust\nstruct BrowserHistory {\n    stack : Vec<String>,\n    index : usize,\n}\n\nimpl BrowserHistory {\n\n    fn new(homepage: String) -> Self {\n        Self{ stack: vec![homepage], index: 0 }\n    }\n    \n    fn visit(&mut self, url: String) {\n        self.index += 1;\n        self.stack.truncate(self.index);\n        self.stack.push(url);\n    }\n    \n    fn back(&mut self, steps: i32) -> String {\n        self.index = self.index.saturating_sub(steps as usize);\n        self.stack[self.index].clone()\n    }\n    \n    fn forward(&mut self, steps: i32) -> String {\n        self.index = (self.index + steps as usize).min(self.stack.len() - 1);\n        self.stack[self.index].clone()\n    }\n}\n```
['Rust']