栈的实现

基本概念

栈（Stack）是计算机科学中的一种抽象数据类型，是限定仅在表尾进行插入或者删除操作的线性表。对栈来说，表尾端称为栈顶（top），表头端称之为栈底（bottom）。在栈顶插入数据叫做入栈（push）,删除数据叫做出栈（pop）。其按照后进先出（LIFO， Last In First Out）的原理运作。栈的应用十分广泛，比如浏览器页面的回退，括号的匹配和进制的转化。
顺序栈，即栈的顺序存储结构，利用一组连续的存储单元存放自栈顶到栈底的数据元素，同时，附加指针top指示栈顶元素在栈中的位置，通常的习惯是以top=0表示空栈。典型的顺序栈示意图如下所示：

顺序栈

栈的表示和实现

按照栈的结构特点和原理，一个栈可以用以下C语言结构体表示

typedef struct
{
    int *base; //栈底
    int *top; //栈顶
    int stacksize; //当前已分配得存储空间
}sqStack;

栈的接口定义

栈的操作包括初始化，入栈，出栈和清空栈，销毁栈，具体定义如下代码所示：

#pragma once
#ifndef STACK_H
#define STACK_H
#define bool int
#define true 1
#define false 0
#define STACK_INIT_SIZE 100 //初始存储空间大小
typedef struct 
{
    int *base; //栈底
    int *top; //栈顶
    int stacksize; //当前已分配的存储空间
}sqStack;

sqStack initStack(); //站的初始化
void destoryStack(sqStack stack); //销毁栈
sqStack clearStack(sqStack stack); //清空栈
bool emptyStack(sqStack stack); //判断是否为空栈
int getSize(sqStack stack); //返回当前栈的长度
sqStack pushStack(sqStack stack, int data); //元素入栈
sqStack popStack(sqStack stack); //元素出栈
void stackTraverse(sqStack stack); //遍历栈中元素
#endif // !STACK_H

栈的接口实现

• 初始化
  栈的初始化需要对栈底进行内存分配，并将栈顶指向栈底，并设置栈的初始空间，具体实现如下代码所示

sqStack initStack()
{
     sqStack stack;
    stack.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));
    if (!stack.base)
    {
        printf("分配失败！");
        exit(0);
    }
    stack.top = stack.base;
    stack.stacksize = STACK_INIT_SIZE;
    return stack;

}

• 入栈
  栈的操作遵循后进先出的原则，所以需要将入栈元素赋值给栈顶之后，栈顶也要增加一个单元，用以下动态图可以清楚地表示入栈操作，如下所示：

  
  入栈操作
  

  根据以上原理，实现代码如下所示

//元素入栈
sqStack pushStack(sqStack stack, int data) //元素入栈
{
    if (stack.top - stack.base >= stack.stacksize)//栈满，增加存储空间
    {
        stack.base = (int*)realloc(stack.base, stack.stacksize * 2 * sizeof(int));
        
        if (!stack.base)
        {
            printf("存储空间分配失败！");
            exit(0);
        }
        stack.top = stack.stacksize + stack.base;
        stack.stacksize = stack.stacksize * 2;
    }
    stack.top++;
    *stack.top = data;
    
    return stack;
    
}

由以上代码所示，进行入栈操作时，需要判断是否有足够的内存空间，当栈顶指针减去栈底指针的大小大于栈分配得空间时，需要进行扩容，每次扩充的容量是原来的2倍。

• 出栈
  出栈遵循后入先出的原则，所以每次只要将栈顶元素取出来，并将栈顶指针减一即可，具体过程可由以下动态图表示：

  
  元素出栈

根据以上过程，实现代码如下所示：

sqStack popStack(sqStack stack)
{
    if (emptyStack(stack))
    {
        
        printf("空栈！");
        exit(0);
    }
    int data = 0;
    data = *stack.top;
    stack.top--;
    return stack;
}

• 遍历栈中元素
  遍历栈中元素，需要将栈中的每一个元素都打印出来，，每次都需要将栈顶指针减少一个单元，当栈顶指针和栈底指针相等时，其循环的终止。具体实现代码如下所示：

void stackTraverse(sqStack stack)
{
    while (stack.top != stack.base)
    {
        printf("%d", *stack.top);
        stack.top--;
        
    }
}

• 返回栈的长度
  返回栈的长度的实现过程基本与遍历栈中元素的实现过程基本一样，具体如以下代码所示;

int getSize(sqStack stack)
{
    int length = 0;
    while (stack.top != stack.base)
    {
        length++;
        stack.top--;
    }
    return length;
}

• 判断空栈
  有遍历栈中元素的代码可知，当栈顶指针和栈底指针相等时，循环终止，说明此是栈已变成空栈，具体实现代码如下所示：

bool emptyStack(sqStack stack)
{
    if (stack.top == stack.base)
    {
        return true;
    }
    else
    {
        return false;
    }
}

• 清空栈
  栈的清空，只需将栈的栈顶指针指向栈的栈底指针即可，具体实现代码如下所示：

sqStack clearStack(sqStack stack)
{
    stack.top = stack.base;
    return stack;
    
}

• 销毁栈
  由栈的初始化可知，栈的初始化主要包括对栈底指针进行内存的分配，栈的销毁只需释放掉栈底指针，并将栈顶指针和栈底指针置空即可，具体实现如下代码所示：

void destoryStack(sqStack stack)
{
    free(stack.base);
    stack.top = NULL;
    stack.base = NULL;
    stack.stacksize = 0;
}

教材：数据结构（C语言版）清华大学出版社
辅助学习网站：https://visualgo.net