数据结构系列学习（六） - 顺序栈（Stack）

目录

引言：

学习：

初始状态：

入栈状态： 

代码实现：

头文件（SqStack.h）：

设置顺序栈的初始大小：

设置顺序栈中元素的范型：

结构体的设计：

所有函数的声明：

源文件（SqStack）对函数功能的具体实现：

初始化函数（Init_Stack）：

入栈函数（Push）：

出栈函数（Pop）：

获取栈顶元素函数（Top）：

判空函数（IsEmpty）：

判满函数（IsFull）： 

查找函数（Search）：

扩容函数（Inc）：

清空函数（Clear）：

销毁函数（Destroy）：

打印函数（Show）：

获取有效长度函数（Get_Length）：

测试：

测试初始化函数、打印函数：

测试入栈函数、扩容函数：

测试出栈函数：

测试清空函数：

测试销毁函数： 

 测试获取有效长度函数：

总结：

---

引言：

数据结构学习目录：

数据结构系列学习(一) - An Introduction to Data Structure

数据结构系列学习（二） - 顺序表（Contiguous_List） 

数据结构系列学习（三） - 单链表(Linked_List) 

数据结构系列学习（四） - 单向循环链表(Circular Linked List) 

数据结构系列学习（五） - 双向链表（Double_Linked_List） 

在上一篇文章中，我们对双向链表进行了学习并使用代码对它进行了实现， 这篇文章中，我们来对一种经典的数据结构——栈，进行了解和学习，并使用代码对它进行实现。

学习：

在严蔚敏《数据结构（C语言版）》中对栈是这样定义的：

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

栈是一种特殊的线性表，数据只能从一端进入，从一端出。就跟我们往一个量筒里面倒水一样，如果把水想象成一层一层的样子，那么首先进入量筒的那一层水就在量筒的底部，也就是栈底，最后进入量筒的那一层水就在量筒的头部，也就是栈顶。

比如说我们现在有一组数据，我们要将这五个数据从大到小依次进行入栈操作：

初始状态：

入栈状态： 

栈（stack）是限定尽在表尾进行插入和删除操作的线性表。

其实这玩意儿也没啥难的，说白了，它就是阉割版的顺序表。

代码实现：

顺序栈中我们需要实现的功能（12个）：

初始化函数(Init_Stack)；

入栈函数(Push)；

出栈函数(Pop)；

获取栈顶元素值(Top)；

判满函数(IsFull)；

判空函数(IsEmpty)；

查找函数(Search)；

扩容函数(Inc)；

清空函数(Clear)；

销毁函数(Destroy)；

打印函数(Show)；

获取有效长度函数(Get_Length)；

头文件（SqStack.h）：

设置顺序栈的初始大小：

#define LIST_INIT_SIZE 10//初始大小

设置顺序栈中元素的范型：

typedef int ELEM_TYPE;

结构体的设计：

typedef struct Stack
{
    ELEM_TYPE * base;//存储空间基址（用来接收malloc返回在堆上申请的连续空间块开始地址）
    int top;//当前有效长度，且还可以表示下一个待插入位置的下标
    int listsize;//当前总空间大小
}Stack,*PStack;

所有函数的声明：

//初始化
void Init_Stack(PStack st);
//入栈(队尾插入)
bool Push(PStack st,ELEM_TYPE val);
//出栈（队尾删除））
bool Pop(PStack st);
//获取栈顶元素值
ELEM_TYPE Top(PStack st);
//判空
bool IsEmpty(PStack st);
//判满
bool IsFull(PStack st);
//搜索
int Search(PStack st,ELEM_TYPE val);
//扩容
void Inc(PStack st);
//清空
void Clear(PStack st);
//销毁
void Destroy(PStack st);
//打印
void Show(PStack st);
//获取有效值个数
int Get_length(PStack st);

源文件（SqStack）对函数功能的具体实现：

初始化函数（Init_Stack）：

我们将栈中的base设置为在堆区申请的初始大小个栈结构体的大小，然后再将代表栈中元素个数的top赋值为0，然后将初始的栈大小设置为我们最开始定义的宏替换。

void Init_Stack(PStack st)
{
    assert(st != nullptr);
    st->base = (ELEM_TYPE*) malloc(LIST_INIT_SIZE * sizeof(Stack));
    st->top = 0;
    st->listsize = LIST_INIT_SIZE;
}

入栈函数（Push）：

入栈首先要对栈进行判满，如果栈满了的话我们就进行扩容，然后我们将要入栈的元素赋值给堆区上base组的top下标位置，然后我们再将top进行加1操作。

bool Push(PStack st,ELEM_TYPE val)
{
    assert(st != nullptr);
    if(IsFull(st)){
        Inc(st);
    }
    st->base[st->top] = val;
    st->top++;
    return true;
}

出栈函数（Pop）：

当我们进行出栈操作是，首先要做的就是对栈进行判空，如果栈为空，则直接返回为假，如果不为空我们就直接将栈中元素的个数减1即可。

bool Pop(PStack st)
{
    assert(st != nullptr);
    if(IsEmpty(st)){
        return false;
    }
    st->top--;
    return true;
}

获取栈顶元素函数（Top）：

这里我们直接返回范型类型的base组top-1下标的元素即可（与数组类似）。

ELEM_TYPE Top(PStack st)
{
    assert(st != nullptr);
    return st->base[st->top-1];
}

判空函数（IsEmpty）：

当栈中的元素个数为0时，栈就为空。

bool IsEmpty(PStack st)
{
    assert(st != nullptr);
    return st->top == 0;
}

判满函数（IsFull）： 

当栈中的元素个数等于栈的空间大小的时候，则判定为栈满。

bool IsFull(PStack st)
{
    assert(st != nullptr);
    return st->top == st->listsize;
}

查找函数（Search）：

类似于顺序查找，定义i下标对栈中的元素进行遍历，当我们要查找的值等于base组的i号下标所对应的元素时，则返回此元素的下标，如果没有找到，则返回-1 。

int Search(PStack st,ELEM_TYPE val)
{
    assert(st != nullptr);
    for(int i = 0;i < st->top;i++){
        if(val == st->base[i]){
            return i;
        }
    }
    return -1;
}

扩容函数（Inc）：

使用realloc函数对原先在堆区申请的base空间组进行二倍扩容，然后将栈的空间大小（listsize）扩大为原来的两倍。

void Inc(PStack st)
{
    assert(st != nullptr);
    st->base = (ELEM_TYPE*) realloc(st->base,(st->listsize * sizeof(ELEM_TYPE)) * 2);
    assert(st->base != nullptr);
    st->listsize *= 2;
}

清空函数（Clear）：

我们将栈里面的元素个数（top）直接赋值为0，这样就清空了栈中所有的元素。

void Clear(PStack st)
{
    assert(st != nullptr);
    st->top = 0;
}

销毁函数（Destroy）：

我们直接将原先通过malloc函数在堆区上申请到的空间释放掉，然后将栈中的元素个数（top）赋值为0，再将栈的空间大小（listsize）赋值为0即可。

void Destroy(PStack st)
{
    assert(st != nullptr);
    free(st->base);
    st->top = 0;
    st->listsize = 0;
}

打印函数（Show）：

定义循环，循环条件为i < top，将栈中的元素全部进行打印，顺便也将栈中的元素个数（top）、栈的总空间大小（listsize）打印出来。

void Show(PStack st)
{
    assert(st != nullptr);
    for(int i = 0;i < st->top;i++){
        printf("%3d",st->base[i]);
    }
    printf("\n");
    printf("栈中的元素个数top为：%d\n",st->top);
    printf("栈目前的总大小listsize为：%d\n",st->listsize);
}

获取有效长度函数（Get_Length）：

定义count整形值用来记录有效值的个数，定义循环，循环每执行一次count就加1，将函数的返回值设置为count。

int Get_length(PStack st)
{
    assert(st != nullptr);
    int count = 0;
    for(int i = 0;i < st->top;i++){
        count++;
    }
    return count;
}

测试：

测试初始化函数、打印函数：

#include
#include
#include
#include "SqStack.h"
int main()
{
    Stack stack;
    Init_Stack(&stack);
    for(int i = 0;i < 100;i++){
        Push(&stack,i + 1);
    }
    printf("在栈上的原始数据为：\n");
    Show(&stack);
/*
    此处添加其他测试功能代码...
*/
    return 0;
}

运行结果：

测试入栈函数、扩容函数：

    Push(&stack,11);
    Show(&stack);

 运行结果：

如图，当栈的空间满了之后，扩容函数将总大小从原来的10个范型扩大到了20个，也就是原来的两倍。

测试出栈函数：

    printf("经过出栈操作之后：\n");
    Pop(&stack);
    Show(&stack);

运行结果：

测试清空函数：

    printf("\n经过清空操作之后：\n");
    Clear(&stack);
    Show(&stack);

运行结果：

测试销毁函数： 

    printf("经过销毁操作之后：\n");
    Destroy(&stack);
    Show(&stack);

运行结果：

 测试获取有效长度函数：

总结：

顺序栈相对来说比较简单，其实也就是阉割版的顺序表，因为栈这种数据结构秉承的原则就是先进后出，所以我们对入栈操作就是顺序表中的尾插操作，我们的出栈操作就是顺序表中的尾删操作。只需要将顺序表中的结构体定义进行修改，然后对其他函数做相应的小改动即可，总体难度偏低。