2018-07-09队列和双端队列的实现

取的一端称为队头，添加的一端称为队尾。
用顺序表的话，头部插入/弹出，时间复杂度为O（n），尾部插入/弹出，时间复杂度为O（1）
选用头部尾部的时候要看，哪一端用得多
代码实现：

# coding:utf-8

class Queue(object):
    """队列"""

    def __init__(self):
        """构造函数"""
        self.__list = []

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

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

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

if __name__ == "__main__":
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)

    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

结果实现：

结果

双端队列

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

双端队列

双端队列的头，和列表中的图没有固定的对应关系

代码实现：

# coding:utf-8

class Deque(object):
    """队列"""

    def __init__(self):
        """构造函数"""
        self.__list = []

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

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


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

    def remove_rear(self):
        """从队列尾部删除一个元素"""
        # return self.__list.pop(0)
        return self.__list.pop()

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

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


if __name__ == "__main__":
    deque = Deque()
    deque.add_front(1)
    deque.add_front(2)
    deque.add_rear(3)
    deque.add_rear(4)
    print(deque.size())
    print(deque.remove_front())
    print(deque.remove_front())
    print(deque.remove_rear())
    print(deque.remove_rear())

实现结果：

实现结果