定义键盘快捷键 正则表达式 variables javafx bitmap onclick jqgrid bootstrap后台管理 etc文件夹 mysql错误代码1064 matlab停止运行 jq入口函数 html下拉框默认选中 excel加减混合求和 python环境搭建 python中for循环的用法 python重复执行 java中的string java开发环境安装 java中float javac java配置文件 javalist转数组 python网站开发实例 atq 梦幻西游手游助手 数据库系统概论第五版 神龙kms 离散数学pdf c语言表白代码 3dmax插件神器 美国地址生成器 迅雷去广告版 识别音乐的软件 谷歌地球用不了 给视频加字幕的软件 幽灵行动多少钱 js动态添加元素 网络驱动 服务器之家
当前位置: 首页 > 学习教程  > 编程语言

<学习笔记>栈、队列和双端队列(2020.7.23)

2020/7/24 9:12:51 文章标签:

1.栈

  • 栈得特性:先进后出得数据结构
  • 栈顶、栈尾
  • 应用:每个web浏览器都有一个返回按钮,当你浏览网页时,这些网页被放置在一个栈种(实际是网页得网址)。你现在看得网页是在顶部,你第一个查看得网页在底部,如果按下返回按钮,及那个相反的顺序浏览刚才得网页。
  • Stack()创建一个空的新栈,不需要参数,返回一个空栈
  • push(item)将一个新项添加到顶部,需要item作为参数,不返回任何内容
  • pop()从栈中删除顶部项,不需要参数,返回item,栈被修改
  • peek()从栈返回顶部,但不会删除它,不需要参数,不返回任何内容
  • isEmpty()测试栈是否为空,不需要参数,并返回布尔值
  • size()返回栈中的item数量,不需要参数,并返回一个整数
#创建一个栈 含有push pop peek isEmpty size方法
class Stack():
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return len(self.items)-1

    def isEmpty(self):
        return self.items == []

    def size(self):
        return len(self.items)


stack = Stack()

stack.push(1)
stack.push(2)
stack.push(3)

print('栈顶下标为:', stack.peek())
print("栈是否为空:", stack.isEmpty())
print("元素个数:", stack.size())
print(stack.pop())
print(stack.pop())
print(stack.pop())

  • list.pop()方法:用于移除列表中的一个元素(默认是最后一个元素),并返回该元素。

结果展示:
在这里插入图片描述
2.队列

  • 队列得特性:先进先出

  • 队首,队尾

  • 应用:我们的计算机实验室有30太计算器与一台打印机联网,当想打印时,他们的打印任务与其他正在等待打印的任务一致,第一个进入的任务是先完成的,如果你是最后一个,那你必须等待前面所有的打印任务先完成。

  • Queue():创建一个新队列,不要参数,返回空队列

  • enqueue(item):将一个新项添加到队尾,要item参数,不返回

  • dequeue():从队首移除项,不需要参数,返回item,队列被修改

  • isEmpty():查看队列是否为空,不需要参数,返回布尔值

  • size():返回队列中得项个数,不需要参数,返回整数

案例:6个人围成一个圈,排列顺序孩子们自己指定,第一个孩子手里有一个山芋,计时器计时1s后传给下一个孩子,以此类推,计时器每计时七秒淘汰一人,直至最后一人取得最终胜利。使用队列实现该游戏策率。
思路如下:
在这里插入图片描述
由上图可知,7s共可以传递6次,淘汰一人。
在这里插入图片描述

  • 准则手里由山芋得人位于队首,这样方便取出。

根据上述准则我们可以这样想,第1s时A手里有山芋,第2s时候B手里有山芋,那么我们可以让A出队列,然后再进队列,这样就可以使拿到山芋得B位于队首。

'''
6个人围成一个圈,排列顺序孩子们自己指定,第一个孩子手里有一个山芋,计时器计时1s后
传给下一个孩子,以此类推,计时器每计时七秒淘汰一人,直至最后一人取得最终胜利。使用
队列实现该游戏策率。
'''

class Queue():
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def isEmpty(self):
        return self.items == []

    def size(self):
        return len(self.items)
queue = Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print("队列是否为空:", queue.isEmpty())
print("元素个数:", queue.size())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

kids = ['A', 'B', 'C', 'D', 'E', 'F']

for kid in kids:
    queue.enqueue(kid) # A位于队首,F位于队尾
while queue.size() > 1:
    for i in range(6): # 每循环一次,山芋产第一次,手里有山芋得人在队首
        kid = queue.dequeue()
        queue.enqueue(kid)

    queue.dequeue() # 第七秒位于队首得项移除
print('获胜的选手是:', queue.dequeue())

结果展示:
在这里插入图片描述

3.双端队列
在这里插入图片描述

  • 双端队列得特性:有两个头部和尾部,可以在双端进行数据得插入和删除,提供了单数据结构中队列得特性。

  • Deque():创建一个空的新deque,不需要参数,返回空得deque

  • addFront(item):将一个新项添加到deque得首部,需要item参数,不返回内容

  • addRear():将一个新项添加到deque得尾部,需要item参数,不返回内容

  • removeFront():从deque中删除首项,不需要参数,返回item,deque被篡改

  • removeRear():从deque中删除尾部,不需要参数,返回item,deque被篡改

  • isEmpty():测试deque是否为空,不需要参数,返回布尔值

  • size():返回deque中的项数,不需要参数,返回整数

***案例:*回文检查,回文是一个字符串,读取首尾相同的字符,例如,radar toot madam。
思路:先变成列表,然后比较首尾两端,通过dequeue()

class Deque():
    def __init__(self):
        self.items = []

    def addFront(self, item): # 队首进,队首出,先进先出
        self.items.insert(0, item) # 从队首进1,那么2就要在1得左面

    def addRear(self, item): # 队尾进,队尾出,先进先出
        self.items.append(item) # 从队尾进1,那么2就要在1得右面

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def isEmpty(self):
        return self.items == []

    def size(self):
        return len(self.items)

q = Deque()
q.addFront(1)
q.addFront(2)
q.addFront(3)

# 先进先出
print(q.removeFront())
print(q.removeFront())
print(q.removeFront())

q.addFront(1)
q.addFront(2)
q.addFront(3)

# 先进后出
print(q.removeRear())
print(q.removeRear())
print(q.removeRear())

'''
案例:回文检查,回文是一个字符串,读取首尾相同的字符,
例如,radar toot madam。
'''

def isHuiWen(s):
    ex = True
    q = Deque()
    for ch in s:
        q.addFront(ch)
    while q.size() > 1: # 如果为奇数个剩1个输出,如果偶数个剩下0个输出,因此大于1循环
        if q.removeFront() != q.removeRear():
            ex = False
            break
    return ex
print(isHuiWen('heireh'))

结果展示:

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_50026.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?