【数据结构】栈

什么是栈

LIFO：后进者先出，先进者后出

“操作受限”的线性表，只允许在一端插入和删除数据。

理解：一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。

栈操作

Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。

push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。

pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。

peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。

is_empty() 测试栈是否为空。不需要参数，并返回布尔值。

size() 返回栈中的 item 数量。不需要参数，并返回一个整数。

python实现

1.利用列表自定义栈

class Stack(object): #底层数据结构为列表 def __init__(self): self.stack = [] def push(self, value): # 入栈 self.stack.append(value) def pop(self): # 弹出栈顶元素 if self.stack: self.stack.pop() else: raise LookupError('stack is empty!') def is_empty(self): # 判断栈是否为空 return bool(self.stack) def peek(self): # 获取目前stack中最新的元素 return self.stack[-1] def size(self): # 返回栈的元素个数 return len(self.stack)

2.利用链表自定义栈

class Node(object): """节点的实现""" def __init__(self,elem): self.elem = elem self.next = None class Stack(object): def __init__(self): """ 初始化，链表头head""" self.__head = None def is_empty(self): """ 初始化，链表头head""" return self.__head is None def push(self,item): """ 压栈""" node = Node(item) node.next = self.__head self.__head = node def pop(self): """ 弹栈""" if self.is_empty(): return else: p = self.__head self.__head = p.next return p.elem

3.queue模块

内部也是用的列表，方法继承自queue，支持线程安全

（这里不做多讲解，【python】queue模块已讲解）

import queue stack = queue.LifoQueue() # 内部使用列表;

栈的实际应用

括号匹配问题

给定一个只包括 (，)，{，}，[，] 的字符串，判断字符串是否有效。有效字符串需满足：1、左括号必须用相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

def brace_match(s): match = {'}':'{', ')':'(', ']':'['} stack = Stack() for ch in s: if ch in ['(', '[', '{']: stack.push(ch) else: if stack.is_empty(): return False elif stack.peek() == match[ch]: stack.pop() else: return False return True if stack.is_empty() else False

迷宫问题

返回从入口发到出口的迷宫路径

# 迷宫问题：深度优先搜索 maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 0, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1, 1, 0, 1], [1, 0, 0, 0, 1, 0, 0, 1, 0, 1], [1, 1, 1, 0, 1, 1, 1, 1, 0, 1], [1, 1, 1, 0, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], ] dirs = [ lambda x, y: (x+1, y), lambda x, y: (x, y+1), lambda x, y: (x-1, y), lambda x, y: (x, y-1), ] def maze_path(x1,y1,x2,y2): stack = [] stack.append((x1, y1)) while len(stack)>0: curNode = stack[-1] if curNode == (x2,y2): print(stack) return True for dir in dirs: nextNode = dir(curNode[0], curNode[1]) if maze[nextNode[0]][nextNode[1]] == 0: stack.append(nextNode) maze[nextNode[0]][nextNode[1]] = 2 break else: maze[nextNode[0]][nextNode[1]] = 2 # 表示走过 stack.pop() else: return False maze_path(1,1,8,8)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。