Python实现栈和队列的简单操作方法示例

yipeiwu_com5年前Python基础

本文实例讲述了Python实现栈和队列的简单操作方法。分享给大家供大家参考,具体如下:

先简单的了解一下数据结构里面的栈和堆:

栈和队列是两种基本的数据结构,同为容器类型。两者根本的区别在于:

stack:后进先出

queue:先进先出

stack和queue是不能通过查询具体某一个位置的元素而进行操作的。但是他们的排列是按顺序的

对于stack我们可以使用python内置的list实现,因为list是属于线性数组,在末尾插入和删除一个元素所使用的时间都是O(1),这非常符合stack的要求。当然,我们也可以使用链表来实现。

stack的实现代码(使用python内置的list),实现起来是非常的简单,就是list的一些常用操作

class Stack(object):
  def __init__(self):
    self.stack = []
  def push(self, value):  # 进栈
    self.stack.append(value)
  def pop(self): #出栈
    if self.stack:
      self.stack.pop()
    else:
      raise LookupError('stack is empty!')
  def is_empty(self): # 如果栈为空
    return bool(self.stack)
  def top(self): 
    #取出目前stack中最新的元素
    return self.stack[-1]

我们定义如下的链表来实现队列数据结构:

定义一个头结点,左边指向队列的开头,右边指向队列的末尾,这样就可以保证我们插入一个元素和取出一个元素都是O(1)的操作,使用这种链表实现stack也是非常的方便。实现代码如下:

class Head(object):
  def __init__(self):
    self.left = None
    self.right = None
class Node(object):
  def __init__(self, value):
    self.value = value
    self.next = None
class Queue(object):
  def __init__(self):
    #初始化节点
    self.head = Head()
  def enqueue(self, value):
    #插入一个元素
    newnode = Node(value)
    p = self.head
    if p.right:
      #如果head节点的右边不为None
      #说明队列中已经有元素了
      #就执行下列的操作
      temp = p.right
      p.right = newnode
      temp.next = newnode
    else:
      #这说明队列为空,插入第一个元素
      p.right = newnode
      p.left = newnode
  def dequeue(self):
    #取出一个元素
    p = self.head
    if p.left and (p.left == p.right):
      #说明队列中已经有元素
      #但是这是最后一个元素
      temp = p.left
      p.left = p.right = None
      return temp.value
    elif p.left and (p.left != p.right):
      #说明队列中有元素,而且不止一个
      temp = p.left
      p.left = temp.next
      return temp.value
    else:
      #说明队列为空
      #抛出查询错误
      raise LookupError('queue is empty!')
  def is_empty(self):
    if self.head.left:
      return False
    else:
      return True
  def top(self):
    #查询目前队列中最早入队的元素
    if self.head.left:
      return self.head.left.value
    else:
      raise LookupError('queue is empty!')

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程

希望本文所述对大家Python程序设计有所帮助。

相关文章

详解pandas数据合并与重塑(pd.concat篇)

详解pandas数据合并与重塑(pd.concat篇)

1 concat concat函数是在pandas底下的方法,可以将数据根据不同的轴作简单的融合 pd.concat(objs, axis=0, join='outer', join...

Django restframework 框架认证、权限、限流用法示例

本文实例讲述了Django restframework 框架认证、权限、限流用法。分享给大家供大家参考,具体如下: 概述 Django Rest Framework 是一个强大且灵活的工...

修复 Django migration 时遇到的问题解决

今天想给自己的 Blog 加点功能,顺便补上测试,然而第一步在创建测试数据库就过不了,我就尝试解决这个问题。 在跑 ./manage.py test 时,先会创建一个测试用的数据库,这时...

Python调用C语言开发的共享库方法实例

在helloworld工程中,编写了一个简单的两个数值相加的程序,编译成为共享库后,如何使用python对其进行调用呢? 使用ll命令列出当前目录下的共享库,其中共享库名为libhell...

Python创建对称矩阵的方法示例【基于numpy模块】

Python创建对称矩阵的方法示例【基于numpy模块】

本文实例讲述了Python创建对称矩阵的方法。分享给大家供大家参考,具体如下: 对称(实对称)矩阵也即: step 1:创建一个方阵 >>> import nump...