2022年 11月 10日

[数据结构] python 栈的介绍

一、栈

栈(Stack)是一个数据集合,可以理解为只能在一端进行插入或删除的列表

栈的特点:后进先出LIFO(last-in,first-out)

栈的概念:栈顶(其实也就是列表最后一个元素位置)、栈底(列表第一个元素的位置)

栈的基本操作:

进栈(压栈):push

出栈:pop

取栈顶:gettop

(取栈顶也可认为:假如面前有一堆书,但是我只取最上面的那个看一眼,但是我不拿走)

二、栈的实现

使用一般的列表结构实现栈:

进栈:li.append

出栈:li.pop

取栈顶:li[-1]

以下代码将实现一个简单的栈结构:

  1. class Stack:
  2. def __init__(self):
  3. self.stack = []
  4. #进栈
  5. def push(self, element):
  6. self.stack.append(element) # 在最后一个元素进栈
  7. #出栈 出栈的前提是:栈不能为空
  8. def pop(self):
  9. try:
  10. return self.stack.pop() # pop不加参数默认返回最后一个,在最后一个元素出栈
  11. except IndexError:
  12. print('stack is empty')
  13. #取栈顶 取栈顶的前提是:栈不能为空
  14. def gettop(self):
  15. if len(self.stack) > 0:
  16. return self.stack[-1]
  17. else:
  18. return None

以上写了两种处理报错的方法,处理报错的方法有很多,也可以用raise方法。

调用:

  1. stack = Stack()
  2. stack.push(1)
  3. stack.push(2)
  4. print(stack.pop())
  5. print(stack.pop())
  6. print(stack.pop())

返回:

  1. 2
  2. 1
  3. None

栈的调用其实还有一种方法:

python中的collections模块,里面实现了许多常用的数据结构,collections.deque实现线程安全的双端队列,可以用它作为栈,也可以用它作为队列。

入栈为:deque.append(x)

出栈为:deque.pop(x)

关于deque的详情网页点击这里https://blog.csdn.net/qq_51148692/article/details/120394497?spm=1001.2014.3001.5501

以下代码将用deque作为栈示例:

  1. from collections import deque
  2. stack=deque() #初始化栈
  3. stack.append(1) #从列表的右端(最后一个元素后)添加元素
  4. stack.append(2)
  5. stack.append(3)
  6. print(stack.pop()) #从列表的右端(最后一个元素)弹出元素
  7. print(stack.pop())
  8. print(stack.pop())

输出为:

  1. 3
  2. 2
  3. 1