[栈](1)栈

19
[ 数据结构 ] [ 栈和队列 ]

栈和队列是两种重要的线性结构，从数据结构角度看，栈和队列也是线性表，其特性在于栈和队列的基本操作是线性表操作的子集，他们是操作受限的线性表

因此，可称为限定性数据结构，但从数据类型角度看，它们是和线性表大不相同的两类重要的抽象数据类型，由于它们广泛应用在各种软件系统中

因此在面向对象的程序设计中，它们是多型数据类型。

栈(Stack) 是限定仅在表尾进行插入或删除操作的线性表，因此，对栈来说，表尾端有其特殊含义，称栈顶(top)，相应的，表头段称为栈底(bottom)。不含元素的空表称为空栈

假设栈S=(a1,a2,...,an)，则称a1为栈底元素，an为栈顶元素，栈中元素按a1，a2

....an的次序进栈，退栈的第一个元素应为栈顶元素，换句话说，栈的修改是按后进先出(last in first out)的原则进行的，如下图所示

img

上述图可解释栈的特点

栈的基本操作除了在栈顶进行插入或删除外，还有栈的初始化、判空及取栈顶元素等，下面给出栈的抽象数据定义

ADT Stack
{
    数据对象：D = {a1 | a1属于ElemSet，i = 1,2,...,n,n >= 0}
    数据关系：R1 = {<a(i - 1)>, | a(i - 1),ai属于D，i = 2,...,n}
    约定an端为栈顶，a1端为栈底

    基本操作：
          InitStack(&S)
    操作结果：构造一个空栈S

          DesstroyStack(&S)
    初始条件：栈S已存在
    操作结果：栈S被销毁

          ClearEmpty(S)
    初始条件：栈S已存在
    操作结果：将S清为空栈

          StackEmpty(S)
    初始条件：栈S已存在
    操作结果：若栈S为空栈，则返回TRUE，否则FALSE

          StackLength(S)
    初始条件：栈S已存在
    操作结果：返回S的元素个数，即栈的长度

          GetTop(S,&e)
    初始条件：栈S已存在且非空
    操作结果：用e返回栈顶元素

          Push(&S,e)
    初始条件：栈S已存在且非空
    操作结果：插入元素e为新的栈顶元素

          Pop(&S,&e)
    初始条件：栈S已存在且非空
    操作结果：删除S的栈顶元素，并用e返回其值

         StackTraverse(S,visit())
    初始条件：栈S已存在且非空
    操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit(),一旦visit()失败
              则操作失败


}ADT Stack

上述为栈的基本操作，上述算法将在下面的笔记中完善

栈的表示和实现

和线性表类似，栈也有两种存储表示方法

顺序栈，即栈的顺序储存结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，通常的习惯做法是以top=0表示空栈

但是C语言中下标约定从0开始，而且在栈的使用中，栈的空间大小很难估计，因此，一般来说，在初始化设空栈时不应限定栈的最大容量。

合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大，为此可设定两个全局常量：

  • STACK_INIT_SIZE(存储空间初始化分配量)
  • STACKINCREMENT(存储空间分配增量)

以下述说明作为顺序栈的定义：

typedef struct
{
    SElemType* bese;//栈底指针
    SElemType* top;//栈顶指针
    int stacksize;//当前分配量
}SqStack;

其中，bese作为栈底指针，一直指向栈底的元素， top作为栈顶指针，一直指向栈顶元素的上一片内存。

在顺序栈中，它始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在，称top为栈顶指针，其初值指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减一。

因此，非空中栈顶指针始终在栈顶元素的下一个位置上，如下图所示

img

以下为栈的模块说明：

typedef int Status;

#define STACK_INIT_SIZE 100
#define STACKINCREMENNT 10

typedef struct
{
    SElemType* bese;//栈底指针
    SElemType* top;//栈顶指针
    int stacksize;//当前分配量
}SqStack;

/*========基本函数操作说明========*/

Status InitSack(SqStack& S);
//构造一个空栈S

Status DestroyStack(SqStack& S);
//销毁栈S，S不存在

Status ClearStack(SqStack& S);
//把S重置为空栈

Status StackEmpty(SqStack S);
//判空，若S为空栈，则返回TRUE,否则FALSE

int StackLength(SqStack S);
//返回S的元素个数，即栈的长度

Status GetTop(SqStack S, SElemType& e);
//若栈不为空，用e返回栈顶元素，并返回OK，否则返回ERROR

Status Push(SqStack& S, SelemType e);
//插入元素e为新的栈顶元素

Status Pop(SqStack& S, SElemType& e);
//若栈不为空，则删除S的栈顶元素，用e返回其值，并且返回OK，否则返回ERRO

Status StackTraverse(SqStack S, Status(*visit)());
//从栈底到栈顶依次对栈中每个元素调用函数visit(),一旦visit()失败，则操作失败

下面来看看栈操作的基本算法：

构造一个空栈：

Status InitStack(SqStack* S)
{
    S->base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));
    if (S->base == NULL)
    {
        exit(0);
    }
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return 0;
}

用e返回栈顶元素

Status GetStack(SqStack S, int* e)
{
    if (S.base == S.top)
    {
        exit(0);
    }
    *e = *(S.top - 1);

    return 0;
}

插入元素e为新的栈顶元素

Status Push(SqStack* S, int e)
{
    if ((S->top - S->base) >= S->stacksize)//栈满，追加空间
    {
        S->base = (int*)malloc((S->stacksize + STACKINCREMENT) * sizeof(int));
        //重新分配新的空间

        if (S->base == NULL)
        {
            exit(0);
        }
        S->top = S->base + S->stacksize;//将top指向栈顶
        S->stacksize += STACKINCREMENT;
    }
    *S->top = e;
    S->top++;

    return 0;
}

删除栈顶元素，并用e返回

Status Pop(SqStack* S, int* e)
{
    if (S->base == S->top)
    {
        return 1;
    }
    S->top--;
    *e = *S->top;
    S->top == NULL;

    return 0;
}

上述式顺序栈的基本操作

那么除了顺序存储结构以外，还有链式存储结构的栈，不管那种结构，我们只需要记住一点：栈先进后出！

所以它的添加和删除都在尾端

栈的应用举例

由于栈结构具有后进先出的固有特性，使得栈称为程序设计中有用的工具。我们来看下面这个例子

进制转换

假设现要编制一个满足下列要求的程序：对输入任意一个非负十进制的整数，打印输出与其等值的八进制数，由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相仿，因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序打印输出的即为与输入对应的进制数

完整算法如下：

void conversion(SqStack *S)
{
    InitStack(S);
    int N;
    scanf("%d",&N);
    while (N)
    {
        Push(S, N % 8);
        N = N / 8;
    }
    while (S->top != S->base)
    {
        int e;
        Pop(S, &e);
        printf("%d", e);
    }
}

这是利用栈的后进先出的特性的最简单的例子，在这个例子中，栈操作的序列是直线式的，即先一味的入栈，然后一味的出栈。

行编辑程序

一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区，由于用户在终端上进行输入时，不能保证不出差错

因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。

较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，允许用户输入出差错，并在发现有误时可以及时更正，例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符“#”，以表示前一个字符无效。

如果发现当键入行内差错较多或难以补救，则可以键入一个退行符“@”，以表示当前行中的字符均无效，例如，假设从终端接受了以下两行字符：

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

则实际有效的如下所示：

  • while(*s)
  • putchar(*s++);

为此，可设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符之后先作如下判别：

  • 如果它既不是退格符也不是退行符，则将该字符压入栈顶
  • 如果是一个退格符，则栈顶删去一个字符
  • 如果它是一个退行符，则将字符栈清为空栈。

算法如下所示

void LineEdit(SqStack* S)
{
    char ch, c;
    InitStack(S);//构造空栈S
    ch = getchar();//从终端接受第一个字符
    while (ch != EOF)//EOF为全文结束
    {
        while (ch != EOF && ch != '\n')//为行结束
        {
            switch (ch)
            {
            case'#'://退格
                Pop(S, &c);
                break;
            case'@'://退行
                ClearStack(S);
                break;
            default://压入栈顶
                Push(S, ch);
                break;
            }
            ch = getchar();
        }
        /*用于判断*/
        while (S->top != S->base)
        {
            char c;
            Pop(S, &c);
            printf("%c", c);
        }
        
        ClearStack(&S);
        if (ch != EOF);
        {
            ch = getchar();
        }
    }
}
/*上述算法用到的清空功能*/
Status ClearStack(SqStack *S)
{
    if (S->top == S->base)
    {
        printf("未存在数据\n");
        return -1;
    }
    while (S->top > S->base)
    {
        S->top--;
        S->top == NULL;
    }
    return 0;
}

迷宫求解（经典问题）

求迷宫中从入口到出口的所有路径是一个经典的程序设计问题，由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口除法，顺某一方向向前探索，若能走通，则继续向前探索，直至所有可能的通路都探索到为止。

为了保证在任何位置上都能沿原路退回，则就需要用到“后进先出”的栈。

在此需要说明一点的是，所谓当前位置可通，指的是未曾走到过的痛到快，即要求该方块位置不仅是通道块，而且既不在当前路径上，也不是曾经纳入过路径的通道块

详细操作看补充笔记。

表达式求值(经典问题 )

表达式求值是程序设计语言编译中的一个最基本问题，它的实现是栈应用的又一个典型例子，这里引用一种简单直观、广为使用的算法，通常称为“算符优先法”

要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式，首先要了解算术四则运算的规则，例如：

4+2*3-10/5

  • 先乘除，后加减
  • 从左算到右
  • 先括号内，后括号外

由此，上述表达式的顺序为：

4+2*3-10/5=4+6-10/5=10-2=8

具体请看补充笔记。

栈与递归的实现

栈还有一个重要应用实在程序设计语言中实现机电柜，一个直接调用自己或通过一系列的调用语句间接的调用自己的函数，称作递归函数。

递归是程序中一个强有力的工具，很多数学函数是递归定义的，比如大家熟悉的阶乘函数和斐波数列(Fibonacci数列)。

有的数据结构，如二叉树，广义表等，由于结构本身固有的递归特性，则它们的操作可递归的描述。

还有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单，如：八皇后问题，Hanoi塔问题等。

Hanoi塔问题

假设有3个分别命名为X、Y和Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1、2....，n的圆盘，现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循以下规则

  • 每次只能移动一个圆盘
  • 圆盘可以插在X、Y和Z的任一塔座上
  • 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上

如何实现移动圆盘的操作呢？当n为1的时候，只需要将编号为1的圆盘从塔座X直接移到塔座Z即可

当n>1时，需利用塔座Y作辅助塔座，若能设法将压在编号为n的圆盘之上的n-1个圆盘从塔座X(依照上述法则)移至塔座Y上，即可先将编号为n的圆盘从塔座X移至塔座Z上，然后再将塔座Y上的n-1个圆盘(依照上述法则)移至塔座Z上

而如何将n-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小1，因此可以用同样的方法求解，由此可得算法如下：

void hanoi(int n, char x, char y, char z)
/*将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘按规则搬到
塔座z上，y可用作辅助塔座
搬动操作move(x,n,z)可定义为(c是初值0的全局变量，对搬动计数)
printf("%i.Move disk %i from %c to %c\n",++c,n,x,z)
*/
{
    if (n == 1)
    {
        move(x, 1, z);//将编号为1的圆盘从x移到z
    }
    else
    {
        hanoi(n - 1, x, z, y);//将x上编号为1至n-1的圆盘移到y，z作辅助塔
        move(x, n, z);//将编号为n的圆盘从x移到z
        hanoi(n - 1, y, x, z);//将y上编号为1至n-1的圆盘移到z，x作辅助塔
    }
}

具体请看补充笔记

本文链接：

https://nullcode.fun/18.html
1 + 9 =
快来做第一个评论的人吧~