python 中的列表作为栈和队列的使用方式

本贴最后更新于 1879 天前,其中的信息可能已经天翻地覆

列表作为栈使用

列表提供的方法,让我们很方便的实现后进先出的具有栈特性的操作。要添加一个元素到堆栈的顶端,使用 append() 。要从堆栈顶部取出一个元素,使用 pop() ,不用指定索引

In [9]: stack = [3,4,5,6] In [10]: stack.append(7) In [11]: stack Out[11]: [3, 4, 5, 6, 7] In [12]: stack.pop() Out[12]: 7 In [13]: stack Out[13]: [3, 4, 5, 6]

列表作为队列使用

队列的特性是后进后出,一端入队另一端出队,使用 append 队尾添加元素,使用 pop(0) 对首元素出队

In [14]: queue = [5,6,7] In [15]: queue.append(8) In [16]: queue Out[16]: [5, 6, 7, 8] In [17]: queue.pop(0) Out[17]: 5 In [18]: queue Out[18]: [6, 7, 8]

但是这种实现方式是比较低效的,pop 的操作时间复杂度是 O(N)的,因为每次队首元素出队后,其他位置的元素都要向前移动一位.
python 中提供了更加高效的队列实现,deque,他是一个双向队列对象,也就是说两端都可以入队和出队,而且时间复杂度都是 O(1).

In [19]: from collections import deque In [20]: d = deque((4,6,7,8)) In [21]: d Out[21]: deque([4, 6, 7, 8]) In [22]: d.append(9) In [23]: d.popleft() Out[23]: 4 In [24]: d Out[24]: deque([6, 7, 8, 9])

删除列表某个切片

在列表中删除某个切片内的元素一般有两种场景,

  • 将指定的切片赋值为空列表
In [25]: a = [3,4,5,6,7] In [26]: a[2:4] = [] In [27]: a Out[27]: [3, 4, 7]
  • 使用 del 语句
In [30]: b = [5,6,7,8,9,0] In [31]: del b[2:5] In [32]: b Out[32]: [5, 6, 0]
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    549 引用 • 674 回帖
  • list
    10 引用 • 15 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...