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程序设计有所帮助。

赞 (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实现

    先来回顾一下栈和队列的基本概念: 相同点:从"数据结构"的角度看,它们都是线性结构,即数据元素之间的关系相同. 不同点:栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表. 队列(Queue)是限定只能在表的一端进行插入和在另一端进行删除操作的线性表.它们是完全不同的数据类型.除了它们各自的基本操作集不同外,主要区别是对插入和删除操作的"限定". 栈必须按"后进先出"的规则进行操作:比如说,小学老师批改学生的作业,如果不打乱作业本的顺

  • Python中栈、队列与优先级队列的实现方法

    前言 栈.队列和优先级队列都是非常基础的数据结构.Python作为一种"编码高效"的语言,对这些基础的数据结构都有比较好的实现.在业务需求开发过程中,不应该重复造轮子,今天就来看看些数据结构都有哪些实现. 0x00 栈(Stack) 栈是一种LIFO(后进先出)的数据结构,有入栈(push).出栈(pop)两种操作,且只能操作栈顶元素. 在Python中有多种可以实现栈的数据结构. 1.list list是Python内置的列表数据结构,它支持栈的特性,有入栈和出栈操作.只不过用lis

  • Python数据结构之栈、队列的实现代码分享

    Python数据结构之栈、队列的实现代码分享

    1. 栈 栈(stack)又名堆栈,它是一种运算受限的线性表.其限制是仅允许在表的一端进行插入和删除运算.这一端被称为栈顶,相对地,把另一端称为栈底.向一个栈插入新元素又称作进栈.入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素:从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素. 栈(Stack)是限制插入和删除操作只能在一个位置进行的表,该位置是表的末端,称为栈的顶(top).栈的基本操作有PUSH(入栈)和POP(出栈).栈又被称为LIF

  • Python实现的栈、队列、文件目录遍历操作示例

    本文实例讲述了Python实现的栈.队列.文件目录遍历操作.分享给大家供大家参考,具体如下: 一. 栈与队列 1. 栈 stack 特点:先进先出[可以抽象成竹筒中的豆子,先进去的后出来] 后来者居上 mystack = [] #压栈[向栈中存数据] mystack.append(1) print(mystack) mystack.append(2) print(mystack) mystack.append(3) print(mystack) #出栈[从栈中取数据] mystack.pop()

  • Python编程实现双链表，栈，队列及二叉树的方法示例

    本文实例讲述了Python编程实现双链表,栈,队列及二叉树的方法.分享给大家供大家参考,具体如下: 1.双链表 class Node(object): def __init__(self, value=None): self._prev = None self.data = value self._next = None def __str__(self): return "Node(%s)"%self.data class DoubleLinkedList(object): def

  • Python数据结构之栈、队列及二叉树定义与用法浅析

    Python数据结构之栈、队列及二叉树定义与用法浅析

    本文实例讲述了Python数据结构之栈.队列及二叉树定义与用法.分享给大家供大家参考,具体如下: 目前只实现了三种,栈.队列和二叉树,哪天得空继续补吧~ 1. 栈 #栈 class Stack: def __init__(self,size = 16): self.stack = [] self.size = size self.top = -1 def setSize(self, size): self.size = size def isEmpty(self): if self.top ==

  • 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基于list的append和pop方法实现堆栈与队列功能示例

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

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

  • Python 实现数据结构中的的栈队列

    栈(stack)又名堆栈,它是一种运算受限的线性表.其限制是仅允许在表的一端进行插入和删除运算.这一端被称为栈顶,相对地,把另一端称为栈底.向一个栈插入新元素又称作进栈.入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素:从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素. 栈可以用顺序表实现,也可以用链表实现,这里为了方便就用顺序表实现. # -*- coding: utf-8 -*- class Stack(object): ""&

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

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

  • python 利用栈和队列模拟递归的过程

    一.递归 递归调用:一个函数,调用的自身,称为递归调用 递归函数:一个可以调用自身的函数称为递归函数 凡是循环能干的事,递归都能干 方法: 1.写出临界条件 2.找这一次和上一次的关系 3.假设当前函数已经能用,调用自身计算上一次的结果再求出本次的结果 下面我们通过两段代码简单看一下递归和非递归的区别: 输入一个大于等于1的数,求1到n的和! # 普通函数方法 def hanshu(n): sum = 0 # 循环遍历每一个数字,将他们加到一个事先定义好的变量上,直到加完 for x in ra

随机推荐