03Stack栈

数据结构=数据+存储方式+操作
数据 存储什么数据？如int，string类型
存储方式 如何组织数据，数据之间的关系？
操作 如何快速的读取查询数据，写入数据到数据结构中？

不要求数据的顺序：维护成本低，比如List列表
要求数据的顺序：维护成本高，使用成本低，比如排序的List

栈
后进先出(LIFO)的线性数据结构

栈的操作
push 放入一个元素
pop 弹出一个元素
top 获取栈顶元素
empty 判断栈是否为空

栈的实现
使用基于List实现Stack

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append(x)

    def pop(self):
        return self.stack.pop()

    def top(self):
        return self.stack[-1]

    def isEmpty(self):
        return len(self.stack) == 0


s = Stack()
s.push(1)
s.pop()
s.push(2)
print(s.top())
s.pop()
print(s.isEmpty())
s.push(3)
print(s.isEmpty())

用LinkedList实现Stack

class LinkedNode:
    def __init__(self, value, next=None, prev=None):
        self.val = value
        self.next = next
        self.prev = prev


class Stack:
    def __init__(self):
        self.head = LinkedNode(None)
        self.tail = LinkedNode(None, None, self.head)
        self.head.next = self.tail

    def push(self, x):
        node = LinkedNode(x, self.tail, self.tail.prev)
        self.tail.prev.next = node
        self.tail.prev = node

    def pop(self):
        if self.isEmpty():
            return
        node = self.tail.prev
        node.prev.next = self.tail
        self.tail.prev = node.prev

    def top(self):
        if self.isEmpty():
            return -1
        return self.tail.prev.val

    def isEmpty(self):
        return self.head.next == self.tail and self.tail.prev == self.head


s = Stack()
s.push(1)
s.pop()
s.push(2)
print(s.top())
s.pop()
print(s.isEmpty())
s.push(3)
print(s.isEmpty())

给定一个字符串所表示的括号序列，包含以下字符： '(', ')', '{', '}', '[' and ']'， 判定是否是有效的括号序列。
括号必须依照 "()" 顺序表示， "()[]{}" 是有效的括号，但 "([)]" 则是无效的括号。

class Solution:
    def isValidParentheses(self, s):
        stack = []
        for c in s:
            if c in ['(', '[', '{']:
                stack.append(c)
            else:
                if len(stack) == 0:
                    return False
                if stack[-1] == '(' and c != ')':
                    return False
                if stack[-1] == '[' and c != ']':
                    return False
                if stack[-1] == '{' and c != '}':
                    return False
                stack.pop()
        return len(stack) == 0


s = Solution()
print(s.isValidParentheses('()[]{}'))