Python实现队列,双端队列

Python实现队列,双端队列 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"))