用python实现链式栈

栈

栈是一种线性的数据结构。栈的定义是：限定仅在表尾进行插入或删除操作的线性表(线性表的介绍参见我的另一篇博文)。直观一点来看，如下图

即最后进栈的元素最先出来，又称为后进先出的线性表

链式栈基本数据结构

链式栈即是链式表构成的，通过指针相连。实现过程如下

链式栈基本单元: 节点(Node)

创建Node类

• 值域
• 指针域

class Node:
    def __init__(self, v):
        """
        :param v: the value of node
        """
        self.value = v
        self.pnext = None  # the pointer to point next

链式栈类

创建LinkedStack类

• top: 栈顶节点
• bottom: 栈底节点
• length: 栈长度

class LinkedStack:
    def __init__(self):
        self.top = None  # the top node
        self.bottom = None  # the bottom node
        self.length = 0  # the length of this stack

链式栈操作函数

self参数为对象本身，类似于C++中的this指针

压栈

创建push函数

• val: 节点值域

def push(self, val):
    """
    add a value to stack
    :param val: the value
    :return:
    """
    if not self.stack_empty():
        self.top.pnext = Node(val)
        self.top = self.top.pnext
        self.length += 1
    else:
        self.top = Node(val)
        self.bottom = self.top
        self.length += 1

出栈

创建pop函数

def pop(self):
    """
    delete the node at the top and return its value
    :return:
    """
    tmp_top = self.top
    tmp_bottom = self.bottom
    for i in range(1, self.length+1):
        if i == self.length - 1:
            self.top = tmp_bottom
            self.top.pnext = None
            self.length -= 1
        else:
            tmp_bottom = tmp_bottom.pnext
    return tmp_top.value

判断栈是否为空

创建stack_empty函数

def stack_empty(self):
    """
    if the stack is empty
    :return:
    """
    if self.top is None:
        return True
    else:
        return False

获取栈顶元素

创建get_top函数

def get_top(self):
    """
    return the value of top
    :return:
    """
    return self.top.value

遍历栈(栈底-栈顶)

创建stack_traverse函数

def stack_traverse(self):
    """
    traverse the stack
    :return:
    """
    tmp = self.bottom
    tmp_list = []
    while tmp:
        tmp_list.append(tmp.value)
        tmp = tmp.pnext
    tmp_list = tmp_list[::-1]
    print("\n-----栈顶-----")
    for val in tmp_list:
        print(val)
    print("--------------\n")

测试案例

创建程序入口

if __name__ == "__main__":
    my_stack = LinkedStack()
    my_stack.push(['start'])
    my_stack.push(12)
    my_stack.push(2323)
    my_stack.push(['end'])
    my_stack.stack_traverse()
    print(my_stack.pop())
    my_stack.stack_traverse()
    print(my_stack.length)

运行结果如下：

-----栈顶-----
['end']
2323
12
['start']
--------------

['end']

-----栈顶-----
2323
12
['start']
--------------

3

源码

点击此处访问