<学习笔记>栈、队列和双端队列(2020.7.23)
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()方法:用于移除列表中的一个元素(默认是最后一个元素),并返回该元素。
结果展示:
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'))
结果展示:
本文地址:https://blog.csdn.net/qq_45363979/article/details/107545795
上一篇: iOS中的HOOK技术
下一篇: java-反射-Method类走读