yuruoyuxi
数据结构入门(三)栈的应用
数据结构入门(三)栈的应用

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

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

  栈的结构实现可以参考数据结构入门(二)栈的应用之数学表达式求值,本文将不再具体给出。

判断字符串是否回文

  所谓回文字符串就是指正读反读均相同的字符序列,如“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实现,用栈实现前序遍历的函数如下:

    # 使用栈结构实现前序遍历
    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)

构建的示例二叉树如下:

https://upload-images.jianshu.io/upload_images/9419034-11f244bbbd251bb9.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240

输出的结果如下:

先序遍历(递归)为:
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/ 。

参考文献

  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
没有标签
首页      开发      cnblogs      数据结构入门(三)栈的应用

yuruoyuxi

数据结构入门(三)栈的应用
  在之前的两篇文章——数据结构入门(一)栈的实现和数据结构入门(二)栈的应用之数学表达式求值中,笔者分别介绍了“栈”这个数据结构在数的进制转换和数学表达式求值方面的应用。在本文中…
扫描二维码继续阅读
2018-12-26
Categories