数据结构入门（三）栈的应用

待我称王封你为后i 2022-04-02 11:23 254阅读 0赞

在之前的两篇文章——[数据结构入门（一）栈的实现][Link 1]和[数据结构入门（二）栈的应用之数学表达式求值][Link 2]中，笔者分别介绍了“栈”这个数据结构在数的进制转换和数学表达式求值方面的应用。在本文中，笔者将会再介绍栈的四个应用，它们分别是：

*  判断字符串是否回文
 *  括号匹配
 *  行编辑程序
 *  二叉树的深度优先遍历

栈的结构实现可以参考[数据结构入门（二）栈的应用之数学表达式求值][Link 2]，本文将不再具体给出。

### 判断字符串是否回文 ###

所谓回文字符串就是指正读反读均相同的字符序列，如“12321”、“aha”、“ahaha”、“清水池里池水清”均是回文，但“ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。  
  首先我们需要找到该字符串的中心点。对于长度为奇数的字符串，中心点就是中间的那个元素；对于长度为偶数的字符串，中心点恰好位于长度为一半的那个元素及其后一个元素的中间。接着将中心点前面的字符依次入栈，然后将当前栈中的字符依次出栈，看看是否能与 中心点之后的字符一一匹配，如果都能匹配则说明这个字符串是回文字符串，否则就不是回文字符串。  
  以下是利用栈来实现判断字符串是否回文的Python代码：

# -*- coding: utf-8 -*-
    # using Stack to check if a string is plalindrome
    
    from Stack import Stack
    
    def isPlalindrome(words):
        length = len(words)
        flag = length//2
        s = Stack()
        for i in range(flag):
            s.push(words[i])
    
        start = flag+1 if length % 2 else flag
        for item in words[start:]:
            if s.pop() != item:
                return False
    
        return True
    
    def main():
        words_list = ["12321", "aha", "ahaha", "清水池里池水清", "ahah"]
        for words in words_list:
            res = isPlalindrome(words)
            print("'%s' is plalindrome: %s" % (words, res))
    
    main()

输出结果如下：

> ‘12321’ is plalindrome: True  
> ‘aha’ is plalindrome: True  
> ‘ahaha’ is plalindrome: True  
> ‘清水池里池水清’ is plalindrome: True  
> ‘ahah’ is plalindrome: False

### 括号匹配 ###

在字符串中，我们常常会遇到括号匹配的问题，常见的括号如下：

*  小括号： “(”和“）”
 *  中括号： “\[”和“\]”
 *  花括号： “\{”和“\}”

每一个开符号必须匹配与其对应的闭符号。以下为匹配示例：

*  正确: ( )(( ))\{(\[( )\])\}
 *  正确: ((( )(( ))\{(\[( )\])\}))
 *  错误: )(( ))\{(\[( )\])\}
 *  错误: (\{\[\])\}
 *  错误: (

下面说明括号匹配的算法。从左至右检查每个元素，用栈S储存括号。每当遇到一个开符号时，就入栈，每当遇到闭符号时，就出栈（假设S非空），并检查两者是否匹配。如果所有元素都检查完毕，且栈S为空，那么原来的表达式括号匹配，否则就不匹配。  
  下面是括号匹配的Python代码：

# -*- coding: utf-8 -*-
    # matching parentheses
    
    from Stack import Stack
    
    def is_matched(expr):
        # return True if all delimiters are properly match; False otherwise
        lefty = '({['   # opening delimiters
        righty = ')}]'  # respective closing delimiters
        s = Stack()
        for c in expr:
            if c in lefty:
                s.push(c)
            elif c in righty:
                if s.is_empty():    # nothing to match with
                    return False
                if righty.index(c) != lefty.index(s.pop()): # mismatched
                    return False
        return s.is_empty()
    
    def main():
        expr_list = ['[(5+x)-(y+z)]', '(5+x))*y', '{[1+(x+y)]}*[(3*z)]']
        for expr in expr_list:
            Flag = is_matched(expr)
            print('%s is matched: %s' %(expr, Flag))
    
    main()

输出结果如下：

> \[(5+x)-(y+z)\] is matched: True  
> (5+x))*y is matched: False  
> \{\[1+(x+y)\]\}*\[(3\*z)\] is matched: True

### 行编辑程序 ###

一个简单的行编辑程序的功能是：接收用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接收一个字符即存入用户数据区”的做法是不恰当的。较好的做法是，设立一个输入缓冲区，用以接受用户输入的每一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚输入的一个字符是错的时，可以补进一个退格符“\#”，表示前一个字符无效；如果发现当前输入的行内差错较多或难以补救，则可以输入一个退行符“@”，表示当前行中的字符均无效。比如，假设从终端接收了两行这样的字符：

> whli\#\#ilr\#e(s\#\*s)  
> outcha@putchar(\*s=\#++);

则实际有效的是下列两行：

> while(\*s)  
> putchar(\*s++);

行编辑程序的输出结果可用栈来解决。可设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符后先做如下判别：如果它既不是退格符也不是退行符，则将该字符入栈；如果是一个退格符，则从栈顶删去一个字符；如果它是退行符，则将该栈清空。以下为实现行编辑程序的Python代码：

# -*- coding: utf-8 -*-
    # line edit programming
    from Stack import Stack
    
    # line edit programming using Stack
    def LineEdit(chars):
    
        s = Stack()
        for char in chars:
            if char != '\n':    # line edit
                if char == '#':
                    s.pop()
                elif char == '@':
                    s.clear()
                else:
                    s.push(char)
            else:   # output
                line = []
                while not s.is_empty():
                    line.append(s.pop())
                print(''.join(line[::-1]))
    
    def main():
        chars = """whli##ilr#e(s#*s) outcha@putchar(*s=#++) fi@if a=# == 'exti##it': system@ sys.tiex####exit((#) """
    
        LineEdit(chars)
    
    main()

输出结果如下：

while(*s)
    putchar(*s++)
    if a == 'exit':
        sys.exit()

### 二叉树的深度优先遍历 ###

关于二叉树的介绍与实现，可以参考笔者的文章：[二叉树的Python实现][Python]。二叉树的深度优先遍历，也就是先序、中序、后续遍历，在文章[二叉树的Python实现][Python]中，我们已经用递归的方法实现了，这是因为二叉树天然就具有良好的递归性质，就连它的定义也可用递归来实现。在本文中，笔者将要用栈来实现二叉树的深度优先遍历。  
  以先序遍历为例，先访问根结点，然后遍历左子树接着是遍历右子树，因此我们可以利用堆栈的先进后出的特点，先将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历。  
  二叉树的实现代码不再给出，读者可参考[二叉树的Python实现][Python]，用栈实现前序遍历的函数如下：

# 使用栈结构实现前序遍历
        def preStack(self):
            if self.data is not None:
                s = Stack()
                s.push(self)
                while not s.is_empty():
                    currentNode = s.pop()
                    print(currentNode.data, end=' ')
                    if currentNode.right is not None:
                        s.push(currentNode.right)
                    if currentNode.left is not None:
                        s.push(currentNode.left)

构建的示例二叉树如下：

![示例二叉树][2018122615123593]

输出的结果如下：

先序遍历（递归）为:
    18 7 3 4 11 5 1 3 6 2 4 
    先序遍历（非递归）为:
    18 7 3 4 11 5 1 3 6 2 4

### 总结 ###

堆栈（Stack）最早由 Alan M. Turing（艾伦·图灵）于 1946 年提出，当时是为了解决子程序的调用和返回。在本文及前面的文章中，介绍了一些关于栈的应用，当然，还有许多话题未涉及，比如：解决迷宫问题，HTML标签匹配，子程序的调用和返回等。另外，栈还常常与递归方法一起使用，能轻松地解决很多问题~  
  关于栈在其它问题中的应用，可以参考网址: [https://www.geeksforgeeks.org/stack-data-structure/][https_www.geeksforgeeks.org_stack-data-structure] 。

### 参考文献 ###

1.  《啊哈！算法》啊哈磊著 人民邮电出版社 p32-35
2.  《数据结构(C语言版)》 严蔚敏 吴伟民 著 清华大学出版社 p48-50
3.  *Data Structures & Algorithms in Python*, M.T.Goodrich, R.Tamassia, M.H.Goldwasser著, p229-237
4.  二叉树深度遍历的非递归算法分析及Java实现: [https://my.oschina.net/husthang/blog/852982][https_my.oschina.net_husthang_blog_852982]

[Link 1]: https://www.jianshu.com/p/d47397c21f2e
[Link 2]: https://www.jianshu.com/p/0e17f00d7559
[Python]: https://www.jianshu.com/p/9503238394df
[2018122615123593]: /images/20220402/a981fde2bc71486897b9ae65020499b6.png
[https_www.geeksforgeeks.org_stack-data-structure]: https://www.geeksforgeeks.org/stack-data-structure/
[https_my.oschina.net_husthang_blog_852982]: https://my.oschina.net/husthang/blog/852982