摘要：本篇主要實(shí)現(xiàn)四種數(shù)據(jù)結(jié)構(gòu)，分別是數(shù)組堆棧隊(duì)列鏈表。后面的一些結(jié)構(gòu)也將用來(lái)實(shí)現(xiàn)。由于堆疊數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出的原理運(yùn)作。

本篇主要實(shí)現(xiàn)四種數(shù)據(jù)結(jié)構(gòu)，分別是數(shù)組、堆棧、隊(duì)列、鏈表。我不知道我為什么要用Python來(lái)干C干的事情，總之Python就是可以干。

所有概念性內(nèi)容可以在參考資料中找到出處

數(shù)組設(shè)計(jì)之初是在形式上依賴內(nèi)存分配而成的，所以必須在使用前預(yù)先請(qǐng)求空間。這使得數(shù)組有以下特性：

請(qǐng)求空間以后大小固定，不能再改變（數(shù)據(jù)溢出問題）；

在內(nèi)存中有空間連續(xù)性的表現(xiàn)，中間不會(huì)存在其他程序需要調(diào)用的數(shù)據(jù)，為此數(shù)組的專用內(nèi)存空間；

在舊式編程語(yǔ)言中（如有中階語(yǔ)言之稱的C），程序不會(huì)對(duì)數(shù)組的操作做下界判斷，也就有潛在的越界操作的風(fēng)險(xiǎn)（比如會(huì)把數(shù)據(jù)寫在運(yùn)行中程序需要調(diào)用的核心部分的內(nèi)存上）。

因?yàn)楹?jiǎn)單數(shù)組強(qiáng)烈倚賴電腦硬件之內(nèi)存，所以不適用于現(xiàn)代的程序設(shè)計(jì)。欲使用可變大小、硬件無(wú)關(guān)性的數(shù)據(jù)類型，Java等程序設(shè)計(jì)語(yǔ)言均提供了更高級(jí)的數(shù)據(jù)結(jié)構(gòu)：ArrayList、Vector等動(dòng)態(tài)數(shù)組。

從嚴(yán)格意義上來(lái)說(shuō):Python里沒有嚴(yán)格意義上的數(shù)組。
List可以說(shuō)是Python里的數(shù)組，下面這段代碼是CPython的實(shí)現(xiàn)List的結(jié)構(gòu)體:

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for "allocated" elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

取自CPython-Github

還有一篇文章講List實(shí)現(xiàn),感興趣的朋友可以去看看。中文版。

當(dāng)然，在Python里它就是數(shù)組。
后面的一些結(jié)構(gòu)也將用List來(lái)實(shí)現(xiàn)。

堆棧（英語(yǔ)：stack），也可直接稱棧，在計(jì)算機(jī)科學(xué)中，是一種特殊的串列形式的數(shù)據(jù)結(jié)構(gòu)，它的特殊之處在于只能允許在鏈接串列或陣列的一端（稱為堆疊頂端指標(biāo)，英語(yǔ)：top）進(jìn)行加入資料（英語(yǔ)：push）和輸出資料（英語(yǔ)：pop）的運(yùn)算。另外堆疊也可以用一維陣列或連結(jié)串列的形式來(lái)完成。堆疊的另外一個(gè)相對(duì)的操作方式稱為佇列。

由于堆疊數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)作。

先入后出，后入先出。

除頭尾節(jié)點(diǎn)之外，每個(gè)元素有一個(gè)前驅(qū)，一個(gè)后繼。

從原理可知，對(duì)堆棧(棧)可以進(jìn)行的操作有:

top():獲取堆棧頂端對(duì)象

push():向棧里添加一個(gè)對(duì)象

pop():從棧里推出一個(gè)對(duì)象

class my_stack(object):
    def __init__(self, value):
        self.value = value
        # 前驅(qū)
        self.before = None
        # 后繼
        self.behind = None

    def __str__(self):
        return str(self.value)


def top(stack):
    if isinstance(stack, my_stack):
        if stack.behind is not None:
            return top(stack.behind)
        else:
            return stack


def push(stack, ele):
    push_ele = my_stack(ele)
    if isinstance(stack, my_stack):
      stack_top = top(stack)
      push_ele.before = stack_top
      push_ele.before.behind = push_ele
    else:
      raise Exception("不要亂扔?xùn)|西進(jìn)來(lái)好么")


def pop(stack):
    if isinstance(stack, my_stack):
        stack_top = top(stack)
        if stack_top.before is not None:
            stack_top.before.behind = None
            stack_top.behind = None
            return stack_top
        else:
            print("已經(jīng)是棧頂了")

和堆棧類似，唯一的區(qū)別是隊(duì)列只能在隊(duì)頭進(jìn)行出隊(duì)操作，所以隊(duì)列是是先進(jìn)先出（FIFO, First-In-First-Out）的線性表

先入先出,后入后出

除尾節(jié)點(diǎn)外,每個(gè)節(jié)點(diǎn)有一個(gè)后繼

（可選）除頭節(jié)點(diǎn)外,每個(gè)節(jié)點(diǎn)有一個(gè)前驅(qū)

push（）:入隊(duì)

pop（）：出隊(duì)

class MyQueue():
    def __init__(self, value=None):
        self.value = value
        # 前驅(qū)
        # self.before = None
        # 后繼
        self.behind = None

    def __str__(self):
        if self.value is not None:
            return str(self.value)
        else:
            return "None"


def create_queue():
    """僅有隊(duì)頭"""
    return MyQueue()


def last(queue):
    if isinstance(queue, MyQueue):
        if queue.behind is not None:
            return last(queue.behind)
        else:
            return queue


def push(queue, ele):
    if isinstance(queue, MyQueue):
        last_queue = last(queue)
        new_queue = MyQueue(ele)
        last_queue.behind = new_queue


def pop(queue):
    if queue.behind is not None:
        get_queue = queue.behind
        queue.behind = queue.behind.behind
        return get_queue
    else:
        print("隊(duì)列里已經(jīng)沒有元素了")

def print_queue(queue):
    print(queue)
    if queue.behind is not None:
        print_queue(queue.behind)

鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大。

init():初始化

insert(): 插入

trave(): 遍歷

delete(): 刪除

find(): 查找

此處僅實(shí)現(xiàn)雙向列表

class LinkedList():
    def __init__(self, value=None):
        self.value = value
        # 前驅(qū)
        self.before = None
        # 后繼
        self.behind = None

    def __str__(self):
        if self.value is not None:
            return str(self.value)
        else:
            return "None"


def init():
    return LinkedList("HEAD")


def delete(linked_list):
    if isinstance(linked_list, LinkedList):
        if linked_list.behind is not None:
            delete(linked_list.behind)
            linked_list.behind = None
            linked_list.before = None
        linked_list.value = None


def insert(linked_list, index, node):
    node = LinkedList(node)
    if isinstance(linked_list, LinkedList):
        i = 0
        while linked_list.behind is not None:
            if i == index:
                break
            i += 1
            linked_list = linked_list.behind
        if linked_list.behind is not None:
            node.behind = linked_list.behind
            linked_list.behind.before = node
        node.before, linked_list.behind = linked_list, node


def remove(linked_list, index):
    if isinstance(linked_list, LinkedList):
        i = 0
        while linked_list.behind is not None:
            if i == index:
                break
            i += 1
            linked_list = linked_list.behind
        if linked_list.behind is not None:
            linked_list.behind.before = linked_list.before
        if linked_list.before is not None:
            linked_list.before.behind = linked_list.behind
        linked_list.behind = None
        linked_list.before = None
        linked_list.value = None


def trave(linked_list):
    if isinstance(linked_list, LinkedList):
        print(linked_list)
        if linked_list.behind is not None:
            trave(linked_list.behind)


def find(linked_list, index):
    if isinstance(linked_list, LinkedList):
        i = 0
        while linked_list.behind is not None:
            if i == index:
                return linked_list
            i += 1
            linked_list = linked_list.behind
        else:
            if i < index:
                raise Exception(404)
            return linked_list

以上所有源代碼均在Github共享，歡迎提出issue或PR，希望與大家共同進(jìn)步!

Wiki百科: 數(shù)據(jù)結(jié)構(gòu)、數(shù)組、隊(duì)列、鏈表

EOF

轉(zhuǎn)載請(qǐng)注明出處：https://zhuanlan.zhihu.com/p/...