【数据结构】栈

什么是栈

• 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)