2022年 11月 3日

[数据结构] 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.     #进栈
  6.     def push(self, element):
  7.         self.stack.append(element)  # 在最后一个元素进栈
  8.  
  9.     #出栈 出栈的前提是：栈不能为空
  10.     def pop(self):
  11.         try:
  12.             return self.stack.pop()  # pop不加参数默认返回最后一个，在最后一个元素出栈
  13.         except IndexError:
  14.             print('stack is empty')
  15.  
  16.     #取栈顶 取栈顶的前提是：栈不能为空
  17.     def gettop(self):
  18.         if len(self.stack) > 0:
  19.             return self.stack[-1]
  20.         else:
  21.             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