黑马程序员技术交流社区

标题: 【郑州校区】 python数据结构与算法（11） [打印本页]

---

作者: 谷粒姐姐    时间: 2018-11-29 14:50
标题: 【郑州校区】 python数据结构与算法（11）
队列
队列（queue）是只允许在⼀端进⾏插⼊操作，⽽在另⼀端进⾏删除操作的 线性表。
队列是⼀种先进先出的（First        In        First        Out）的线性表，简称FIFO。允许插⼊ 的⼀端为队尾，允许删除的⼀端为队头。队列不允许在中间部位进⾏操作！ 假设队列是q=（a1，a2，……，an），那么a1就是队头元素，⽽an是队尾 元素。这样我们就可以删除时，总是从a1开始，⽽插⼊时，总是在队列最 后。这也⽐较符合我们通常⽣活中的习惯，排在第⼀个的优先出列，最后来 的当然排在队伍最后。

队列的实现
同栈⼀样，队列也可以⽤顺序表或者链表实现。
操作
Queue()        创建⼀个空的队列 enqueue(item)        往队列中添加⼀个item元素 dequeue()        从队列头部删除⼀个元素 is_empty()        判断⼀个队列是否为空 size()        返回队列的⼤⼩

[AppleScript] 纯文本查看 复制代码

class        Queue(object):                                """队列"""                                def        __init__(self):                                                                self.items        =        []

                                def        is_empty(self):                                                                return        self.items        ==        []

                                def        enqueue(self,        item):                                                                """进队列"""                                                                self.items.insert(0,item)

                                def        dequeue(self):                                                                """出队列"""                                                                return        self.items.pop()

                                def        size(self):                                                                """返回⼤⼩"""                                                                return        len(self.items)

if        __name__        ==        "__main__":                                q        =        Queue()

队列的实现

50

[AppleScript] 纯文本查看 复制代码

        q.enqueue("hello")                                q.enqueue("world")                                q.enqueue("itcast")                                print        q.size()                                print        q.dequeue()                                print        q.dequeue()                                print        q.dequeue()

双端队列
双端队列（deque，全名double-ended        queue），是⼀种具有队列和栈的性 质的数据结构。
双端队列中的元素可以从两端弹出，其限定插⼊和删除操作在表的两端进 ⾏。双端队列可以在队列任意⼀端⼊队和出队。


操作
Deque()        创建⼀个空的双端队列 add_front(item)        从队头加⼊⼀个item元素 add_rear(item)        从队尾加⼊⼀个item元素 remove_front()        从队头删除⼀个item元素 remove_rear()        从队尾删除⼀个item元素 is_empty()        判断双端队列是否为空 size()        返回队列的⼤⼩

实现

[AppleScript] 纯文本查看 复制代码

class        Deque(object):                                """双端队列"""                                def        __init__(self):                                                                self.items        =        []

                                def        is_empty(self):                                                                """判断队列是否为空"""

        return        self.items        ==        []

                                def        add_front(self,        item):                                                                """在队头添加元素"""                                                                self.items.insert(0,item)

                                def        add_rear(self,        item):                                                                """在队尾添加元素"""                                                                self.items.append(item)

                                def        remove_front(self):                                                                """从队头删除元素"""                                                                return        self.items.pop(0)

                                def        remove_rear(self):                                                                """从队尾删除元素"""                                                                return        self.items.pop()

                                def        size(self):                                                                """返回队列⼤⼩"""                                                                return        len(self.items)

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()

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2