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

作者:buaa_shang 时间:2022-03-14 23:18:28 

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

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

不同点:栈(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()
标签:栈,队列,Python
0
投稿

猜你喜欢

  • 详解Vue中的watch和computed

    2024-05-05 09:10:52
  • Python抽象类的新写法

    2022-12-04 13:39:38
  • 了解WEB页面工具语言XML(一)产生背景

    2008-09-05 17:18:00
  • python抓取京东小米8手机配置信息

    2021-10-12 15:55:32
  • mysql 设置自动创建时间及修改时间的方法示例

    2024-01-24 08:12:55
  • pytorch中Tensor.to(device)和model.to(device)的区别及说明

    2021-10-20 05:26:06
  • JS版图片放大镜效果

    2024-04-30 08:50:57
  • asp如何在读取Excel文件时创建列表的下拉菜单?

    2010-06-18 19:59:00
  • 微软建议的ASP性能优化28条守则(8)

    2005-05-30 16:04:00
  • MySQL密码忘了怎么办?MySQL重置root密码方法

    2024-01-23 02:18:30
  • 如何将 awk 脚本移植到 Python

    2022-02-28 05:40:52
  • python交易记录整合交易类详解

    2022-09-15 20:18:37
  • python函数指定默认值的实例讲解

    2021-07-20 14:05:01
  • 详解golang defer 闭包 匿名函数

    2024-02-11 09:19:20
  • Python画图常用命令大全(详解)

    2023-04-17 15:20:16
  • 如何基于Python按行合并两个txt

    2021-03-19 08:24:41
  • pycharm下pyqt4安装及环境配置的教程

    2021-11-01 16:03:57
  • 从零开始学YII2框架(五)快速生成代码工具 Gii 的使用

    2024-05-11 09:54:56
  • Google Chrome CSS选择器速度测试比较

    2008-10-06 13:24:00
  • Pytorch的安装过程之pip、conda、Docker容器安装

    2021-05-20 00:07:51
  • asp之家 网络编程 m.aspxhome.com