线性结构 -- 栈

深藏阁楼爱情的钟 2022-08-28 14:53 151阅读 0赞

# 前言 #

栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它们是和线性表不相同的两类重要的抽象数据类型。

# 一 栈的定义和特点 #

## 1.1 栈的定义 ##

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

## 1.2 栈的特点 ##

假设栈 S = (![a\_\{1\},a\_\{2\}, ...,a\_\{n\}][a_1_a_2_ ..._a_n])，则称 a1 为栈底元素，an 为为栈顶元素。栈中元素按 ![a\_\{1\},a\_\{2\}, ...,a\_\{n\}][a_1_a_2_ ..._a_n] 的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图 3.1(a) 所示。因此，栈又称为**后进先出**(Last In First Out，LIFO) 的线性表。

简而言之，栈仍然是线性表，它是线性结构，它的特点是 “**先进后出，后进先出**”。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_11_color_FFFFFF_t_70_g_se_x_16][]

在日常生活中，有很多类似于栈的例子。例如，洗干净的盘子总是逐个往上叠放在已经洗好的盘子上面，而用时是从上往下逐个取用。栈的操作特定正是上述实际应用的抽象。

在程序设计中，如果需要按照保存数据时相反的顺序来使用数据，就可以利用栈来实现。

和线性表类似，栈也有两种存储表示方法，一种是栈的顺序存储结构，称为**顺序栈**；另一种是栈的链式存储结构，称为**链栈**。

# 二 栈的顺序存储表示 — 顺序栈 #

顺序栈是利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置。通常习惯的做法是：以 top = 0 表示空栈，鉴于C语言中数组的下标约定是从 0 开始，则当以C语言作为描述语言时，如此设定会带来很大的不便，因此另设指针 base 指示栈底元素在顺序栈的位置。当 top 和 base 的值相等时，表示空栈。

## 2.0 顺序栈的数据结构定义 ##

//宏定义
    #define STACK_INIT_SIZE  100   //顺序栈存储空间的初始分配量
    #define STACK_INCREMENT  10    //顺序栈存储空间的分配增量
    
    //顺序栈元素类型定义
    typedef int SElemType;
    
    //- - - - - 顺序栈的存储结构 - - - - -
    typedef struct {
        SElemType *base;               // 栈底指针
        SElemType *top;                // 栈顶指针
        int stacksize;                 // 当前已分配的存储空间，以元素为单位
    } SqStack;

【**说明**】

> （1）base 为栈底指针，初始化完成后，**栈底指针 base 始终指向栈底的位置**，若 base == NULL，则表明栈结构不存在。top 为栈顶指针，其初始指向栈底。每当插入新的栈顶元素时，指针 top 增 1；删除栈顶元素时，指针 top 减 1。因此，栈空时，top == base，都指向栈底；栈非空时，**栈顶指针 top 始终指向栈顶元素的上一个位置**。
> 
> （2）stacksize 指示栈可使用的最大容量。

**顺序栈中数据元素和栈指针之间的对应关系**，如下图 3.3 所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16][]

## 2.1 顺序栈的基本操作 ##

### 2.1.0 Status模块 ###

Status.h 模块：预定义了一些常量及类型，以增强C语言的描述功能。

//Status.h 模块：预定义了一些常量及类型，以增强C语言的描述功能。
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    //状态码
    #define TRUE        1   // 真/是
    #define FALSE       0   // 假/否
    #define OK          1   // 通过/成功
    #define ERROR       0   // 错误/失败
    
    //系统中已有此状态码定义，要防止冲突
    #ifndef OVERFLOW
    #define OVERFLOW    -2  //堆栈上溢
    #endif
    
    //系统中已有此状态码定义，要防止冲突
    #ifndef NULL
    #define NULL ((void*)0)
    #endif
    
    //状态码类型
    typedef int Status;
    
    //布尔类型
    typedef int Boolean;

### 2.1.1 顺序栈的初始化 ###

【**算法描述**】C语言实现

/* 顺序栈的初始化
     * 构造一个空栈S。初始化成功则返回OK，否则返回ERROR
    */
    Status InitStack(SqStack *S)
    {
        if(S == NULL)
            return EERROR;
        
        //为顺序栈S动态分配一个初始容量为 STACK_INIT_SIZE 的存储空间
        S->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
        if(!S->base)
            exit(OVERFLOW);              //存储分配失败，退出程序
        S->top = S->base;                //top初始等于base，空栈
        S->stacksize = STACK_INIT_SIZE;  //栈的初始容量置为 STACK_INIT_SIZE
        
        return OK;
    }

### 2.1.2 销毁顺序栈操作 ###

【**算法描述**】C语言实现

/* 销毁顺序栈操作
     * 释放顺序栈所占存储空间
    */
    Status DestroyStack(SqStack *S)
    {
        if(S == NULL)
            return ERROR;
        
        free(S->base);
        S->base = NULL;
        S->top = NULL;
        S->stacksize = 0;
        
        return OK;
    }

### 2.1.3 顺序栈的置空操作 ###

【**算法描述**】C语言实现

/* 顺序栈的置空操作
     * 只是清理顺序栈中存储的数据，不释放顺序栈所占空间
    */
    Status ClearStack(SqStack *S)
    {
        if(S==NULL || S->base==NULL)
            return ERROR;
        
        S->top = S->base;
        
        return OK;
    }

### 2.1.4 顺序栈的判空操作 ###

【**算法描述**】C语言实现

/* 顺序栈的判空操作
     * 判断顺序栈中是否包含有效数据
     * 顺序栈不为空，则返回TRUE；否则返回FALSE
    */
    Status StackIsEmpty(SqStack *S)
    {
        if(S->top == S->base)
    		return TRUE;
    	else
    		return FALSE;
    }

### 2.1.5 计算顺序栈中包含的有效元素的个数 ###

【**算法描述**】C语言实现

// 计算顺序栈中包含的有效元素的个数
    int StackLength(SqStack *S)
    {
        if(S->base == NULL)
            return 0;
        
        return (S->top - S->base);
    }

### 2.1.6 取顺序栈的栈顶元素 ###

【**算法描述**】C语言实现

/* 取顺序栈的栈顶元素
     * 取顺序栈S的栈顶元素，并用参数e接收
     * 成功，返回OK；否则返回ERROR
    */
    Status GetTop(SqStack *S, SElemType *e)
    {
        if(S->base==NULL || S->top==S->base)
            return EERROR;
        
        *e = *(S->top - 1);
        
        return OK;
    }

### 2.1.7 顺序栈的入栈操作 ###

【**算法描述**】C语言实现

/* 顺序栈的入栈操作
     * 插入元素e为新的栈顶元素
    */
    Status Push(SqStack *S, SElemType e)
    {
        if(S==NULL || S->base==NULL)
            return EERROR;
    
        //栈满时，追加存储空间
        if((S->top - S->base) >= S->stacksize)
        {
            S->base = (SElemType*)realloc(S->base, (S->stacksize + STACK_INCREMENT) * sizeof(SElemType));
            if(S->base == NULL)
                exit(OVERFLOW);                 //存储空间分配失败
            S->top = S->base + S->stacksize;    //栈顶指针指向栈顶元素的上一个位置
            S->stacksize += STACK_INCREMENT;
        }
        //先赋值，然后栈顶指针再自增加1
        *(S->top++) = e;
        
        return OK;
    }

### 2.1.8 顺序栈的出栈操作 ###

【**算法描述**】C语言实现

/* 顺序栈的出栈操作
     * 删除栈顶元素，并用参数e接收
    */
    Status Pop(SqStack *S, SElemType *e)
    {
        if(S==NULL || S->base==NULL)  //栈不存在
            return EERROR;
        
        if(S->top == S->base)         //空栈
            return ERROR;
    
        //栈顶指针先自减1，再赋值
        *e = *(--S->top);
        
        return OK;
    }

### 2.1.9 顺序栈的遍历操作 ###

【**算法描述**】C语言实现

/* 顺序栈的遍历操作
     * 从栈底到栈顶依次访问栈中每个元素，并输出元素值
    */
    Status StackTraverse(SqStack *S)
    {
        if(S==NULL || S->base==NULL)  //栈不存在
            return EERROR;
        
        if(S->top == S->base)         //空栈
            return ERROR;
    
        SElemType *p = S->base;       //p为顺序栈S的工作指针，初始指向栈底
        while(p < S->top)
        {
            printf("%d, ", *p);
            p++;
        }
        printf("\n");
        
        return OK;
    }

# 三 栈的链式存储表示 — 链栈 #

链栈是指采用链式存储结构实现的栈。它其实就是一个操作受限的单链表。由于栈的主要操作是在栈顶插入和删除，显然以链表的头部作为栈顶是最方便的，而且没必要像单链表那样为了操作方便附加一个头结点。链栈的存储结构示意图，如下图所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_9_color_FFFFFF_t_70_g_se_x_16][]

## 3.0 链栈的数据结构定义 ##

//链栈元素类型定义
    typedef int SElemType;
    
    //- - - - - 链栈的存储结构 - - - - -
    typedef struct StackNode
    {
    	SElemType          data;  //数据域
    	struct StackNode*  next;  //指针域
    }StackNode, *LinkStack;

## 3.1 链栈的基本操作 ##

### 3.1.0 Status模块 ###

Status.h 模块：预定义了一些常量及类型，以增强C语言的描述功能。

### 3.1.1 链栈的初始化操作 ###

【**算法描述**】C语言实现

/* 链栈的初始化操作
     * 构造一个空栈，栈顶指针置空
    */
    Status InitStack_L(LinkStack S)
    {
        S = NULL;
        return OK;
    }

### 3.1.2 链栈的销毁操作 ###

【**算法描述**】C语言实现

/* 链栈的销毁操作
     * 销毁链栈S，使其不再存在
    */
    Status DestroyStack_L(LinkStack *S)
    {
        LinkStack p, q;
        p = L;             //p初始指向栈顶元素
        while(p)           //p指向栈底结点时，退出循环
        {
            q = p->next;   //q指向待删除栈顶结点的后继结点
            free(p);       //释放栈顶结点空间
            p = q;         //p指向新的栈顶元素
        }
        free(S);
        
        return OK;
    }

### 3.1.3 清空链栈操作 ###

【**算法描述**】C语言实现

/* 清空链栈操作
     * 把链栈的所有结点空间都释放掉
    */
    Status ClearStack_L(LinkStack S)
    {
        if(!S)              //空栈
            return ERROR;
        
        LinkStack p,q;
        p = S;              //p为链栈的工作指针，初始指向栈顶结点
        while(p != NULL)    //p指向栈底结点时，退出循环
        {
            q = p->next;
            free(p);        //释放链栈的每个结点的空间
            p = q;
        }
        
        return OK;
    }

### 3.1.4 链栈判空操作 ###

【**算法描述**】C语言实现

/* 链栈判空操作
     * 判断链栈S是否为空，若为空则返回TRUE，否则返回FALSE
    */
    Status StackIsEmpty_L(LinkStack S)
    {
        if(!S)
            return TRUE;
        else
            return FALSE;
    }

### 3.1.5 计算链栈中的元素个数，即栈的长度 ###

【**算法描述**】C语言实现

/* 计算链栈中的元素个数，即栈的长度
     * 若栈非空，返回栈的元素个数；若栈为空，返回0
    */
    Status StackLength_L(LinkStack S)
    {
        if(!S)
            return 0;
        
        int count = 0;
        LinkStack p = S;     //p为链栈的工作指针，初始指向栈顶结点
        while(p)
        {
            p = p->next;
            count++;
        }
        return count;
    }

### 3.1.6 取栈顶元素操作 ###

【**算法描述**】C语言实现

/* 取栈顶元素操作
     * 返回链栈S的栈顶元素，并用参数e接收
    */
    Status GetTop_L(LinkStack S, SElemType *e)
    {
        if(!S)
            return ERROR;
        
        *e = S->data;      //返回栈顶元素的值，栈顶指针不变
        
        return OK;
    }

### 3.1.7 链栈的入栈操作 ###

【**算法描述**】C语言实现

/* 链栈的入栈操作
     * 在栈顶插入元素e，作为新的栈顶元素
    */
    Status Push_L(LinkStack S, SElemType e)
    {
        if(!S)
            return ERROR;
        
        LinkStack p = (LinkStack)malloc(sizeof(SNode));  //生成一个新结点p
        p->data = e;
        p->next = S;     //将新结点插入到栈顶
        S = p;           //栈顶指针指向新结点，作为新的栈顶元素
        
        return OK;
    }

### 3.1.8 链栈的出栈操作 ###

【**算法描述**】C语言实现

/* 链栈的出栈操作
     * 删除栈顶元素，并用参数e接收其值
    */
    Status Pop_L(LinkStack S, SElemType *e)
    {
        if(!S)
            return ERROR;
        
        LinkStack p;
        p = S;           //p临时保存栈顶元素地址，以备释放
        *e = S->data;    //将栈顶元素赋值给e
        S = S->next;     //修改栈顶指针
        free(p);         //释放原栈顶结点的空间
        
        return OK;
    }

### 3.1.9 链栈的遍历操作（从栈底到栈顶） ###

【**算法描述**】C语言实现

/* 链栈的遍历操作（从栈底到栈顶）
     * 从栈底到栈顶依次访问栈中每个元素，并输出元素值(输入顺序与输出顺序一致)
    */
    Status StackTraverse_L(LinkStack S)
    {
        if(!S)
            return ERROR;
        
        LinkStack p;
        int length = StackLength_L(S);
        for(int i=length; i>0; i--)
        {
            p = S;           //p为链栈的工作指针，初始指向栈顶元素
            int j = 1;       //j为计数器
            while(p && j<i)  //顺时针向后查找，直到p指向第i个元素或p为NULL
            {
                p = p->next;
                j++;
            }
            printf("%d->", p->data);
        }
        printf("\n");
        
        return OK;
    }

### 3.1.10 栈的遍历操作（从栈顶到栈底） ###

【**算法描述**】C语言实现

/* 栈的遍历操作（从栈顶到栈底）
     * 从栈顶到栈底依次访问栈中每个元素，并输出元素值(输入顺序与输出顺序相反)
    */
    Status StackTraverse_Top_L(LinkStack S)
    {
        if(!S)
            return ERROR;
    
        LinkStack p = S;    //p为链栈的工作指针，初始指向栈顶元素
        while(p)
        {
            printf("%d->", p->data);
            p = p->next;
        }
        printf("\n");
        
        return OK;
    }

# 参考 #

《数据结构(C语言版)》严蔚敏，吴伟民 (编著)

《数据结构(C语言版-第2版)》严蔚敏 , 李冬梅 , 吴伟民 (编著)

[第3章 栈和队列 - 栈的顺序存储][3_ _ -]

[《数据结构(C语言版)》- 栈的链式表示][C_-]

[a_1_a_2_ ..._a_n]: https://latex.codecogs.com/gif.latex?a_%7B1%7D%2Ca_%7B2%7D%2C%20...%2Ca_%7Bn%7D
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/73ee86703f2f44d0be03905dc3937aa5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/896aa212fc154812bc000c78cb28ef08.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/dcbe4057a45145c384835f06fa673c9f.png
[3_ _ -]: https://www.cnblogs.com/kangjianwei101/p/5225684.html
[C_-]: https://blog.csdn.net/prlhnxx/article/details/79360035