1. 列表的定义

先进先出（FIFO）

2. 用法

类代码如下：

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def pop(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

    def is_empty(self):
        return self.items == []

3. 算法运用

① 约瑟夫环
剑指offer62

    def __init__(self):
        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)

    def is_empty(self):
        return self.items == []

# num为传递的次数，每隔一个人就是传递1次
class Solution:
    def lastRemaining(self, n: int, num = 2) -> int:
        lst = Queue()
        for i in range(n):
            lst.enqueue(i)
        while lst.size() >1:
            for i in range(num):
                lst.enqueue(lst.dequeue())
            lst.dequeue()
        return lst.dequeue()

先按头消去，每隔一个消去；再从第二个每隔一个消去
【1,2,3,4,5,6】→【2,4,6】→【2,6】→【6】
这种方法代码如下：

class Queue:
    def __init__(self):
        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)

    def is_empty(self):
        return self.items == []

# num为传递的次数，每隔一个人就是传递1次
class Solution:
    def lastRemaining(self, n: int, num = 1) -> int:
        lst = Queue()
        flag = 0
        for i in range(1, n+1):
            lst.enqueue(i)
        mark = lst.size() % 2
        while lst.size() // 2 > 0:
            if flag == 0:
                lst.dequeue()
                for i in range(lst.size()//2):
                    for j in range(num):
                        lst.enqueue(lst.dequeue())
                    lst.dequeue()

                flag = 1
                if mark == 0:
                    lst.enqueue(lst.dequeue())
            else:
                for i in range(lst.size()//2):
                    for j in range(num):
                        lst.enqueue(lst.dequeue())
                    lst.dequeue()
                    
                flag = 0
                if mark == 0:
                    lst.enqueue(lst.dequeue())
                    
        return lst.dequeue()

LeetCode 390. 消除游戏

#采用队列和栈的思想，不过虽然超时，但是是正确的。
class Queue:
    def __init__(self):
        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)

    def is_empty(self):
        return self.items == []

# num为传递的次数，每隔一个人就是传递1次
class Solution:
    def lastRemaining(self, n: int, num = 1) -> int:
        lst = Queue()
        flag = 0
        for i in range(1, n+1):
            lst.enqueue(i)
        
        while lst.size() // 2 > 0:
            mark = lst.size() % 2
            if flag == 0:
                lst.dequeue()
                for i in range(lst.size()//2):
                    for j in range(num):
                        lst.enqueue(lst.dequeue())
                    lst.dequeue()

                flag = 1
                if mark == 0:
                    lst.enqueue(lst.dequeue())

            else:
                lst.items.pop(0)
                for i in range(lst.size()//2):
                    for j in range(num):
                        lst.items.append(lst.items.pop(0))
                    lst.items.pop(0)
                flag = 0
                if mark == 0:
                    lst.items.append(lst.items.pop(0))
                
        return lst.dequeue()

4 双向队列

两边可以加东西与减东西

image.png

python有双向队列的库，可以直接导入：

from collections import deque

image.png

题目：

1. LeetCode 239：双向队列

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        from collections import deque
        queue = deque()
        for i in range(len(nums)):
            if queue and queue[0] < i-k+1:
                queue.popleft()
            while queue and nums[queue[-1]] < nums[i]:
                queue.pop()
            queue.append(i)
            
            if i >= k-1:
                res.append(nums[queue[0]])
        
        return res

2. Leetcode 9. Palindrome Number

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        if x == 0:
            return True
        
        res = deque()
        for i in str(x):
            res.append(i)
            
        mark = True
        
        while len(res) > 1 and mark is True:
            if res.pop() != res.popleft():
                mark = False
        
        return mark