队列

队列(queue)是一系列有顺序的元素的集合，新元素的加入在队列的“队尾”(rear)，元素的移除发生在队列的“队首”(front)。这种排序原则叫做先进先出(FIFO)。

队列操作

  1. queue.queue()：创建一个空队列
  2. queue.enqueue(item)：添加元素到队尾
  3. queue.dequeue()：从队首移除元素
  4. queue.isEmpty()：判断队列是否为空
  5. queue.size()：队列大小

Python实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# python list实现队列
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):
        if self.isEmpty():
            return "The queue is empty!"
        else:
            return self.items.pop()

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

双端队列

双端队列(deque, double-ended queue)也是一系列元素的有序集合，其两端分别称为队首(front)和队尾(rear)。元素可以从两端插入，也可以从两端删除，兼具栈和队列的所有功能。

双端队列操作

  1. Deque()：创建双端队列
  2. addFront(item)：在队首插入元素
  3. addRear(item)：在队尾插入元素
  4. rmFront()：从队首移除元素
  5. rmRear()：从队尾移除元素
  6. isEmpty()：判断双端队列是否为空
  7. size()：返回双端队列的大小

Python list实现双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 rmFront(self):
        if self.isEmpty():
            return "The deque is empty!"
        else:
            return self.items.pop()

    def rmRear(self):
        if self.isEmpty():
            return "The deque is empty!"
        else:
            return self.items.pop(0)

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