欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-15 20:25:28
1.栈栈得特性:先进后出得数据结构栈顶、栈尾应用:每个web浏览器都有一个返回按钮,当你浏览网页时,这些网页被放置在一个栈种(实际是网页得网址)。你现在看得网页是在顶部,你第一个查看得网页在底部,如果按下返回按钮,及那个相反的顺序浏览刚才得网页。Stack()创建一个空的新栈,不需要参数,返回一个空栈push(item)将一个新项添加到顶部,需要item作为参数,不返回任何内容pop()从栈中删除顶部项,不需要参数,返回item,栈被修改peek()从栈返回顶部,但不会删除它,不需要参数,不...

1.栈

  • 栈得特性:先进后出得数据结构
  • 栈顶、栈尾
  • 应用:每个web浏览器都有一个返回按钮,当你浏览网页时,这些网页被放置在一个栈种(实际是网页得网址)。你现在看得网页是在顶部,你第一个查看得网页在底部,如果按下返回按钮,及那个相反的顺序浏览刚才得网页。
  • Stack()创建一个空的新栈,不需要参数,返回一个空栈
  • push(item)将一个新项添加到顶部,需要item作为参数,不返回任何内容
  • pop()从栈中删除顶部项,不需要参数,返回item,栈被修改
  • peek()从栈返回顶部元素,peek和pop的共同点是都返回栈顶元素。不同点是pop删除栈顶元素,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 self.items[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()方法:用于移除列表中的一个元素(默认是最后一个元素),并返回该元素。

结果展示:
<学习笔记>栈、队列和双端队列(2020.7.23)

2.队列

  • 队列得特性:先进先出

  • 队首,队尾

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

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

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

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

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

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

案例:6个人围成一个圈,排列顺序孩子们自己指定,第一个孩子手里有一个山芋,计时器计时1s后传给下一个孩子,以此类推,计时器每计时七秒淘汰一人,直至最后一人取得最终胜利。使用队列实现该游戏策率。
思路如下:
<学习笔记>栈、队列和双端队列(2020.7.23)
由上图可知,7s共可以传递6次,淘汰一人。
<学习笔记>栈、队列和双端队列(2020.7.23)

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

根据上述准则我们可以这样想,第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())

结果展示:
<学习笔记>栈、队列和双端队列(2020.7.23)

3.双端队列

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

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

  • 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'))

结果展示:

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

本文地址:https://blog.csdn.net/qq_45363979/article/details/107545795