栈和队列数据结构的基本概念及其相关的Python实现

先来回顾一下栈和队列的基本概念：

相同点：从"数据结构"的角度看，它们都是线性结构，即数据元素之间的关系相同。

不同点：栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。 队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的"限定"。

栈必须按"后进先出"的规则进行操作：比如说，小学老师批改学生的作业，如果不打乱作业本的顺序的话，那么老师批改的第一份作业一定是最后那名同学交的那份作业，如果把所有作业本看作是一个栈中的元素，那么最后一个同学交的作业本就是栈顶元素，而第一个同学交的，也就是最低端的作业本，就是栈底元素，这就是对栈的读取规则。

而队列必须按"先进先出"的规则进行操作：打个比方，一些人去银行办理业务，一定是先去排队的最先得到服务，当然他也是第一个走出银行的（假设这些人都在一个窗口排队）。如果把所有这些等候服务的人看作是队的元素，第一个人就是对头元素，相应的，最后一个人就是队尾元素。这是队的读取规则。

用Python实现栈，这是Python核心编程里的一个例子:

#!/usr/bin/env python 

#定义一个列表来模拟栈
stack = [] 

#进栈,调用列表的append()函数加到列表的末尾,strip()没有参数是去掉首尾的空格
def pushit():
  stack.append(raw_input('Enter new string: ').strip()) 

#出栈,用到了pop()函数
def popit():
  if len(stack) == 0:
    print 'Cannot pop from an empty stack!'
  else:
    print 'Removed [', stack.pop(), ']' 

#编历栈
def viewstack():
  print stack 

#CMDs是字典的使用
CMDs = {'u': pushit, 'o': popit, 'v': viewstack} 

#pr为提示字符
def showmenu():
  pr = """
  p(U)sh
  p(O)p
  (V)iew
  (Q)uit
    Enter choice: """ 

  while True:
    while True:
      try:
        #先用strip()去掉空格,再把第一个字符转换成小写的
        choice = raw_input(pr).strip()[0].lower()
      except (EOFError, KeyboardInterrupt, IndexError):
        choice = 'q' 

      print '\nYou picked: [%s]' % choice
      if choice not in 'uovq':
        print 'Invalid option, try again'
      else:
        break 

#CMDs[]根据输入的choice从字典中对应相应的value,比如说输入u,从字典中得到value为pushit,执行pushit()进栈操作
    if choice == 'q':
      break
    CMDs[choice]() 

#判断是否是从本文件进入,而不是被调用
if __name__ == '__main__':
  showmenu()

用Python实现队列:

#!/usr/bin/env python 

queue = [] 

def enQ():
  queue.append(raw_input('Enter new string: ').strip()) 

#调用list的列表的pop()函数.pop(0)为列表的第一个元素
def deQ():
  if len(queue) == 0:
    print 'Cannot pop from an empty queue!'
  else:
    print 'Removed [', queue.pop(0) ,']' 

def viewQ():
  print queue 

CMDs = {'e': enQ, 'd': deQ, 'v': viewQ} 

def showmenu():
  pr = """
  (E)nqueue
  (D)equeue
  (V)iew
  (Q)uit
    Enter choice: """ 

  while True:
    while True:
      try:
        choice = raw_input(pr).strip()[0].lower()
      except (EOFError, KeyboardInterrupt, IndexError):
        choice = 'q' 

      print '\nYou picked: [%s]' % choice
      if choice not in 'devq':
        print 'Invalid option, try again'
      else:
        break
    if choice == 'q':
      break
    CMDs[choice]() 

if __name__ == '__main__':
  showmenu()
赞 (0)

相关推荐

  • python数据结构之二叉树的建立实例

    先建立二叉树节点,有一个data数据域,left,right 两个指针域 复制代码 代码如下: # -*- coding: utf - 8 - *- class TreeNode(object): def __init__(self, left=0, right=0, data=0):        self.left = left        self.right = right        self.data = data 复制代码 代码如下: class BTree(object):

  • python二叉树遍历的实现方法

    复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class TreeNode(object):    def __init__(self,data=0,left=0,right=0):        self.data = data        self.left = left        self.right = right class BTree(object):    def __init__(self,root=0):     

  • Python实现简单多线程任务队列

    最近我在用梯度下降算法绘制神经网络的数据时,遇到了一些算法性能的问题.梯度下降算法的代码如下(伪代码): def gradient_descent(): # the gradient descent code plotly.write(X, Y) 一般来说,当网络请求 plot.ly 绘图时会阻塞等待返回,于是也会影响到其他的梯度下降函数的执行速度. 一种解决办法是每调用一次 plotly.write 函数就开启一个新的线程,但是这种方法感觉不是很好. 我不想用一个像 cerely(一种分布式任

  • 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实现栈的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python #定义一个列表来模拟栈 stack = [] #进栈,调用列表的append()函数加到列表的末尾,strip()没有参数是去掉首尾的空格 def pushit(): stack.append(raw_input('Enter new string: ').strip()) #出栈,用到了pop()函数 def popit(): if len(stack) == 0: p

  • Python二叉搜索树与双向链表转换实现方法

    本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

  • 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数据结构之二叉树的遍历实例

    遍历方案   从二叉树的递归定义可知,一棵非空的二叉树由根结点及左.右子树这三个基本部分组成.因此,在任一给定结点上,可以按某种次序执行三个操作:   1).访问结点本身(N)   2).遍历该结点的左子树(L)   3).遍历该结点的右子树(R) 有次序:   NLR.LNR.LRN 遍历的命名 根据访问结点操作发生位置命名:NLR:前序遍历(PreorderTraversal亦称(先序遍历))  --访问结点的操作发生在遍历其左右子树之前.LNR:中序遍历(InorderTraversal)

  • Python3中多线程编程的队列运作示例

    Python3,开一个线程,间隔1秒把一个递增的数字写入队列,再开一个线程,从队列中取出数字并打印到终端 #! /usr/bin/env python3 import time import threading import queue # 一个线程,间隔一定的时间,把一个递增的数字写入队列 # 生产者 class Producer(threading.Thread): def __init__(self, work_queue): super().__init__() # 必须调用 self.

  • Python算法之栈（stack）的实现

    本文以实例形式展示了Python算法中栈(stack)的实现,对于学习数据结构域算法有一定的参考借鉴价值.具体内容如下: 1.栈stack通常的操作: Stack() 建立一个空的栈对象 push() 把一个元素添加到栈的最顶层 pop() 删除栈最顶层的元素,并返回这个元素 peek()  返回最顶层的元素,并不删除它 isEmpty()  判断栈是否为空 size()  返回栈中元素的个数 2.简单案例以及操作结果: Stack Operation Stack Contents Return

  • python双向链表实现实例代码

    python双向链表实现实例代码

    示意图: python双向链表实现代码: 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class Node(object):    def __init__(self,val,p=0):        self.data = val        self.next = p        self.prev = p class LinkList(object):    def __init__(self):        self.he

随机推荐