前面两篇文章用C语言实现了栈（栈stack的数组和单链表实现 ），并对栈进行了应用（基于单链表实现的栈解题-LeetCode） 。

本篇文章将使用python3实现栈并进行解题。

首先定义一个栈的类，和栈的每一个节点的类。其中栈中包括他的top指针、他的大小和他的单个节点；单个节点中包括数据和相当于指向下一个节点的指针。

class Stack://栈的类

    class Node://栈的每一个节点的类
        def __init__(self, data, next):
            self._data = data//节点的数据域
            self._next = next//节点的指针域

    def __init__(self):
        self._top = None//栈的top指针
        self._size = 0//栈的大小

对栈的操作，我们先只定义三个简单的方法：StackPush()、StackPop()、IsStackEmpty():

先分析一下方法StackPush：

一行代码搞定，比较抽象，需要仔细理解：self._top = self.Node(data, self._top)

通俗的理解就是，新加入的节点作为栈的top节点，而新加入的节点的next的指针指向原来栈的top节点。

def StackPush(self, data):
        self._top = self.Node(data, self._top)
        self._size += 1
        //print("push:", data, "size:", self._size)

分析方法StackPop：

如果栈空就不需要弹出节点了，报出异常：

class StackEmptyException(Exception):  # 空栈时抛出异常
    pass
    
if self.IsStackEmpty():
            raise StackEmptyException('Error:trying to pop from empty stack')

把栈顶数据弹出，top指针指向下一个数据节点，栈的大小减1

 def Stackpop(self):
        if self.IsStackEmpty():
            raise StackEmptyException('Error:trying to pop from empty stack')
        ans = self._top._data
        self._top = self._top._next
        self._size -= 1
       // print("pop:", ans, "size:", self._size)
        return ans

分析方法IsStackEmpty()

栈的大小为0，则栈已经为空。

def IsStackEmpty(self):
        return self._size == 0

pyhton3 栈的代码清单如下：

class StackEmptyException(Exception):  # 空栈时抛出异常
    pass


class Stack:

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

    def __init__(self):
        self._top = None
        self._size = 0

    def StackPush(self, data):
        self._top = self.Node(data, self._top)
        self._size += 1
        print("push:", data, "size:", self._size)

    def IsStackEmpty(self):
        return self._size == 0

    def Stackpop(self):
        if self.IsStackEmpty():
            raise StackEmptyException('Error:trying to pop from empty stack')
        ans = self._top._data
        self._top = self._top._next
        self._size -= 1
        print("pop:", ans, "size:", self._size)
        return ans

对栈进行应用，基于单链表实现的栈解题-LeetCode 中使用c语言编写了代码，我们使用python3改写一下：

代码清单见下：

class StackEmptyException(Exception):  # 空栈时抛出异常
    pass


class Stack:

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

    def __init__(self):
        self._top = None
        self._size = 0

    def StackPush(self, data):
        self._top = self.Node(data, self._top)
        self._size += 1
        print("push:", data, "size:", self._size)

    def IsStackEmpty(self):
        return self._size == 0

    def Stackpop(self):
        if self.IsStackEmpty():
            raise StackEmptyException('Error:trying to pop from empty stack')
        ans = self._top._data
        self._top = self._top._next
        self._size -= 1
        print("pop:", ans, "size:", self._size)
        return ans


class Valid:
    def mach(self, c):
        if (c == '}'):
            return '{'
        elif (c == ')'):
            return '('
        elif (c == ']'):
            return '['
        else:
            return False

    def isValid(self, strings):
        stack = Stack()

        for string in strings:
            if(len(strings) % 2 != 0):
                return False
            if((string == '{') or (string == '(') or (string == '[')):
                Stack.StackPush(stack, string)
            else:
                if(Stack.IsStackEmpty(stack)):
                    return False
                if(self.mach(string)):
                    data = Stack.Stackpop(stack)
                    if(data != self.mach(string)):
                        return False
        return Stack.IsStackEmpty(stack)


if __name__ == "__main__":
    s = "[[[]]]{}"
    valid = Valid()
    ret = valid.isValid(s)
    print(ret)

数据结构系列：

栈stack的数组和单链表实现

基于单链表实现的栈解题-LeetCode

判断二叉树是否为平衡二叉树

平衡二叉树 构建平衡二叉树

如何优雅地画好二叉树

二叉树的层序遍历及应用

二叉树遍历的思维导图

平衡二叉树的结点删除操作

不平衡二叉树的旋转（LL、RR、LR、RL）

二叉查找树（BST：Binary Search Tree）

LeetCode系列：

确定有限状态机(DFA)-Leet

字符串转换成一个 32 位有符号整数-atoi 函数Leet

leetcode2. 两数相加-c语言-python3

LeetCode4. 寻找两个正序数组的中位数

LeetCode5.1-马拉车算法求解最长回文子串

LeetCode5.0-最长回文子串-中心扩展法-C语言

LeetCode5.2-动态规划求解最长回文子串

LeetCode7.翻转整数-C语言与python的异同点