第五章

5.1  基本概念

栈(stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈的顶(top),它是后进先出(LIFO)的。对栈的基本操作只有push(进栈)和pop(出栈)两种,前者相当于插入,后者相当于删除最后的元素。

由于栈在本质上是一种受限制的表,所以可以使用任何一种表的形式来实现它,我们最常使用的一般有两种:

  1. 链表

  2. 数组

它们在复杂度上的优缺点对比如下:

  1. 新增和删除元素时的时间复杂度

  2. 空间复杂度

结论:

  1. 如果对运行时的效率要求非常高,并且能够在初始化时预知栈的大小,那么应该首选数组形式;否则就应该选用链表形式。

  2. 由于对栈的操作永远都是针对栈顶(top)进行的,因此数组的随机存取的优点就没有了,而且数组必须预先分配空间,空间大小也受到限制,所以一般情况下(对运行时效率的要求不是太高)链表应该是首选。

5.2  代码实现

栈的实现如下:

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   stack.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-6 11:42:17
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __STACK_H__
#define __STACK_H__

#include "../../slist/src/slist.h"

template<typename T>
class CStack : public CSList<T>
{
public:
    int push(T data);
    int pop(T *data = NULL);
    int top(T *data) const;
};

template<typename T>
inline int CStack<T>::push(T data)
{
    return AddTail(data);
}

template<typename T>
inline int CStack<T>::pop(T *data)
{
    if (IsEmpty())
        return 0;

    if (data)
        top(data);

    RemoveTail();
    return 1;
}

template<typename T>
inline int CStack<T>::top(T *data) const
{
    ASSERT(data);

    if (IsEmpty())
        return 0;

    *data = GetTail();
    return 1;
}

#endif  // __STACK_H__

调用如下:

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   stack.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-6 11:42:28
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include "stack.h"
using namespace std;

static void PrintValue(const int nRetCode, const int nValue)
{
    if (nRetCode)
        cout << nValue << endl;
    else
        cout << "Error occured!" << endl;
}

int main()
{
    CStack<int> stack;
    int nValue;
    int nRetCode;

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    stack.push(1);
    stack.push(2);
    stack.push(3);

    nRetCode = stack.top(&nValue);
    PrintValue(nRetCode, nValue);

    nRetCode = stack.pop(&nValue);
    PrintValue(nRetCode, nValue);

    nRetCode = stack.pop(&nValue);
    PrintValue(nRetCode, nValue);

    nRetCode = stack.pop(&nValue);
    PrintValue(nRetCode, nValue);
}

5.3  说明

上面的代码就是在单链表的基础上实现的栈,您会看到,在C++的继承机制下,栈的实现简单得可怕。 :)

一个影响栈的运行效率的问题是错误检测。我的栈实现中是仔细地检查了错误的——对空栈进行top和pop操作,以及当存储空间不够时进行push操作是会引起异常的,显然,我们不愿意出现这种情况,但是,如果把对这些条件的检测放到代码中,那就很可能要花费像实际栈操作那样多的时间。由于这个原因,除非在错误处理极其重要的场合(例如在操作系统中),一般在栈中省去错误检测就成了普通的惯用手法。

但我认为,一个良好的程序首先应该是健壮的,这比效率还要重要,特别是对于栈这种最基本的数据结构,它很可能会被作为基本的元素而被别的地方大量地使用。所以我并没有因为效率的问题而省去了错误检查机制。

引入错误检查机制的代价是:

  1. 对top和pop的操作变得有些繁琐。在代码中我是使用了返回值0或者1来表示成功或者失败,而实际的栈顶元素是通过参数来返回的。这样做必定会有人不满——太麻烦了!但这是我能想到的最好的解决方法,如果你有更好的方法,请告诉我。

  2. 运行时效率会降低。如果确实耗费了太多的时间,你可以把错误检查去掉,但前提条件是你能确保整个运行过程中不会出错——其实还是要有错误检查的,只不过这些错误检查会放在外围来做而已。

好了,就说那么多,下面我们来看看栈的应用。

5.4  应用:中缀到后缀表达式的转换

对栈的应用实在是太广泛了(谁让栈是最基本的数据结构元素之一呢?),例如有平衡符号、表达式转换之类的,我们在这里就选择一个比较有实用价值的例子——中缀到后缀表达式的转换。(可以用在编译器等地方)

5.4.1  代码实现

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   postfix.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-6 16:00:54
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

// 算法:
// 1)检查输入的下一元素。
// 2)假如是个操作数,输出。
// 3)假如是个开括号,将其压栈。
// 4)假如是个运算符,则
//   i) 假如栈为空,将此运算符压栈。
//   ii) 假如栈顶是开括号,将此运算符压栈。
//   iii) 假如此运算符比栈顶运算符优先级高,将此运算符压入栈中。
//   iv) 否则栈顶运算符出栈并输出,重复步骤4。
// 5)假如是个闭括号,栈中运算符逐个出栈并输出,直到遇到开括号。开括号出栈并丢弃。
// 6)假如输入还未完毕,跳转到步骤1。
// 7)假如输入完毕,栈中剩余的所有操作符出栈并输出它们。

#include <stdio.h>
#include "stack.h"

// 返回操作符的优先级
// +和-的优先级是一样的,*和/的优先级也是一样的,但+和-的优先级要比*和/的低。
static int GetPRI(const char optr)
{
    switch (optr)
    {
    case '+': return 1;
    case '-': return 1;
    case '*': return 2;
    case '/': return 2;
    default : return 0;
    }
}

// 在这个函数中完成对栈顶的操作符和当前操作符的优先级对比,
// 并决定是输出当前的操作符还是对当前的操作符进行入栈处理。
static void ProcessStackPRI(
    CStack<char> &stack,
    const char optr,
    char **szPostfix
)
{
    ASSERT(*szPostfix);

    int i;
    int nRetCode;
    char chStackOptr;
    int nCount = stack.GetCount();

    for (i = 0; i <= nCount; ++i)
    {
        nRetCode = stack.top(&chStackOptr);
        if (
            (0 == nRetCode) ||                  // 栈顶为空,新操作符添加到栈顶
            (GetPRI(chStackOptr) < GetPRI(optr))// 栈顶操作符优先级比当前的要低
        )
        {
            stack.push(optr);
            break;
        }
        else
        {
            // 如果栈顶操作符优先级不低于当前的,则栈顶元素出栈并输出:
            stack.pop();
            *(*szPostfix)++ = chStackOptr;
        }
    }
}

static void Infix2Postfix(
    const char *szInfix,
    char *szPostfix
)
{
    ASSERT(szPostfix);

    char chOptr;
    int nRetCode;
    CStack<char> stack;

    while (*szInfix)
    {
        switch (*szInfix)
        {
        // 忽略空格和TAB:
        case ' ':
        case '\t':
            break;

        // 对操作符进行优先级判断,以便决定是入栈还是输出:
        case '+':
        case '-':
        case '*':
        case '/':
            nRetCode = stack.IsEmpty();
            if (!nRetCode)
                ProcessStackPRI(stack, *szInfix, &szPostfix);
            else
                stack.push(*szInfix);   // 当栈为空时,毫无疑问操作符应该入栈
            break;

        // 遇到左括号时,无条件入栈,因为它的优先级是最高的
        case '(':
            stack.push(*szInfix);
            break;

        // 遇到右括号时,逐个把栈中的操作符出栈,直到遇到左括号为止
        case ')':
            do
            {
                nRetCode = stack.pop(&chOptr);
                if (nRetCode && ('(' != chOptr))            // 左括号本身不输出
                    *szPostfix++ = chOptr;
            } while (!stack.IsEmpty() && ('(' != chOptr));  // 遇到左括号为止
            break;

        // 其余的情况,直接输出即可
        default:
            *szPostfix++ = *szInfix;
            break;
        }
        ++szInfix;
    }
    // 如果输入的内容已经分析完毕,那么就把栈中剩余的操作符全部出栈
    while (!stack.IsEmpty())
    {
        nRetCode = stack.pop(&chOptr);
        *szPostfix++ = chOptr;
    }
    *szPostfix = '\0';
}

int main()
{
    char *szInfix = "a+b*c+(d*e+f)*g";
    char szPostfix[255];

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    Infix2Postfix(szInfix, szPostfix);

    printf("Infix   : %s\n", szInfix);
    printf("Postfix : %s\n", szPostfix);
}

5.4.2  说明

源代码里面已经有了详细的注释,我就不再罗嗦了。我只做了+、-、*、/四种操作符的转换,另外,如果括号不匹配,例如有左括号但是没有右括号,或者反过来,程序就可能会运行不正确,但这不是我写这个例子的重点,我写它只是为了掌握栈的用法,如果您有兴趣,可以试着完善它。

下面给出两个例子:

中缀表达式:a + b * c + (d * e + f) * g
后缀表达式:abc*+de*f+g*+

中缀表达式:2 * (x + y) / (1 - x)
后缀表达式:2xy+*1x-/