35_栈的概念及实现（下）

关键词：StaticStack的缺陷、链式栈的存储实现、LinkStack.h、符号成对检测

0. 问题：StaticStack的缺陷：

当存储的元素为类类型时， StaticStack的对象在创建时会多次调用元素类型的构造函数，影响效率。
产生缺陷的原因：
StaticStack在实现时以原生数组作为存储空间，在创建StaticStack时会调用元素类型的构造函数来确定单个存储空间的大小。

1. 链式栈的存储实现

链式栈的原理图

2. 链式栈的设计要点

• 类模板，抽象父类Stack的直接子类
• 在内部组合使用LinkList类，实现栈的链式存储
• 只在单链表成员对象的头部进行操作
  链式栈的继承层次结构图

LinkStack.h

#ifndef LINKSTACK_H
#define LINKSTACK_H

#include "Stack.h"
#include "LinkList.h"

namespace DTLib
{

template < typename T >
class LinkStack : public Stack<T>
{
protected:
    LinkList<T> m_list;
public:
    void push (const T& e);
    void pop();
    T top() const;
    void clear();
    int size() const;
};

template < typename T >
void LinkStack<T>::push (const T& e)
{
    m_list.insert(0, e);
}

template < typename T >
void LinkStack<T>::pop()
{
    if( m_list.length() > 0 )
    {
        m_list.remove(0);
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No element in current stack ...");
    }
}

template < typename T >
T LinkStack<T>::top() const
{
    if( m_list.length() > 0 )
    {
        return m_list.get(0);
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No element in current stack ...");
    }
}

template < typename T >
void LinkStack<T>::clear()
{
    m_list.clear();
}

template < typename T >
int LinkStack<T>::size() const
{
    return m_list.length();
}

}

#endif // LINKSTACK_H

3. 栈的应用实践——实现编译器中的符号成对检测

算法思路：

• 从第一个字符开始扫描
  当遇见普通字符时忽略
  当遇见左符号时，压入栈中
  当遇见右符号时，弹出栈中的符号，并进行匹配
• 结束
  成功：所有字符扫描完成，且栈为空
  失败：匹配失败或所有字符扫面完成但栈非空

#include "LinkStack.h"
/* -----符号匹配----- */
bool isLeft(char c)
{
    return (c == '(') || (c == '{') || (c == '[') || (c == '<');
}

bool isRight(char c)
{
    return (c == ')') || (c == '}') || (c == ']') || (c == '>');
}

bool isQuot(char c)
{
    return (c == '\'') || (c == '\"');
}

bool isMatch(const char l, const char r)
{
    return ( (l == '(') && ( r == ')') ) ||
           ( (l == '{') && ( r == '}') ) ||
           ( (l == '[') && ( r == ']') ) ||
           ( (l == '<') && ( r == '>') ) ||
           ( (l == '\'') && ( r == '\'') ) ||
           ( (l == '\"') && ( r == '\"') );
}

bool scan(const char* str)
{
    LinkStack<char> stack;
    int i = 0;
    bool ret = true;

    str = (str == NULL) ? "" : str;

    while( ret && (str[i] != '\0') )
    {
        if( isLeft(str[i]) )
        {
            stack.push(str[i]);
        }
        else if( isRight(str[i]) )
        {
            if( (stack.size() > 0) && isMatch(stack.top(), str[i]) )
            {
                stack.pop();
            }
            else
            {
                ret = false;
            }
        }
        else if( isQuot(str[i]) )
        {
            if( (stack.size() == 0) || !isMatch(stack.top(), str[i]) )
            {
                stack.push(str[i]);
            }
            else if( isMatch(stack.top(), str[i]) )
            {
                stack.pop();
            }
        }

        ++i;
    }

    return ret && (stack.size() == 0);
}

void test_operate_match()
{
    if( scan("(){}<>\"\"") )
    {
        cout << "match!" << endl;
    }
    else
    {
        cout << "NO match!!!" << endl;
    }
}

4. 小结

• 链式栈的实现组合使用了单链表对象
• 在单链表的头部操作能够实现高效的入栈和出栈操作
• 栈后进先出的特性适用于检测成对出现的符号
• 栈非常适用于需要就近匹配的场合

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4