Yinyaohui

Python（双端）队列

2019/10/15 Algorithms

记录学习笔记和心得，参考书籍《Python数据结构与算法分析》。

队列

定义

队列是一种有序集合，添加和删除操作发生在不同端。

原则

队列遵循先进先出原则，即LIFO(list-in first-out)。

操作

  • Queue()创建一个空队列。不需要参数，返回一个空队列。

  • enqueue(item)添加元素到队列的尾部。参数为待添加元素，无返回值。

  • dequeue()移除队列头部元素。不需要参数，但返回头部元素，修改队列的内容。

  • isEmpty()检查队列是否为空。不需要参数，返回布尔值。

  • size()返回队列中元素数目。不需要参数，返回一个整数值。

实现

使用列表实现队列。

class Queue():
    def __init__(self):
        self.items = []
        
    def isEmpty(self):
        return self.items == []
    
    def enqueue(self,item):
        self.items.append(item)
        
    def dequeue(self):
        return self.items.pop(0)
    
    def size(self):
        return len(self.items)

以上代码将列表尾部当作队列尾部，可以利用列表的append和pop方法。

双端队列

两端都可以添加和移除元素。

操作

  • Deque()创建一个空的双端队列/不需要参数，返回一个空的双端队列。
  • addFront(item)将一个元素添加到双端队列的前端，无返回值。
  • addRear(item)将一个元素添加到双端队列的后端，无返回值。
  • removeFront()从双端队列的前端移除一个元素，不需要参数，返回前端第一个元素，修改队列内容。
  • removeRear()从双端队列的后端移除一个元素，不需要参数，返回后端第一个元素，修改队列内容。
  • isEmpty()检查双端队列是否为空。不需要参数，返回布尔值。
  • size()返回双端队列中元素数目。不需要参数，返回一个整数值。

实现

class Deque():
    def __init__(self):
        self.items = []
    
    def isEmpty(self):
        return self.items == []
    
    def addFront(self, item):
        self.items.insert(0, item)
        
    def addRear(self, item):
        self.items.append(item)
        
    def removeFront(self):
        return self.items.pop(0)
    
    def removeRear(self):
        return self.items.pop()
    
    def size(self):
        return len(self.items)

使用时，记住前后端的位置非常重要！

Search

    Table of Contents