線性結(jié)構(gòu)的概念

• 線性結(jié)構(gòu)是一種有序數(shù)據(jù)項的集合，可以有零個或多個數(shù)據(jù)項题翻，其中每個數(shù)據(jù)項都有唯一的前驅(qū)和后繼宽涌，除了第一個沒有前驅(qū)平夜，最后一個沒有后繼

• 線性表包括列表，棧卸亮，隊列等不同的抽象數(shù)據(jù)結(jié)構(gòu)忽妒，不同的線性表主要體現(xiàn)在于對于數(shù)據(jù)項的增刪改查的方式以及性能差異

三種主要線性數(shù)據(jù)結(jié)構(gòu)類型

列表-LIST

• python中包含了一個內(nèi)建的列表類型，是基于數(shù)組進行實現(xiàn)的嫡良，但其實還有幾種不同的實現(xiàn)方法,下面主要介紹兩種經(jīng)典的實現(xiàn)（數(shù)組和鏈表）

順序存儲（數(shù)組實現(xiàn)）

• 底層物理結(jié)構(gòu)是數(shù)組锰扶，而數(shù)組用一段連續(xù)的內(nèi)存存放，所以在內(nèi)存中數(shù)據(jù)項是相互挨在一起的寝受，只要知道了此列表在內(nèi)存地址中的起始位置，就能通關(guān)偏移量的大小定位到其他數(shù)據(jù)項的位置罕偎，基于索引

數(shù)組兩大特點

• 支持隨機訪問
• 存儲在一塊連續(xù)的內(nèi)存上

你所要了解的數(shù)組操作

增加數(shù)組大小

1. 創(chuàng)建一個新的很澄，更大的數(shù)組（申請更大的內(nèi)存空間）
2. 將原數(shù)據(jù)復(fù)制到新的數(shù)組中（這樣新數(shù)組就有更大的空間容納數(shù)據(jù)項）
3. 將指向就數(shù)組的變量重新指向新數(shù)組，舊數(shù)組的內(nèi)存則被回收

減小數(shù)組的大小

1. 創(chuàng)建一個更小的數(shù)組
2. 將原數(shù)組內(nèi)容復(fù)制到新數(shù)組
3. 將新數(shù)組設(shè)置為新的數(shù)組對象

數(shù)組中插入一項

1. 先檢查數(shù)組大小是否夠用颜及，不夠用先申請空間
2. 從數(shù)組最后一項的位置開始直到要插入數(shù)據(jù)項的索引位置甩苛，將每個數(shù)據(jù)項都往后移動一個位置
3. 這樣就會在目標(biāo)位置空出一個位置給新的數(shù)據(jù)項插入

數(shù)組中刪除一項

1. 先將目標(biāo)索引位置的數(shù)據(jù)項從數(shù)組中移除
2. 將索引位置之后的所有數(shù)組向前移動一位

時間復(fù)雜度

# O(1)
搜索第i項/替換第i項/從末尾追加/從末尾刪除/
# O(n)
從第i個位置插入/刪除/增加數(shù)組容量/減小數(shù)組容量

鏈?zhǔn)酱鎯Γㄦ湵韺崿F(xiàn)）

特點

• 由于數(shù)組結(jié)構(gòu)的列表對于刪除和插入的性能不是很好，所以構(gòu)造了以鏈表作為底層結(jié)構(gòu)的實現(xiàn)
• 鏈表結(jié)構(gòu)和數(shù)組結(jié)構(gòu)的不同主要體現(xiàn)在每個數(shù)據(jù)項不光含有數(shù)據(jù)信息俏站，還另外維護了一個指針元素讯蒲，這兩部分合起來稱之為一個節(jié)點。而鏈表實現(xiàn)的基本元素就是節(jié)點肄扎，單鏈表的節(jié)點包含兩個部分墨林，數(shù)據(jù)項的引用以及到下一個節(jié)點的引用
• 鏈表結(jié)構(gòu)中，對于單純的數(shù)據(jù)項犯祠，在內(nèi)存中的相對位置沒有規(guī)則旭等，但是可以通過每個節(jié)點中指針信息指向下一個數(shù)據(jù)項在內(nèi)存中的位置，這樣就形成鏈條一樣的形狀衡载，故稱之為鏈表結(jié)構(gòu)

構(gòu)建節(jié)點類

# 構(gòu)建節(jié)點類
class Node:
  def __init__(self, data, next=None):
    self.data = data
    self.next = next
# 一般來講搔耕，初始化次類會創(chuàng)建一個空鏈接或是新的Node對象

生成鏈表

head = None
for i in range(n):
  head = Node(i, head)
# 假設(shè)n=3，生成的鏈表是這個樣子的：2->1->0->None痰娱，此時head=Node(2,指向數(shù)據(jù)項為1的節(jié)點)
# 你會發(fā)現(xiàn)弃榨，數(shù)據(jù)項的遍歷和節(jié)點生成以相反的方式呈現(xiàn)（當(dāng)然菩收，這只是一種生成鏈表的方式，也可以通過程序設(shè)計鲸睛，保證數(shù)據(jù)項和節(jié)點生成的一致性）

鏈表操作(代碼實現(xiàn))

遍歷

# 正確的做法一般來講访诱，會構(gòu)建一個新的變量憨闰，初始化為鏈表的head指針，用指針去遍歷整個鏈表
temp = head
while temp !=None:
  temp = temp.next

# 錯誤的遍歷方法，因為head在變化卜范，最后的結(jié)果就是，head是None窄俏，前面的節(jié)點全都刪除了
while head !=None:
  head = head.next

搜索目標(biāo)值

# 構(gòu)建一個新的變量脱货，初始化為鏈表的head指針，通過遍歷搜索目標(biāo)值
temp = head
while temp != None and temp.data != target_data:
  probe = probe.next
if probe != None:
  print("success to find")
 else:
  print("fail to find")

替換第i項位置的數(shù)據(jù)

temp = head
# 假設(shè)替換索引為5的節(jié)點
index = 5
# 要么遍歷到鏈表結(jié)尾风瘦，鏈表長度不夠队魏，結(jié)束循環(huán)，要么找到鏈表要替換的位置万搔，結(jié)束循環(huán)
while temp != None and index > 0:
  temp = temp.next
  index -= 1
if temp == None:
  print("fail to replace")
else:
  temp.data = target

在任意索引位置插入節(jié)點

# 兩種情況胡桨，要么索引大于鏈表長度，那么插在最后瞬雹，要么索引小于鏈表昧谊，插入索引位置
if head is None or index < 0:
  head= Node(new_data, head)
else:
  temp = head
  # index > 1是為了放置新節(jié)點在（index-1）到index之間
  if temp.next != None and index > 1:
    temp = temp.next
    index -= 1
  temp.next = Node(new_data, temp.next)

在任意位置刪除節(jié)點

# 這里只考慮索引小于鏈表長度
temp = head
index = 5
while temp.next.next != None and index > 1:
  temp = temp.next
  index -= 1
temp.next = temp.next.next

時間復(fù)雜度

# O(1)
從開始處插入節(jié)點/從開始處刪除節(jié)點
# O(n)
在第i個位置訪問/替換(平均情況),在第i個位置插入/刪除(平均情況)

列表接口

• 一般列表這種結(jié)構(gòu)，都會提供如下幾個接口

add(data)               # 添加數(shù)據(jù)項
insert(index, data)     # 插入數(shù)據(jù)項到索引位置
replace(index, data)    # 將索引位置的數(shù)據(jù)項替換
pop(index)              # 將索引位置的數(shù)據(jù)項彈出列表
remove(data)            # 刪除某個數(shù)據(jù)項

棧-STACK

特點

• 棧結(jié)構(gòu)也可以通過數(shù)組或者鏈表結(jié)構(gòu)設(shè)計實現(xiàn)

• 數(shù)據(jù)項的加入和移除都限制在一端酗捌，這個端點一般稱之為棧頂

• 后進先出的結(jié)構(gòu)特點（LIFO）呢诬，越早進入棧結(jié)構(gòu)的數(shù)據(jù)越晚離開棧

生活中的例子（加深理解）

• 一摞盤子，想取的話只能先取最上面的一個胖缤，然后下一個尚镰，依次類推，但如果想放新的盤子上去哪廓，也只能將新盤子放在所有盤子的最上面狗唉，然后再摞一個，以此類推涡真。這個（頂端）用來拿或者取盤子的位置分俯，抽象出來一個概念，稱之為棧頂综膀。盤子最下面不參與任何的操作澳迫，稱之為棧底。

經(jīng)典應(yīng)用

• 編譯器基本功能中的對于各種括號（"(){}[]"）的正確匹配
• 回溯算法
• 管理計算機內(nèi)存支持函數(shù)和方法的調(diào)用
• 中綴表達式轉(zhuǎn)換為后綴表達式剧劝；計算后綴表達式
  • 利用運算符優(yōu)先級的思想（轉(zhuǎn)換）
    1. 如果遇到操作數(shù)橄登，我們就直接將其輸出
    2. 如果遇到操作符，則我們將其放入到棧中，遇到左括號時我們也將其放入棧中拢锹。
    3. 如果遇到一個右括號谣妻，則將棧元素彈出，將彈出的操作符輸出直到遇到左括號為止卒稳。注意蹋半，左括號只彈出并不輸出。
    4. 如果遇到任何其他的操作符充坑，如（“+”减江， “*”，“（”）等捻爷，從棧中彈出元素直到遇到發(fā)現(xiàn)更低優(yōu)先級的元素(或者棧為空)為止辈灼。彈出完這些元素后，才將遇到的操作符壓入到棧中也榄。有一點需要注意巡莹，只有在遇到" ) "的情況下我們才彈出" ( "，其他情況我們都不會彈出" ( "
    5. 如果我們讀到了輸入的末尾甜紫，則將棧中所有元素依次彈出

部分應(yīng)用代碼實現(xiàn)

# 我們這里簡單的用python內(nèi)置列表作為基礎(chǔ)結(jié)構(gòu)實現(xiàn)棧結(jié)構(gòu)
class Stack:
    """利用列表（底層為數(shù)組）構(gòu)建棧的抽象結(jié)構(gòu)"""
    def __init__(self):
        self._items = []

    def size(self):
        return len(self._items)

    def push(self, item):
        self._items.append(item)

    def pop(self):
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

    def peek(self):
        return self._items[len(self._items) - 1]
#######################################################################

# 中綴轉(zhuǎn)后綴表達式
def infix_to_suffix(expressions):
    """當(dāng)前約定中綴表達式是以空格進行分割, exp: a + b * c"""
    s = Stack()
    exp_list = expressions.split(" ")
    # 存放操作數(shù)
    num_list = []
    # 自定義優(yōu)先級降宅，"("的存在是為了有多重括號存在時，保證所有的+-*/都可以順利入棧
    priority_dic = {"(": 1, "+": 2, "-": 2, "*": 3, "/": 3}
    for token in exp_list:
        if token not in "+-*/()":
            num_list.append(int(token))
        elif token == "(":
            s.push(token)
        elif token == ")":
            while s.peek() != "(":
                num_list.append(s.pop())
            # 將"("彈出
            s.pop()
        else:
            while s.size() > 0 and priority_dic.get(token) <= priority_dic.get(s.peek()):
                num_list.append(s.pop())
            s.push(token)
    # 檢查棧中是否還有操作符存在囚霸，有的話腰根，依依彈出即可
    while not s.is_empty():
        num_list.append(s.pop())
    return "".join([str(i) for i in num_list])


# 計算后綴
def calc_suffix(expression):
    s = Stack()
    for token in expression:
        if token in "0123456789":
            s.push(int(token))
        else:
            # 要考慮到減法和除法順序不能顛倒的問題
            num_first = s.pop()
            num_second = s.pop()
            tmp_result = convert_to_math(token, num_first, num_second)
            s.push(tmp_result)
    return s.pop()


# 輔助函數(shù)，每兩個彈出元素的計算結(jié)果
def convert_to_math(token, num1, num2):
    if token == "*":
        return num1 * num2
    elif token == "/":
        return num2 / num1
    elif token == "-":
        return num2 - num1
    elif token == "+":
        return num1 + num2

# 測試數(shù)據(jù)
convert_ret = infix_to_suffix("3 + 5 * 2 - 5 * ( 3 + 2 )")
calcu_ret = calc_suffix(convert_ret)
print(calcu_ret)
####################################################################

# 10進制轉(zhuǎn)換為2/8/16進制的字符串格式
def to_str(n, base):
    :param n: 十進制數(shù)
    :param base: 想要轉(zhuǎn)換的進制
    :return: 
    if n < base:
        return str(n)
    elif 2 <= base <= 10:
        return to_str(n // base, base) + str((n % base))
    else:
        convert_string = "0123456789abcdef"
        return to_str(n // base, base) + convert_string[(n % base)]

ret = to_str(541, 2)
print(ret)

隊列-QUEUE

特點

• 隊列也可以由數(shù)組或是鏈表結(jié)構(gòu)設(shè)計實現(xiàn)拓型，數(shù)組的實現(xiàn)（循環(huán)數(shù)組的方法）要難于鏈表唠雕，但是性能更優(yōu)

• 隊列是一種有次序的數(shù)據(jù)集合，表現(xiàn)為向隊列中添加數(shù)據(jù)時吨述，永遠(yuǎn)在尾端添加，而移除數(shù)據(jù)則永遠(yuǎn)從隊首刪除

• 先進先出的結(jié)構(gòu)特點（FIFO）钞脂，越早進入棧結(jié)構(gòu)的數(shù)據(jù)越早離開棧

生活中的例子（加深理解）

• 排隊買票揣云，一般情況下，你應(yīng)該從買票隊伍的最后一個位置進入列隊
• 一臺打印機面向多個用戶或是程序的情況

經(jīng)典應(yīng)用

• 模擬打印機處理多任務(wù)
• 模擬道路交通冰啃，超市結(jié)賬排隊情況等
• CPU訪問
  • 多個進程訪問同一個CPU邓夕，新進程會被添加到隊列，這個隊列就是等待CPU使用的進程

部分應(yīng)用代碼實現(xiàn)

約瑟夫/熱土豆理論

# 熱土豆問題：幾個小朋友阎毅，圍成一圈焚刚，用一個熱土豆（或別的什么東西），數(shù)一個數(shù)就拋給下一個人扇调，每數(shù)到3矿咕，手上有土豆的人就站出來，然后繼續(xù)，問哪個位置的人最后剩下碳柱？

# 利用內(nèi)置數(shù)據(jù)類型列表構(gòu)建隊列數(shù)據(jù)結(jié)構(gòu)
class Queue():
    def __init__(self):
        self._items = []

    def size(self):
        return len(self._items)

    def enqueue(self, data):
        self._items.insert(0, data)

    def dequeue(self):
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

# 熱土豆問題邏輯代碼
def hot_potato(lists, num):
    q = Queue()
    # 按人名將數(shù)據(jù)項入隊
    for person in lists:
        q.enqueue(person)
    # 直到只剩下一個人捡絮，游戲結(jié)束
    while q.size() > 1:
        for i in range(num):
            q.enqueue(q.dequeue())
        q.dequeue()
    # 將最后剩下的人返回
    return q.dequeue()

# 模擬熱土豆的實例，參數(shù)分表代表參加游戲的人名以及土豆每傳遞幾次就出隊一個人
last_person = hot_potato(["A", "B", "C", "D", "E", "F", "G", "H", "I", "L", "M", "N", "O"], 3)
print(last_person)

生產(chǎn)者消費者模型

import threading
import queue
 
 
def producer():
    """
    模擬生產(chǎn)者
    :return:
    """
    for i in range(10):
        print("生產(chǎn)包子%s" %i)
        q.put("包子 %s" % i)
 
    print("開始等待所有的包子被取走...")
    q.join()  # 等待這個包子隊列被消費完畢
    print("所有的包子被取完了...")
 
 
def consumer(n):
    """
    模擬消費者
    :return:
    """
    while q.qsize() > 0:
        print("%s 取到" % n, q.get())
        q.task_done()  # 每取一個包子莲镣，便告知隊列這個任務(wù)執(zhí)行完了
 
q = queue.Queue()
 
p = threading.Thread(target=producer,)
p.start()
 
c1 = consumer("xiaochen")