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

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

列表作为栈使用

列表提供的方法,让我们很方便的实现后进先出的具有栈特性的操作。要添加一个元素到堆栈的顶端,使用 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 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    541 引用 • 672 回帖 • 1 关注
  • list
    10 引用 • 15 回帖

相关帖子

欢迎来到这里!

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

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