python使用顺序表实现队列

1. 队列

队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表。原理运作为先进先出

1.1 python实现队列

1.1.1 构造函数

• 使用顺序表list作为队列的容器
• 将list设为私有

class Queue(object):
    """队列的代码实现"""
    def __init(self):
        self.__init = []

1.1.2 enqueue函数

• 作用：进入队列，往队列添加一个元素
• 使用append在末尾追加【在末尾添加元素就确定了要在头部弹出元素】

    def enqueue(item):
        """往队列中添加一个item元素"""
        self.__list.append(item)

1.1.2 dequeue函数

• 作用：弹出元素，在队列的头部弹出元素
• 使用pop(0)从队列头部弹出元素
• 头部尾部的选择应该看经常进行入队还是出队的操作，哪个频繁就减少哪个的时间复杂度

def dequeue(self):
        """从队列头部删除一个元素"""
        self.__list.pop(0)

1.1.3 is_empty函数

• 作用：判断队列是否为空

def is_empty(self):
        """判断一个队列是否为空"""
        return self.__list == []

1.1.4 size函数

• 作用：返回队列的元素个数
• 使用len即可

def size(self):
        """返回队列的大小"""
        return len(self.__list)

1.2 完整代码

class Queue(object):
    """队列的代码实现"""
    def __init(self):
        self.__init = []
        
    def enqueue(item):
        """往队列中添加一个item元素"""
        self.__list.append(item)
        
    def dequeue(self):
        """从队列头部删除一个元素"""
        self.__list.pop(0)
        
    def is_empty(self):
        """判断一个队列是否为空"""
        return self.__list == []
        
    def size(self):
        """返回队列的大小"""
        return len(self.__list)

---

2. 双端队列

双端队列：具有队列和栈的属性的结构，元素可以从两端弹出，其限定插入和删除操作在表的两端进行，双端队列可以在队列任意一端入队和出队

2.1 python实现双端队列

2.1.1 构造函数

• 使用顺序表list作为队列的容器
• 将list设为私有

class Deque(object):
    def __init(self):
        self.__init = []

2.1.2 add_front【头部添加】

• 作用：在头部添加元素
• 使用insert方法，在头部添加元素

def add_front(self,item):
        """往队列头部添加一个item元素"""
        self.__list.insert(0,item)

2.1.3 add_rear【尾部添加】

• 作用：在尾部添加元素
• 使用append方法，在尾部添加元素

def add_rear(self,item):
        """往队列尾部添加一个元素"""
        self.__list.append(item)

2.1.4 pop_front【头部取出】

• 作用：从队列头部取出元素
• 使用pop(0)取出头部元素

def pop_front(self):
        """从队列头部弹出一个元素"""
        return self.__list.pop(0)

2.1.5 pop_rear【尾部取出】

• 作用：从队列尾部取出元素
• 使用pop()取出头部元素

def pop_rear(self):
        """从队列尾部弹出一个元素"""
        return self.__list.pop(

is_empty和size方法普通的队列相同

2.2 完整代码

class Deque(object):
    def __init(self):
        self.__init = []
        
    def add_front(self,item):
        """往队列头部添加一个item元素"""
        self.__list.insert(0,item)
        
    def add_rear(self,item):
        """往队列尾部添加一个元素"""
        self.__list.append(item)
    
    def pop_front(self):
        """从队列头部弹出一个元素"""
        return self.__list.pop(0)
    def pop_rear(self):
        """从队列尾部弹出一个元素"""
        return self.__list.pop()

    def is_empty(self):
        """判断一个队列是否为空"""
        return self.__list == []
        
    def size(self):
        """返回队列的大小"""
        return len(self.__list)