美文网首页
数据结构-堆栈和队列最简单的实现(Python实现)

数据结构-堆栈和队列最简单的实现(Python实现)

作者: 绿萝呀 | 来源:发表于2019-07-21 16:01 被阅读0次

    OK,上篇博客我们介绍了双向链表以及代码实现,这篇文章我们来学习堆栈和队列。

    队、栈和链表一样,在数据结构中非常基础一种数据结构,同样他们也有各种各样、五花八门的变形和实现方式。但不管他们形式上怎么变,队和栈都有其不变的最基本的特征,我们今天就从最基本,最简单的实现来看看队列和堆栈。

    不管什么形式的队列,它总有的一个共同的特点就是“先进先出”。怎么理解呢?就像是超市排队结账,先排队的人排在队的前面,先结账出队。这是队列的特征。

    而堆栈则和队列相反,它是“先进后出”,怎么理解呢?基本所有的编辑器都有一个撤销功能,就是按Ctrl+Z。当你写了一段文字,第一次按Ctrl+Z,消失的是你最后写的文字,第二次按Ctrl+Z,同样消失的是当前编辑器内最后写的文字。这就是一个堆栈结构的应用例子。

    好,介绍完概念我们来看一下代码如何实现这两种数据结构,这篇文章我们采用最简单方式——通过Python原生的数据类型列表来实现。上篇文章,我们介绍了链表,通过链表我们同样可以实现堆栈和队列,感兴趣的朋友不妨尝试一下。

    队列

    首先,我们来定义一个队列类:

    class Queue():
        def __init__(self):
            self.__list = list()
    

    接下来,我们给队列类添加一些方法:

    • 判断队列是否为空
        def isEmpty(self):
            return self.__list == []
    
    • 入队
        def push(self, data):
            self.__list.append(data)
    
    • 出队
        def pop(self):
            if self.isEmpty():
                return False
            return self.__list.pop(0)
    
    • 定义len()函数和print()操作类方法
        def __len__(self):
            return len(self.__list)
    
        def __str__(self):
            if self.isEmpty():
                return ''
            return ' '.join([str(x) for x in self.__list])
    

    OK,到这里,一个最简单的队列就实现啦,自己实例化一个队列测试一下吧

    下面我们来看堆栈

    堆栈

    堆栈的实现和队列类似,同样有入栈和出栈操作,我们直接上代码:

    class Stack():
        def __init__(self):
            self.__list = list()
    
        def isEmpty(self):
            return self.__list == []
    
        def push(self, data):
            self.__list.append(data)
        
        def pop(self):
            if self.isEmpty():
                return False
            return self.__list.pop()
    
        def __len__(self):
            return len(self.__list)
    
        def __str__(self):
            if self.isEmpty():
                return ''
            return ' '.join([str(x) for x in self.__list])
    

    可以看到,堆栈和队列的类实现基本相同,差别仅在出队和出栈的时候,队列是弹出第一个元素,而堆栈则是弹出最后一个元素。这也是队列和堆栈最本质的区别。

    后面的文章我们将会介绍更多种队列和堆栈的实现方式,以及它们的变形。

    好啦,最简单的队列和堆栈实现就介绍到这里了,基于链表的实现你尝试的怎么样了呢?留言告诉我吧

    相关文章

      网友评论

          本文标题:数据结构-堆栈和队列最简单的实现(Python实现)

          本文链接:https://www.haomeiwen.com/subject/afxvlctx.html