队列及其python实现

• 队列（Queue）
• 队列的实现
• 约瑟夫问题
• 双端队列
• • 回文词的判定

队列（Queue）是一个有次序的数据集合；数据项仅添加到尾rear端，而且仅从首front端移除，Queue具有FIFO的操作次序。

队列支持的操作：

• 入队（enqueue）：增加一个新的元素
• 出队（dequeue）：删除一个元素
• peek() ：返回队首数据项
• isEmpty() : 查看队列是否为空
• size()：返回队列中数据项的个数

数组（列表）实现：

class Queue(object):
    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 peek(self):
        return self.items[len(self.items)-1]
    # 返回队列中数据项的个数
    def size(self):
        return len(self.items)

from ADT_CLASS import Queue

q = Queue()
print(q.isEmpty())
q.enqueue(1)
q.enqueue('dog')
q.enqueue('4')
print(q.size())
print(q.peek())
print(q.dequeue())
print(q.size())

输出：
队列是否为空: True
队列长度： 3
队首数据： 1
删除队首： 1
队列长度： 2

这里我们模拟一圈人坐在一起玩逢num数过的游戏，最后留下的人是谁。
模拟游戏开始，只需要将队首的人出列，随即再加到队尾，过了num次后，将队首的人移除，不再入队。
如此反复，直到队中还剩下一人。

from ADT_CLASS import Queue

def josephProblem(namelist, num):
    q = Queue()
    for name in namelist:
        q.enqueue(name)
    while q.size() > 1:
        for i in range(num):
            q.enqueue(q.dequeue())
        q.dequeue()
    return q.dequeue()

namelist = ['a','b','c','d','e','f','g']
print(josephProblem(namelist,3))

双端队列（Deque）是一种有次序的数据集；

• 数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。（某种意义上说，双端队列集成了栈和队列的功能）；
• 双端队列不具有 LIFO 或 FIFO 特性。
  
  这里我们用collections 库里的deque来实现双端队列；

from collections import deque

d = deque()
print(d)

d = deque(['a','b','c'])
print(d)

d.append(1)#后端添加
d.appendleft(0)#前端添加
print(d)

d.extend((2,3))
print(d)

d.extendleft((-1,-2))
print(d)
#在索引3之前插入数字100
d.insert(3,100)
print(d)

a = d.pop()#后端弹出
print(a)
print(d)

a = d.popleft()#前端弹出
print(a)
print(d)
print(len(d))
#清除队列所有元素
d.clear()
print(d)

输出：
deque([])
deque(['a', 'b', 'c'])
deque([0, 'a', 'b', 'c', 1])
deque([0, 'a', 'b', 'c', 1, 2, 3])
deque([-2, -1, 0, 'a', 'b', 'c', 1, 2, 3])
deque([-2, -1, 0, 100, 'a', 'b', 'c', 1, 2, 3])
3
deque([-2, -1, 0, 100, 'a', 'b', 'c', 1, 2])
-2
deque([-1, 0, 100, 'a', 'b', 'c', 1, 2])
8
deque([])

LeetCode 125. 验证回文串

from collections import deque
def isPalindrome(s):
    d = deque()
    for ch in s:
        d.append(ch)
    # for ch in s:
    #     if ch.isalnum():
    #         d.appendleft(ch.lower())
    res = True
    while len(d) > 1 and res:
        first = d.pop()
        last = d.popleft()
        if first != last:
            res = False
    return res

print(isPalindrome('abccba'))
print(isPalindrome('raceacar'))

输出：
True
False