Python 实现数据结构-堆栈和队列的操作方法

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

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

而堆栈则和队列相反，它是“先进后出”，怎么理解呢?基本所有的编辑器都有一个撤销功能，就是按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 实现数据结构-堆栈和队列的操作方法,希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！

赞 (0)

相关推荐

  • python实现堆栈与队列的方法

    本文实例讲述了python实现堆栈与队列的方法.分享给大家供大家参考.具体分析如下: 1.python实现堆栈,可先将Stack类写入文件stack.py,在其它程序文件中使用from stack import Stack,然后就可以使用堆栈了. stack.py的程序: 复制代码 代码如下: class Stack():      def __init__(self,size):          self.size=size;          self.stack=[];         

  • 详解常用查找数据结构及算法（Python实现）

    详解常用查找数据结构及算法（Python实现）

    一.基本概念 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录). 查找表(Search Table):由同一类型的数据元素(或记录)构成的集合 关键字(Key):数据元素中某个数据项的值,又称为键值. 主键(Primary Key):可唯一地标识某个数据元素或记录的关键字. 查找表按照操作方式可分为: 静态查找表(Static Search Table):只做查找操作的查找表.它的主要操作是: 查询某个"特定的"数据元素是否在表中

  • Python实现列表转换成字典数据结构的方法

    本文实例讲述了Python实现列表转换成字典数据结构的方法.分享给大家供大家参考,具体如下: ''' [ {'symbol': 101, 'sort': 1, 'name': 'aaaa'}, {'symbol': 102, 'sort': 2, 'name': 'bbbb'}, {'symbol': 103, 'sort': 3, 'name': 'cccc'}, {'symbol': 104, 'sort': 4, 'name': 'dddd'}, {'symbol': 105, 'sort

  • Python 实现数据结构-循环队列的操作方法

    今天我们来到了循环队列这一节,之前的文章中,我介绍过了用python自带的列表来实现队列,这是最简单的实现方法. 但是,我们都知道,在列表中删除第一个元素和删除最后一个元素花费的时间代价是不一样的,删除列表的第一个元素,那么在它之后的所有元素都要进行移动.所以当列表特别长的时候,这个代价就比较明显了.我们本文介绍的循环队列可以避免这个问题,同样我们上篇文章提到的用链表实现的方法也可以避免. 下面,我们来介绍循环队列. 循坏队列 循环队列,就是将普通的队列首尾连接起来, 形成一个环状,并分别设置首

  • Python数据结构之翻转链表

    翻转一个链表 样例:给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null 一种比较简单的方法是用"摘除法".就是先新建一个空节点,然后遍历整个链表,依次令遍历到的节点指向新建链表的头节点. 那样例来说,步骤是这样的: 1. 新建空节点:None 2. 1->None 3. 2->1->None 4. 3->2->1->None 代码就非常简单了: """

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • Python基于list的append和pop方法实现堆栈与队列功能示例

    Python基于list的append和pop方法实现堆栈与队列功能示例

    本文实例讲述了Python基于list的append和pop方法实现堆栈与队列功能.分享给大家供大家参考,具体如下: #coding=utf8 ''''' 堆栈: 堆栈是一个后进先出(LIFO)的数据结构. 在栈上"push"元素是个常用术语,意思是把一个对象添加到堆栈中. 删除一个元素,可以把它"pop"出堆栈. 队列: 队列是一种先进先出(FIFO)的数据类型. 新的元素通过"入队"的方式添加进队列的末尾, "出对"就是从

  • python数据结构链表之单向链表(实例讲解)

    python数据结构链表之单向链表(实例讲解)

    单向链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域.这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值. 表元素域elem用来存放具体的数据. 链接域next用来存放下一个节点的位置(python中的标识) 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点. 节点实现 class Node(object): """单链表的结点""" def __i

  • Python实现的数据结构与算法之快速排序详解

    Python实现的数据结构与算法之快速排序详解

    本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中

  • Python 实现数据结构-堆栈和队列的操作方法

    队.栈和链表一样,在数据结构中非常基础一种数据结构,同样他们也有各种各样.五花八门的变形和实现方式.但不管他们形式上怎么变,队和栈都有其不变的最基本的特征,我们今天就从最基本,最简单的实现来看看队列和堆栈. 不管什么形式的队列,它总有的一个共同的特点就是"先进先出".怎么理解呢?就像是超市排队结账,先排队的人排在队的前面,先结账出队.这是队列的特征. 而堆栈则和队列相反,它是"先进后出",怎么理解呢?基本所有的编辑器都有一个撤销功能,就是按Ctrl+Z.当你写了一段

  • Python基于列表模拟堆栈和队列功能示例

    本文实例讲述了Python基于列表模拟堆栈和队列功能.分享给大家供大家参考,具体如下: 之前的文章http://www.jb51.net/article/59897.htm介绍了堆栈与队列的Python实现方法,这里使用列表来模拟一下堆栈与队列的简单操作. 一.队列特点:先进先出.后进后出 用列表insert.pop模拟进队出队: >>> l = [] >>> l.insert(0,'p1') >>> l.insert(0,'p2') >>

  • Python实现基本数据结构中队列的操作方法示例

    本文实例讲述了Python实现基本数据结构中队列的操作方法.分享给大家供大家参考,具体如下: #! /usr/bin/env python #coding=utf-8 class Queue(object): def __init__(self,size): self.size=size self.head=-1 #初始化队头 self.tail=-1 #初始化队尾 self.queue=[] def EnQueue(self,x): if self.IsFull():#如果试图往满队列插入元素

  • Python常见数据结构之栈与队列用法示例

    本文实例讲述了Python常见数据结构之栈与队列用法.分享给大家供大家参考,具体如下: Python常见数据结构之-栈 首先,栈是一种数据结构.具有后进先出特性. #栈的实现 class Stack(): def __init__(self,size): self.stack=[] self.size=size self.top=-1 def push(self,content): if self.Full(): print "Stack is Full" else: self.sta

  • Python数据结构之优先级队列queue用法详解

    Python数据结构之优先级队列queue用法详解

    一.基本用法 Queue类实现了一个基本的先进先出容器.使用put()将元素增加到这个序列的一端,使用get()从另一端删除.具体代码如下所示: import queue q = queue.Queue() for i in range(1, 10): q.put(i) while not q.empty(): print(q.get(), end=" ") 运行之后,效果如下: 这里我们依次添加1到10到队列中,因为先进先出,所以出来的顺序也与添加的顺序相同. 二.LIFO队列 既然

  • LinkedList学习示例模拟堆栈与队列数据结构

    堆栈:先进后出First in Last Out FILO 如同一个杯子队列:先进先出 First in First out FIFO  如同一个水管 复制代码 代码如下: class Duilie{    private LinkedList link;    Duilie(){        link = new LinkedList();    }    public void myAdd(Object obj){        link.addFirst(obj);    }    pu

  • 详解Python中的四种队列

    队列是一种只允许在一端进行插入操作,而在另一端进行删除操作的线性表. 在Python文档中搜索队列(queue)会发现,Python标准库中包含了四种队列,分别是queue.Queue / asyncio.Queue / multiprocessing.Queue / collections.deque. collections.deque deque是双端队列(double-ended queue)的缩写,由于两端都能编辑,deque既可以用来实现栈(stack)也可以用来实现队列(queue

随机推荐