双栈数据结构设计：浏览器前进后退功能实现

问题背景

浏览器历史记录管理是一个经典的数据结构问题。用户可以通过前进和后退按钮在访问过的页面之间导航，这需要高效的数据结构来支持这些操作。

双栈设计原理

双栈设计使用两个栈来分别存储后退和前进的历史记录。当用户访问新页面时，将当前页面压入后退栈；当用户后退时，从后退栈弹出页面并压入前进栈。

核心算法实现

class BrowserHistory:
    def __init__(self):
        self.back_stack = []      # 后退栈
        self.forward_stack = []   # 前进栈
        self.current_page = None
    
    def visit(self, url):
        """访问新页面"""
        if self.current_page:
            self.back_stack.append(self.current_page)
        self.current_page = url
        self.forward_stack.clear()  # 清空前进栈
    
    def back(self):
        """后退操作"""
        if not self.back_stack:
            return None
        self.forward_stack.append(self.current_page)
        self.current_page = self.back_stack.pop()
        return self.current_page
    
    def forward(self):
        """前进操作"""
        if not self.forward_stack:
            return None
        self.back_stack.append(self.current_page)
        self.current_page = self.forward_stack.pop()
        return self.current_page

时间复杂度分析

双栈设计的时间复杂度为O(1)，空间复杂度为O(n)，其中n为历史记录总数。这种设计非常适合频繁的前进后退操作。