不为成仙,只为在这红尘中等你回来。

您现在的位置是:网站首页>>算法与数据结构

队列

2020年11月9日 20:37 | 分类:算法与数据结构 | 标签: Python

  • 队列(Queue)是一个数据集合,仅允许在列表的一端进行插入,另一端进行删除。
  • 进行插入的一端成为队尾(rear),插入动作称为进队或入队
  • 进行删除的一端成为队头(front),删除动作称为出队
  • 队列的性质:先进先出(First-in, First-out)

队列的实现方式——环形队列

  • 环形队列:当队尾指针 rear == Maxsize + 1 时,再前进一个位置就自动到 0
    • 队首指针前进 1:front = (front + 1) % Maxsize
    • 队尾指针前进 1:rear = (rear + 1) % Maxsize
    • 队空条件:rear == front
    • 队满条件:(rear + 1) % Maxsize == front
class Queue:
    def __init__(self, size=100):
        self.queue = [0 for _ in range(size)]
        self.size = size
        self.rear = 0  # 队尾指针
        self.front = 0  # 队首指针

    def push(self, element):
        if not self.is_filled():
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = element
        else:
            raise IndexError("Queue is filled.")

    def pop(self):
        if not self.is_empty():
            self.front = (self.front + 1) % self.size
            return self.queue[self.front]
        else:
            raise IndexError("Queue is empty.")

    def is_empty(self):
        """判断队空"""
        return self.rear == self.front

    def is_filled(self):
        """判断队满"""
        return (self.rear + 1) % self.size == self.front


q = Queue(5)
print(q.is_empty())
print(q.is_filled())
q.push(1)
q.push(2)
q.push(3)
q.push(4)
print(q.is_empty())
print(q.is_filled())
print(q.pop())
print(q.pop())
print(q.pop())
print(q.pop())

Python 内置模块 deque

  • 这是一个双向队列
  • 使用方法:from collections import deque
    • 创建队列:queue = deque()
      • 默认创建空队列
      • 加参数:deque([1, 2, 3], n)
        • n 代表队列长度
    • 进队:append()
    • 出队:popleft()
    • 双向队列对首进队:appendleft()
    • 双向队列队尾出队:pop()