1.队列
队列是元素的有序集合，在尾部添加元素，头部移除元素（类似于排队）
2.队列特性
先进先出（FIFO,first?in?first out）
3.队列抽象数据类型
? ? ? ? Queue():创建一个空队列，不需要参数，返回一个空队列
? ? ? ? enqueue(item):在队列尾部添加一个元素，需要一个元素作为参数，不返回任何值
? ? ? ? dequeue():从队列头部移除一个元素，不需要参数，返回一个元素，且修改队列的内容
? ? ? ? isEmpty():检查队列是否为空，不需要参数，返回一个布尔值
? ? ? ? size():返回队列中元素的数目，不需要参数，且会返回一个整数
?4.用python列表实现队列
#将列表的0索引位置作为队列的尾部
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self,item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
q = Queue()
print(q.isEmpty())
q.enqueue([1,2,3,"jq",True])
print(q.isEmpty())
print(q.dequeue())
q.enqueue(999)
q.enqueue(888)
print(q.dequeue())
print(q.size())?5.双端队列Deque
双端队列有前后两端，其两端都可以添加或删除元素，不受限制，具体的使用原则取决于使用者
6.双端队列抽象数据类型
? ? ? ? Deque:创建一个空的双端队列，不需要参数，返回一个空的双端队列
? ? ? ? addFront(item):在双端队列前端添加一个元素，接收一个元素作为参数，无返回值
? ? ? ? addRear(item):在双端队列后端添加一个元素，接收一个元素作为参数，无返回值
? ? ? ? removeFront():移除双端队列前端一个元素，不需要参数，且会返回一个元素，并修改双端队列内容
? ? ? ? removeRear():移除双端队列后端一个元素，不需要参数，且会返回一个元素，并修改双端队列内容
? ? ? ? isEmpty():判断双端队列是否为空，不需要参数，且会返回一个布尔值
? ? ? ? size():返回双端队列元素个数，不需要参数，且会返回一个整数
?7.用python列表实现双端队列
#把列表索引0位置作为双端队列后端
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self,item):
self.items.append(item)
def addRear(self,item):
self.items.insert(0,item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
de = Deque()
print(de.isEmpty())
de.addFront(1)
de.addRear(2)
print(de.size())
de.removeFront()
de.removeRear()
print(de.size())
8.用双端队列实现回文检测
from Algorithm import Deque
def palchecker(aString):
"""
用双端队列实现回文检测
:param aString: 输入字符串
:return: 布尔值
"""
chardeque = Deque.Deque()
for ch in aString:
chardeque.addRear(ch)
stillEqual = True
while chardeque.size()>1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False
return stillEqual
print(palchecker("python"))
print(palchecker("madam"))