使用栈

Python 中的数据结构与算法

Miriam Antona

Software Engineer

栈

  • LIFO： 后进先出
    • 最后插入的项会最先被移除

一叠书的图片。

Python 中的数据结构与算法

栈

  • LIFO： 后进先出
    • 最后插入的项总是最先被移除
  • 只能在顶部进行添加
    • 向栈压入（push）

在栈顶添加了一本新书的一叠书图片。

Python 中的数据结构与算法

栈

  • LIFO： 后进先出
    • 最后插入的项总是最先被移除
  • 只能在顶部进行添加
    • 向栈压入（push）
  • 只能从顶部**取出**
    • 从栈弹出（pop）

一叠书的图片，从栈顶取走了一本书。

Python 中的数据结构与算法

栈

  • LIFO： 后进先出
    • 最后插入的项总是最先被移除
  • 只能在顶部进行添加
    • 向栈压入（push）
  • 只能从顶部进行移除
    • 从栈弹出（pop）
  • 只能读取**最后一个元素**
    • 从栈窥视（peek）

一叠书的图片，箭头指向最上面那本书的封面。

Python 中的数据结构与算法

栈 - 实际应用

  • 撤销功能

只有一个元素的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 撤销功能
    • 每次按键都push

在栈顶添加了新元素的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 撤销功能
    • 每次按键都push

在栈顶添加了新元素的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 撤销功能
    • 每次按键都push

在栈顶添加了新元素的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 撤销功能
    • 每次按键都push

在栈顶添加了新元素的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 撤销功能
    • 每次按键都push
    • pop最后一次按键

从栈顶移除了一个元素的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 符号检查器： ( [ { } ] )
    • push左括号

包含一个左括号的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 符号检查器： ( [ { } ] )
    • push左括号

在栈顶添加了一个新的左括号的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 符号检查器： ( [ { } ] )
    • push左括号

在栈顶添加了一个新的左括号的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 符号检查器： ( [ { } ] )
    • push左括号
    • 检查右括号

含有左括号并带有"check "}""字样的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 符号检查器： ( [ { } ] )
    • push左括号
    • 检查右括号
    • pop匹配的左括号

从栈顶移除了一个左括号的栈。

Python 中的数据结构与算法

栈 - 实际应用

  • 函数调用
    • push内存块
    • 执行结束后pop
Python 中的数据结构与算法

栈 - 用单链表实现

以链表表示的栈。

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None
Python 中的数据结构与算法

栈 - 用单链表实现

以链表表示的栈，并标出节点各部分名称。

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None
Python 中的数据结构与算法

栈 - 用单链表实现

以链表表示的栈，"TOP" 指向栈顶。

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None
Python 中的数据结构与算法

栈 - push

空栈与有元素的栈示意图。

def push(self, data):
Python 中的数据结构与算法

栈 - push

空栈与有元素的栈示意图，准备插入新节点。

def push(self, data): 
  new_node = Node(data)

  if self.top:
Python 中的数据结构与算法

栈 - push

空栈与有元素的栈示意图，新节点连接到栈顶元素。

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top
Python 中的数据结构与算法

栈 - push

空栈与有元素的栈示意图，新节点已插入。

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node
Python 中的数据结构与算法

栈 - pop

def pop(self):

  if self.top is None:

    return None

  else:

栈的示意图，"TOP" 指向栈顶节点。

Python 中的数据结构与算法

栈 - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

栈的示意图，"popped_node" 指向栈顶节点。

Python 中的数据结构与算法

栈 - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

栈的示意图，"popped_node" 指向原栈顶，"TOP" 指向第二个节点。

Python 中的数据结构与算法

栈 - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

栈的示意图，"popped_node" 指向已与栈断开的节点，"TOP" 指向新的栈顶。

Python 中的数据结构与算法

栈 - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

栈的示意图，"TOP" 指向栈顶节点。

Python 中的数据结构与算法

栈 - peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None
Python 中的数据结构与算法

Python 中的 LifoQueue

  • LifoQueue：
    • Python 的 queue 模块
    • 行为与栈相同
import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True
Python 中的数据结构与算法

Passons à la pratique !

Python 中的数据结构与算法

Preparing Video For Download...