python实现堆栈数据结构及其基本方法

简介: 栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

栈可以用来在函数调用的时候存储断点,做递归时要用到栈,其基本模型如下:

2019-04-08-21_16_50.png


在python中已经有实现栈的数据结构,在queue库中的LifoQueue就是一种堆栈,堆栈的实现也是线性表,在Python的queue中是通过列表这一线性顺序表实现的,其LifoQueue源码如下:

class LifoQueue(Queue):
    '''Variant of Queue that retrieves most recently added entries first.'''

    def _init(self, maxsize):
        self.queue = []

    def _qsize(self):
        return len(self.queue)

    def _put(self, item):
        self.queue.append(item)

    def _get(self):
        return self.queue.pop()


下面我们实现一个自定义的堆栈结构,首先定义一个堆栈类:

class Stack:
    """堆栈结构类"""
    def __init__(self):
        self._item = []


接着我们实现基本的方法:添加元素、弹出栈顶、返回栈顶、判断是否为空、返回堆栈大小。

class Stack:
    """堆栈结构类"""
    def __init__(self):
        self._item = []

    def push(self, item):
        """
        添加新元素
        :param item:
        :return:
        """

        self._item.append(item)

    @property
    def size(self):
        """
        返回堆栈大小
        :return:
        """

        return len(self._item)

    @property
    def is_empty(self):
        """
        判断是否为空
        :return:
        """

        return not self._item

    def pop(self):
        """
        弹出栈顶元素
        :return:
        """

        return self._item.pop()

    def peek(self):
        """
        返回栈顶元素
        :return:
        """

        return self._item[-1]


上面实现的只是基础模型,缺少异常处理和其他相关的机制,用列表实现堆栈,安全性不是很高,但是如果使用链表使用的话一次只能按序获取一个元素,从链表一端到另一端,这样安全性会更高。

2019-04-08-21_16_51.png


相关文章
|
3天前
|
算法 开发者 计算机视觉
燃爆全场!Python并查集:数据结构界的网红,让你的代码炫酷无比!
在编程的世界里,总有一些数据结构以其独特的魅力和高效的性能脱颖而出,成为众多开发者追捧的“网红”。今天,我们要介绍的这位明星,就是Python中的并查集(Union-Find)——它不仅在解决特定问题上大放异彩,更以其优雅的设计和强大的功能,让你的代码炫酷无比,燃爆全场!
15 0
|
3天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
77 64
|
12天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
|
3天前
|
Go
数据结构之 - 深入了解栈数据结构
数据结构之 - 深入了解栈数据结构
13 5
|
12天前
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
12天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
|
12天前
06_用栈来求解汉诺塔问题
06_用栈来求解汉诺塔问题
|
12天前
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
|
12天前
03_如何仅用递归函数和栈操作逆序一个栈
03_如何仅用递归函数和栈操作逆序一个栈
|
12天前
|
测试技术
02_由两个栈组成的队列
02_由两个栈组成的队列