什么是栈

原文地址:What is a stack
翻译:Recheal
“栈”(有时被称为“push-down stack”)是存储数据的一种有序集合,在集合中添加和移除已有的项只能从同一个的尾端开始。这个尾端常常被称为这个特殊数据结构的“顶”(top),而与这个取用删除数据相对的头部被大家称作为“基部”(base)。

栈的基部很重要,因为在栈中离基部越近的项意味着该项留存得时间越长,而最先被添加的项则被安置在最先被取用移除数据的位置上。因此,有人将这种排序原则称为LIFO,即留存越久的数据保留,刚刚添加的数据越先被删除。显然,这种数据结构是基于时间维度的。
事实上,栈的例子在生活中随处可见。比如当你要取用一堆书的时候,你会先把上面的书先移动下来,再抽取下面的书。拿网络中实际的例子来说,当你浏览网页,想要返回到上一页的时候,事实上就是对排列成“栈”的URL进行取用,你点击了回退的按钮,事实上就是访问了处于“栈”最顶端,即最近所访问的网页。

栈的python实现

上面我们已经明确了栈的特性,那么现在我们先来纸上谈兵地说说,如果我们想要创建一个栈的数据结构,它应该具有什么样的运算特性。
Stack()创建一个新的空栈,它不需要参数并且其返回值为空。
push(item)将会在栈的顶端添加数据,它需要以item为输入,不会有返回。
pop()将会删除栈顶端的数据,它不需要参数,栈会因此被改变。
peek()将会返回栈顶端的数据,但是并不会移动这个数据,栈不会受到影响。
isEmpty()将会测试栈是否为空,不需要参数输入,并且会返回布尔值。
size()不需要输入,会返回栈内数量的个数。

有了上述理解之后,我们再回到实际中,尝试用python来构建一个具有上述特性的栈。python作为面向对象的语言之一,其创建像栈一样的抽象数据类型的实现方法是创建一个新类(class),而上述栈的运算特性则会被实现为这个类的函数。另外,由于栈是数据项的集合,正好与python的list相对应,所以我们将栈中的数据放置在lsit里面。

class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[len(self.items)-1]
    def size(self):
        return len(self.items)

确实挺简单的!事实上,pythonds模块(包括basic,tree,graphs三个模块)中已经包含了所有本书中讨论的数据结构,因此我们实际中需要使用的时候并不需要自己创建,只需要from pythonds.basic.stack import Stack即可。

在Python中使用栈解决实际问题

在现实中,我们对于数学表达式(5+6)*(7+8)/(4+3)并不存在歧义的理解,可是在程序语言Lisp中,我们却常常被太多的括号搞晕(这也是Lisp为人诟病的槽点之一)。
在大部分情况下,我们希望括号能够和谐分布(in balanced fashion),即有开括号即在不远处可以找到其比括号。
比如像这样:

(()()()())
(((())))
(()((())()))

而那些不和谐的括号,则常常是这样的:

((((((())
()))
(()()(()

区别出和谐括号分布和不和谐括号分布的能力是识别许多程序语言结构的重要组成部分。我们现在的挑战就是要写一个算法,这个算法可以讲括号字符串从左向右读取并分辨出是否是和谐括号分布。为了解决这个问题,我们需要好好观察。首先,当我们从左到右地处理符号的时候,我们最近所处理的开括号一定是和下一个比括号相对应的,而我们第一个处理到的开括号可能要等到处理到最后才能够访问到,下面这张图是使用栈来解决这个问题的一个线索:

form pythonds.basic.stack import Stack
def parChecker(symbol):
    s= Stcack()
    balanced = True
    index = 0
    while index<len(symbol) and balanced ==True:
        if symbol[index] == "(":
            s.push(symbol[index])
        else:
            if s.isEmpty == True:
                balanced = False
            else:
                s.pop()
            index = index +1
    if balanced and s.isEmpty():
        return True
    else:
        return False