数据结构--利用Python实现常用的栈结构

栈的简介

栈作为一种数据结构，是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

栈的作用

1、内存管理中使用的堆栈；

2、基于桟实现的二叉树的遍历；

3、在处理需求中的平衡问题：

（1）判断符号是成对出现的，比如<>,{},[],()等

（2）判断这个字符串是否是回文字符串，比如：bcb, '123321',等。

栈的C语言实现：

demo:判读一个字符串是否是回文字符串，输入bcb, 输出yes

思路分析：

（1）首先，读取这行字符串，并且计算这个字符串的长度

（2）其次，如果一个字符串是回文的话，那么它的一定是对称的，计算出中点。

mid = len / 2 -1

（3）再次，我们将mid之前的数据全都写入到栈中

（4）最后，再将写入的数据一词取出，并且和mid之后的数据进行比较，如果可以匹配成功，返回输出yes，否者输出no

代码如下：

数据结构--利用Python实现常用的栈结构

栈的python语言实现：

class Node(object):
    # 定位的点的值和一个指向
    def __init__(self, val):
        # 指向元素的值,原队列第二元素
        self.val = val
        # 指向的指针
        self.next = None
class stack(object):
    # 初始化最开始的位置
    def __init__(self):
        self.top = None
        # 获取栈顶的元素
    def peek(self):
        # 如果栈顶不为空
        if self.top != None:
            # 返回栈顶元素的值
            return self.top.val
        else:
            return None
    # 添加到栈中
    def push(self,n):
        # 实例化节点
        n = Node(n)
        # 顶端元素传值给一个指针
        n.next = self.top
        self.top = n
        return n.val

    # 退出栈
    def pop(self):
        if self.top == None:
            return None
        else:
            tmp = self.top.val
            # 下移一位，进行
            self.top = self.top.next
            return tmp

if __name__ == '__main__':
    s = stack()
    s.push(1)
    print(s.pop())

数据结构--利用Python实现常用的栈结构

相关推荐