Python中的栈

什么是栈

在数据结构中栈和队列可以理解为一种容器。它门也是一种简单的缓存结构，只支持数据的存储和访问。栈中的元素之间相互没有任何和的具体关系，只有时间的相互顺序。栈的相关操作包括数据元素的存入，访问删除等。

时间顺序特点

栈保证元素后进先出（Last in First Out，LIFO）。

使用环境

1、计算过程分为一些顺序进行的步骤

2、计算中执行某些步骤会不断产生一些后面可能需要的中间数据

3、产生的数据不能立即使用，但需要在将来使用。

4、需要保存的数据在个数上不能事先确定

栈的实现

一、栈的列表实现

class Stack(object):

    def __init__(self):
     # 创建空列表实现栈
        self.__list = []

    def is_empty(self):
    # 判断是否为空
        return self.__list == []
    def push(self,item):
    # 压栈，添加元素
        self.__list.append(item)

    def pop(self):
    # 弹栈，弹出最后压入栈的元素
        if self.is_empty():
            return 
        else:
            return self.__list.pop()

    def top(self): 
    # 取最后压入栈的元素
        if self.is_empty():
            return
        else:
            return self.__list[-1]

二、栈的链表实现

顺序表实现扩展存储空间操作复杂，且需要大块的存储空间；采用链表实现在这两个问题上有优势，但是链表实现更多的依赖与解释器的存储管理，会带来操作开销。

链表

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

栈的应用

1、倒序输出一组元素

把元素存入栈，在顺序取出

stack = Stack()
for x in List:
    stack.push(x)
# 翻转后的列表（新列表）
reverse_list = []
while not stack.is_empty():
    # 判断，若不为空就取出元素加入的新列表中
    reverse_list.append(stack.pop())

2、括号匹配问题
1、顺序扫描被检查字符串中的字符
2、跳过无关的字符
3、遇到开括号压入栈
4、遇到闭括号时与弹栈元素匹配，检查是否匹配
5、匹配成功继续，否则匹配失败

class Check(object):
    def __init__(self, text):
        self.text = text
        self.parens = "[](){}"
        self.open_parens = "[{("
        self.opposite = {"}": "{", "]": "[", ")": "("}
        self.len_text = len(text)
        self.index = 0
    def parent(self):
        while True:
            while self.index < self.len_text and self.text[self.index] not in self.parens:
                self.index += 1
            if self.index >= self.len_text:
                return 
                yield self.index, self.text[self.index]
                self.index += 1

    def check_parens(self):
        # 实例化一个栈
        stack = Stack()
        for index, str in self.parent():
            if str in self.open_parens:
                # 压栈
                stack.push(str)
            elif self.opposite[str] != stack.pop():
                print  "失败"
            else:
                pass
        print "匹配结束"
if __name__ == "__main__":
   # 有待改进 
   check = Check("{{))")
    check.check_parens()

待续

新手上路，道路千万条，安全第一条