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

yipeiwu_com6年前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 实现数据结构-堆栈和队列的操作方法,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对【听图阁-专注于Python设计】网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

相关文章

numpy下的flatten()函数用法详解

flatten是numpy.ndarray.flatten的一个函数,其官方文档是这样描述的: ndarray.flatten(order='C') Return a copy of...

Django读取Mysql数据并显示在前端的实例

Django读取Mysql数据并显示在前端的实例

前言: 由于使用Django框架来做网站,需要动态显示数据库内的信息,所以读取数据库必须要做,写此博文来记录。 接下来分两步来做这个事,添加网页,读取数据库; 一、添加网页 首先按添加网...

Python3.5内置模块之shelve模块、xml模块、configparser模块、hashlib、hmac模块用法分析

Python3.5内置模块之shelve模块、xml模块、configparser模块、hashlib、hmac模块用法分析

本文实例讲述了Python3.5内置模块之shelve模块、xml模块、configparser模块、hashlib、hmac模块用法。分享给大家供大家参考,具体如下: 1、shelve...

Python脚本实现集群检测和管理功能

Python脚本实现集群检测和管理功能

场景是这样的:一个生产机房,会有很多的测试机器和生产机器(也就是30台左右吧),由于管理较为混乱导致了哪台机器有人用、哪台机器没人用都不清楚,从而产生了一个想法--利用一台机器来管理所有...

python分析作业提交情况

python分析作业提交情况

这次做一个比较贴近我实际的东西:python分析作业提交情况。 要求:     将服务器中交作业的学生(根据文件的名字进行提取)和统计成绩的表格中...