如何用棧實現瀏覽器的前進和後退？

  • 2019 年 11 月 8 日
  • 筆記

2019 年第 79 篇文章，總第 103 篇文章

數據結構與算法系列的第四篇文章，前三篇文章：

  1. 數據結構算法入門–一文了解什麼是複雜度
  2. 一文了解數組
  3. 數據結構算法入門–鏈表

前言

瀏覽器的前進和後退功能怎麼用棧來實現呢？

這裡先介紹一下棧的定義和實現，並介紹它的一些常用的應用，最後再簡單實現一個簡單的瀏覽器前進和後退的操作。

棧是一種「操作受限」的線性表，只允許在一端插入和刪除數據，特點就是後進先出、先進後出。

目錄：

  • 棧的實現
  • 棧在函數調用中的應用
  • 棧在表達式求值中的應用
  • 棧在括號匹配中的應用
  • 利用棧實現瀏覽器的前進和後退功能

棧的實現

棧既可以通過數組實現，也可以通過鏈表實現。數組實現的棧，稱為順序棧；鏈表實現的棧，稱為鏈式棧。

這裡用 Python 分別實現這兩種棧。

順序棧的實現代碼：

from typing import Optional    class ArrayStack:    def __init__(self, nums):        # 初始化數組        self._data = list()        # 數組的大小        self._nums = nums        # 數組元素個數        self._count = 0      def push(self, data) -> bool:        '''        入棧        :param data:        :return:        '''        if (self._count + 1) == self._nums:            # 棧已經滿了            return False          self._data.append(data)        self._count += 1        return True      def pop(self) -> Optional[int]:        '''        出棧        :return:        '''        if self._count:            value = self._data[self._count - 1]            self._data.pop(self._count - 1)            self._count -= 1            return value      def __repr__(self) -> str:        '''        打印棧        :return:        '''        nums = reversed(self._data)          return " ".join("[{}]".format(num) for num in nums)    if __name__ == '__main__':    stack = ArrayStack(10)      for i in range(15):        stack.push(i)    # 輸出：[8] [7] [6] [5] [4] [3] [2] [1] [0]    print(stack)      for _ in range(5):        stack.pop()    # 輸出：[3] [2] [1] [0]    print(stack)

鏈式棧的實現代碼：

from typing import Optional    # 鏈表結點類class Node:    def __init__(self, data: int, next=None):        self._data = data        self._next = next    class LinkedStack:    """    鏈表實現的棧    """      def __init__(self):        self._top = None      def push(self, value: int):        '''        入棧，將新結點放在鏈表首部        :param value:        :return:        '''        new_top = Node(value)        new_top._next = self._top        self._top = new_top      def pop(self) -> Optional[int]:        if self._top:            value = self._top._data            self._top = self._top._next            return value      def __repr__(self) -> str:        '''        打印棧元素        :return:        '''        current = self._top        nums = []        while current:            nums.append(current._data)            current = current._next        return " ".join("[{}]".format(num) for num in nums)  if __name__ == '__main__':    stack = LinkedStack()    # 入棧    for i in range(9):        stack.push(i)    # 輸出：入棧結果:  [8] [7] [6] [5] [4] [3] [2] [1] [0]    print('入棧結果: ', stack)    # 出棧    for _ in range(3):        stack.pop()    # 輸出：出棧結果:  [5] [4] [3] [2] [1] [0]    print('出棧結果: ', stack)

看完上述實現代碼，這裡思考下棧的操作的時間和空間複雜度分別是多少呢？

對於空間複雜度，入棧和出棧都只需要一兩個臨時變量存儲空間，所以空間複雜度是 O(1)。

時間複雜度，入棧和出棧也只是涉及到棧頂的數據的操作，因此時間複雜度是 O(1)。

棧在函數調用中的應用

棧的一個比較經典的應用就是函數調用棧。

操作系統給每個線程分配了一塊獨立的內存空間，它被組織為「棧」這種結構，用來存儲函數調用時的臨時變量。每進入一個函數，就會將臨時變量作為一個棧幀入棧，當被調用的函數執行完成，返回之後，將這個函數對應的棧幀出棧。

下面是一個例子：

def add(x, y):    sum = x + y    return sum  def main():    a = 1    ret = 0    res = 0    ret = add(3, 5)    res = a + ret    print('%d', res)

這段代碼中，main() 函數調用了 add() 函數，獲取計算結果，並且和變量 a 相加，得到最終結果 res ，然後打印。這段代碼中的函數調用棧情況如下所示，它顯示的是在調用 add() 函數並執行相加時的情況。

棧在表達式求值中的應用

棧的另一個常用場景就是實現表達式求值，編譯器實現表達式求值的方法是通過兩個棧來實現。一個保存操作數，一個保存運算符。其實現思路如下：

  1. 從左到右遍歷表達式，遇到數字，就壓入操作數棧；
  2. 遇到運算符，就和運算符棧的棧頂元素進行比較，如果比棧頂元素的優先級高，就壓入棧；如果比棧頂元素的優先級低或者是相同優先級，就取出棧頂的運算符，然後從操作數棧的棧頂取 2 個操作數，進行計算後將計算結果放入操作數棧，接着繼續比較運算符和當前運算符棧的棧頂元素。

這裡給出一個例子，如何計算表達式 3+5*8-6，如下圖所示：

棧在括號匹配中的應用

棧的第三個應用是可以檢查表達式中的括號是否匹配。

通過棧來檢查括號匹配問題的方法思路如下：

  1. 從左到右掃描表達式，遇到左括號，壓入棧中；
  2. 如果掃描到右括號，從棧頂取出一個左括號，如果可以匹配，繼續掃描表達式；但如果不能匹配，或者棧為空，說明表達式是非法的格式；
  3. 掃描完畢後，棧說空，說明表達式是合法格式；否則，說明還有未匹配的左括號，表達式是非法格式。

利用棧實現瀏覽器的前進和後退功能

最後一個應用是實現瀏覽器的前進和後退功能，這裡採用兩個棧來解決。

我們使用兩個棧，X 和 Y，我們把首次瀏覽的頁面依次壓入棧 X，當點擊後退按鈕時，再依次從棧 X 中出棧，並將出棧的數據依次放入棧 Y。當我們點擊前進按鈕時，我們依次從棧 Y 中取出數據，放入棧 X 中。當棧 X 中沒有數據時，那就說明沒有頁面可以繼續後退瀏覽了。當棧 Y 中沒有數據，那就說明沒有頁面可以點擊前進按鈕瀏覽了。

實現代碼如下所示：

from Stack.linked_stack import LinkedStackimport copy    class NewLinkedStack(LinkedStack):    def is_empty(self):        return not self._top    class Browser():    def __init__(self):        # forward_stack 保存打開瀏覽器或者前進時候的頁面        self.forward_stack = NewLinkedStack()        # back_stack 保存後退時候從 forward_stack 彈出的頁面        self.back_stack = NewLinkedStack()      def can_forward(self):        if self.back_stack.is_empty():            return False        return True      def can_back(self):        if self.forward_stack.is_empty():            return False        return True      def open(self, url):        print('Open new url {}'.format(url))        self.forward_stack.push(url)      def back(self):        if self.forward_stack.is_empty():            return        # 點擊後退按鈕，從 forward_stack 中彈出當前頁面，並保存到 back_stack 中        top = self.forward_stack.pop()        self.back_stack.push(top)        print('back to {}'.format(top))      def forward(self):        if self.back_stack.is_empty():            return        # 點擊前進按鈕，從　back_stack 中彈出，然後保存到 forward_stack 中        top = self.back_stack.pop()        self.forward_stack.push(top)        print('forward to {}'.format(top))      def __repr__(self):        copy_forward_stack = copy.deepcopy(self.forward_stack)        url_list = list()        while not copy_forward_stack.is_empty():            url_list.append(copy_forward_stack.pop())        return " ".join("{}".format(url) for url in url_list)    if __name__ == '__main__':    browser = Browser()    browser.open('a')    browser.open('b')    browser.open('c')    print('open the browser: {}'.format(browser))    if browser.can_back():        browser.back()      if browser.can_forward():        browser.forward()      browser.back()    browser.back()    browser.back()    print('browser: {}'.format(browser))

輸出結果：

Open new url aOpen new url bOpen new url copen the browser: c b aback to cforward to cback to cback to bback to abrowser:

總結

本文先介紹了如何實現一個棧，然後介紹了棧的幾個應用，包括函數調用、表達式求值、括號匹配、瀏覽器前進和後退的實現等。

VirMach 便宜 VPS

QNews

QNews