【C语言数据结构5】--栈的实现

偏执的太偏执、 2022-08-30 11:14 204阅读 0赞

# 栈 #

## 一、什么是栈 ##

栈是一种特殊的线性表，我们可以认为栈是一种阉割版的线性表。它的插入、删除操作只能在**栈顶**进行。因此造就了它后进先出（LIFO）的特征。

在生活中有很多栈的例子，比如平时吃的冰糖葫芦，我们需要先吃掉上面的才能吃下面的（虽然不是这样，但是希望大家配合一下）。又比如我们脱衣服，要把外面的衣服脱了才能脱里面的衣服。

![在这里插入图片描述][20210719145113327.gif_pic_center]

我们可以看一下下面的图片：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tTb2Nr_size_16_color_FFFFFF_t_70_pic_center]

中间部分就是一个栈，而栈最顶端的部分就是栈顶。栈最常用的两个操作就是**进栈**（入栈）和**出栈**操作。这组操作就是插入删除操作，它们只允许在栈顶进行。

进栈操作就是将新数据放入栈顶的上方（逻辑上），然后变成栈的新栈顶。而出栈操作则是将栈顶元素删除，然后让栈顶下方的元素作为栈顶。

## 二、栈的表示 ##

我们可以用顺序存储和链式存储两种结构来实现栈，下面我们分别看看用两种存储结构如何表示一个栈。

### （1）顺序存储结构 ###

这里和顺序表的表示是类似的，但是我们需要设置一个栈顶指针。

#define MAXSIZE 20
    typedef int ElemType;
    typedef struct{ 
        ElemType data[MAXSIZE];		//静态数组，用于存放栈的元素
        int top;				   //栈顶指针
    }SqStack;

在结构体中定义了一个静态数组用于存放栈中的数据，另外还需要定义一个栈顶指针。栈顶指针会一直指向数组中最后一个元素的下标（栈顶元素）。

### （2）链式存储结构 ###

链式存储结构实现的栈和单链表是类似的，结构体如下：

typedef struct SNode{ 
        ElemType data;			//数据域
        struct SNode *next;		//指针域
    }*LinkedStack;

这里就不详细解释了。

因为栈的操作是限制在栈顶的，因此不存在线性表中大量移动数据的问题，因此我们选择用顺序存储结构来实现栈的各个操作。

## 三、栈的实现 ##

### （1）栈的初始化 ###

顺序存储我们同样可以使用两种方式来实现，一种是通过静态数组的方式，另一种是通过malloc函数动态申请内存的方式。

对于前者我们的初始化只需要初始化栈顶，对于后者我们还需要使用malloc分配内存。两种差别不大，这里我们选择用前者实现。

/** * 用于初始化栈S */
    int InitSqStack(SqStack *S){ 
        //将栈顶指向-1
        S->top = -1;
        return 1;
    }

在前面我们说过，栈顶指针会一直指向栈顶元素的下标。这里之所以不设置为0是因为，如果栈顶为0，那就表示栈中又一个元素。因此初始化时我们设置为-1。

### （2）入栈 ###

入栈的图示如下：

![在这里插入图片描述][20210719161800510.png_pic_center]

入栈操作我们需要判断栈是否满了，如果满了则返回0，如果没满则需要移动栈顶指针，再将元素入栈。

int Push(SqStack *S, ElemType elem){ 
        //如果栈满了，则top == MAXSIZE-1，此时不进行入栈操作，返回0
        if(S->top == MAXSIZE-1){ 
            return 0;
        } 
        //移动栈顶指针
        S->top++;
        //将入栈元素放置在栈顶
        S->data[S->top] = elem;
        return 1;
    }

我们还可以将移动指针和元素放入栈顶的操作合并成一句：

//先进行++S->top移动指针，再将元素赋值到新top的位置
    S->data[++S->top] = elem;

不过鉴于可读性差了许多。作者认为，在代码不会影响执行效率的情况下，还是不要为了追求代码简短而放弃可读性。

### （3）出栈 ###

出栈操作和入栈操作是相反的。图示如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tTb2Nr_size_16_color_FFFFFF_t_70_pic_center 1]

我们先判断是否栈空，如果栈中有数据，则先获取数据，再移动栈顶指针。

int Pop(SqStack *S, ElemType *elem){ 
        //如果栈为空，则top==-1，此时不进行出栈操作
        if(S->top == -1){ 
            return 0;
        }
        //获取栈顶元素
        *elem = S->data[S->top];
        //移动栈顶指针
        S->top--;
        return 1;
    }

因为我们要获取出栈的数据，因此这里传入的elem是一个指针。

### （4）清空栈 ###

清空栈的操作我们只需要完成逻辑上的清空即可，即将栈的top赋值为-1，代码如下：

void ClearStack(SqStack *S){ 
        //将栈顶指向-1
        S->top = -1;
    }

### （5）栈判空 ###

栈判空我们只需要判断top是否指向-1即可：

int EmptyStack(SqStack S){ 
      	//如果S.top==-1则返回1，如果S.top!=-1则返回0
        return S.top == -1 ? 1 : 0;
    }

上面使用了三元运算符，我们可以把上面的代码翻译成如下：

int EmptyStack(SqStack S){ 
        if(S.top == -1){ 
            return 1;
        }else{ 
            return 0;
        }
    }

### （6）获取栈顶元素 ###

除了出栈，我们还可以提供一个获取栈顶元素的操作。它和出栈的区别就是它不会移动栈顶指针（不会删除栈中元素），因此它的操作要比出栈简单：

int GetTop(SqStack S, ElemType *elem){ 
        if(S.top == -1){ 
            return 0;
        }
        *elem = S.data[S.top];
        return 1;
    }

除了上面的操作，我们还可以实现很多其它操作。这里就不再细说了。

## 四、栈的应用 ##

栈有很多应用，可能刚开始接触栈会觉得这种结构非常多余。但是其实操作系统很多功能都是基于栈这种结构的，像是数值运算，程序递归，括号匹配等都可以用栈来实现。下面我们来实现几个简单的例子。

### （1）逆序输出 ###

现在我们要求实现输入一个序列，然后按照与这个序列输入相反的顺序输出。

这里我们利用栈先进后出的特性。我们将序列的数据依次入栈，再依次出栈输出即可达到逆序输出效果，代码如下：

void ReversePrint(int n){ 
        ElemType temp;
        SqStack S;
        InitSqStack(&S);
        //将输入元素依次入栈
        for(int i = 0; i < n; ++i){ 
            scanf("%d", &temp);
            Push(&S, temp);
        }
        //将元素出栈并输出
        for(int i = 0; i < n; ++i){ 
            Pop(&S, &temp);
            printf("%d\t", temp);
        }
    }

### （2）进制转换 ###

在进制转换中，栈同样扮演者逆序输出的作用。

将10进制数N转换成d进制数的原理如下：  
 N 1 = N / d s 1 = N 1 % d N 2 = N 1 / d s 2 = N 2 % d . . . N n = N n − 1 / d s n = N n % d N\_1 = N/d \\\\ s\_1 = N\_1\\%d \\\\ N\_2 = N\_1/d \\\\ s\_2 = N\_2\\%d \\\\...\\\\ N\_n = N\_\{n-1\}/d \\\\ s\_n = N\_n \\%d N1=N/ds1=N1%dN2=N1/ds2=N2%d...Nn=Nn−1/dsn=Nn%d  
其中%为取模操作。我们先对十进制数进行除操作，然后将除的结果取模。最终N的d进制数为：  
 s n s n − 1 . . . s 1 s\_ns\_\{n-1\}...s\_1 snsn−1...s1  
我们实际操作一下，这里N取1348，d取8：

最后得出10进制数1348的8进制为2504。下面我们用代码来实现一下：

void conversion(){ 
        int n;
        //用于获取出栈元素
        ElemType e;
        SqStack S;
        InitSqStack(&S);
        scanf("%d", &n);
        while (n){ 
            //把式中s放入栈
            Push(&S, n % 8);
            n = n / 8;
        }
        while (!EmptyStack(S)){ 
      	    //逆序输出
            Pop(&S, &e);
            printf("%d\t", e);
        }
    }

### （3）括号匹配 ###

括号匹配的大致步骤如下：

1.  依次判断字符串内容
2.  如果是左括号则直接入栈
3.  如果是右括号则匹配栈顶是否是对应的右括号
4.  如果匹配成功则入栈继续匹配，如果匹配失败则返回0
5.  遍历完字符后，如果栈为空，则匹配成功。如果栈非空，则匹配失败

我们可以用几个例子模拟一下：

([)]
    ()()()
    ([][]{ })
    ([][]{ }))

这里就不详细分析了，下面是具体代码：

int match(char str[], int len){ 
        ElemType elem;
        SqStack S;
        InitSqStack(&S);
        for(int i = 0; i < len; i++){ 
            //如果是左括号则直接入栈
            if(str[i] == '(' || str[i] == '[' || str[i] == '{'){ 
                Push(&S, str[i]);
            //如果是右括号，则进行匹配
            }else if(str[i] == ')'){ 
                //匹配成功则出栈
                if(GetTop(S, &elem) && elem == '('){ 
                    Pop(&S, &elem);
                }else{ 
                    return 0;
                }
            }else if(str[i] == ']'){ 
                if(GetTop(S, &elem) && elem == '['){ 
                    Pop(&S, &elem);
                }else{ 
                    return 0;
                }
            }else if(str[i] == '}'){ 
                if(GetTop(S, &elem) && elem == '{'){ 
                    Pop(&S, &elem);
                }else{ 
                    return 0;
                }
            }
        }
        if(EmptyStack(S)){ 
            return 1;
        }else{ 
            return 0;
        }
    }

另外大家可以用栈实现一些其它算法。

[20210719145113327.gif_pic_center]: /images/20220829/f0ec1956064444468ffee32da6706ef2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tTb2Nr_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/7bf77393eaf84cfba1c0013030e51e85.png
[20210719161800510.png_pic_center]: /images/20220829/81772a3db3f743c391ae35ca33180735.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tTb2Nr_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220829/29645fd83497474f9f61be9f9be8e9ba.png