【数据结构】线性数据结构-顺序栈

栈（Stack）是一种基本的数据结构，具有以下特点：
后进先出（LIFO, Last In First Out）：栈内的数据项遵循后进先出的原则，即最后存入的项最先被取出。
操作限制：栈通常只允许在一端进行插入和删除操作，这一端称为栈顶（Top），相对的另一端称为栈底（Bottom）。
应用场景：栈常用于解决函数调用、表达式求值、括号匹配等问题。
栈可以通过多种方式实现，常见的有基于数组的实现和基于链表的实现。无论哪种实现方式，都需要支持基本的栈操作如 push（入栈）、pop（出栈）、peek（查看栈顶元素）等。

①SqStack.h

#pragma once//预处理指令，防止头文件被重复包含
typedef int ElemType;
typedef struct {
	ElemType* elem;     // 存储空间的基址
	int top;    // 栈顶元素的下一个位置，简称栈顶位标
	int size;    // 当前分配的存储容量
	int increment;    // 扩容时，增加的存储容量
} SqStack;         // 顺序栈

#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define TRUE 2
#define FALSE -2

#define MAXSIZE 20
#define INCREMENT 5

typedef int Status;

Status InitStack_Sq(SqStack& S, int size, int inc);//初始化空顺序栈S
Status StackEmpty_Sq(SqStack S);//判断栈是否为空
Status Push_Sq(SqStack& S, ElemType e);//入栈操作
Status Pop_Sq(SqStack& S, ElemType& e);//出栈操作

②SqStack.cpp

实现栈的重要的四种基本操作

Status InitStack_Sq(SqStack& S, int size, int inc);//初始化空顺序栈S
Status StackEmpty_Sq(SqStack S);//判断栈是否为空
Status Push_Sq(SqStack& S, ElemType e);//入栈操作
Status Pop_Sq(SqStack& S, ElemType& e);//出栈操作

初始化顺序栈

首先为栈申请一块空间，如果申请失败，即没有足够的内存，返回OVERFLOW

申请成功，注意这里的S.top指向栈顶元素的下一个位置，S.top最先指向0号位置

同时，初始化栈的初始容量和可扩展的容量

Status InitStack_Sq(SqStack& S, int size, int inc) { // 初始化空顺序栈S
    S.elem = (ElemType*)malloc(size * sizeof(ElemType)); // 分配存储空间
    if (NULL == S.elem) return OVERFLOW;//分配失败
    S.top = 0;       // 置S为空栈
    S.size = size;  // 初始容量值
    S.increment = inc; // 初始增量值
    return OK;
}

栈的判空

没有任何元素的时候，栈顶指针指向0号位置，S.top==0

Status StackEmpty_Sq(SqStack S) { // 判断栈S是否空，若空则返回TRUE，否则FALSE
    if (0 == S.top)
        return TRUE;
    else
        return FALSE;
}

入栈操作

首先，入栈后元素越来越多，有栈满的风险，因此第一步检查栈是否已满

栈的容量是S.size，从0号位置开始，因此存储到S.size-1的位置时栈已经满了，因为S.top指向栈顶元素的位置，即S.top==S.size时栈满。

栈满需要为栈分配空间，使用realloc函数分配更多的空间，同样要判断一下分配失败的情况

分配更大的内存后，要更新基址，同时容量增加了S.increment

入栈时，元素先入栈然后指针向后移，即先使用再加1，对应S.top++这种操作

Status Push_Sq(SqStack& S, ElemType e) { // 元素e压入栈S
    ElemType* newbase;
    if (S.top >= S.size) { // 若栈顶位标已到达所分配的容量，则栈满，扩容
        newbase = (ElemType*)realloc(S.elem, (S.size + S.increment) * sizeof(ElemType));
        if (NULL == newbase) return OVERFLOW;
        //Add your code here: 调整S.elem和S.size
        S.elem = newbase;
        S.size += S.increment;
    }
    //Add your code here: e入栈，并将S.top加1
    S.elem[S.top++] = e;

    return OK;
}

出栈操作

首先，出栈后，元素越来越少，有栈空的风险，因此要先判断是否栈空

调用前面的 Status StackEmpty_Sq(SqStack S) 函数进行判断,栈空不能进行出栈，返回ERROR

出栈时，先取出里面的元素，然后指针向前移，先使用，后减的操作，对应S.top--

Status Pop_Sq(SqStack& S, ElemType& e) { // 栈顶元素出栈，赋给元素e
    //Add your code here：判断栈空
    if(StackEmpty_Sq(S)==TRUE)
        return ERROR;
    //Add your code here: e出栈，并将S.top减1
    e = S.elem[S.top-1];
    S.top--;

    return OK;
}

③Main.cpp

简单测试前面的接口是否有问题，没有问题的接口封装好就可以用于各种需要栈的场景里了

这里用于进制转换，我们手算进制转换，我们每次取余，直到该数变为0，我们发现先取的余数后被使用，符合栈“先进后出”的特点

#include <stdio.h>
#include "SqStack.h"

void Conversion(int N) {
    SqStack S;
    ElemType e;
    InitStack_Sq(S, MAXSIZE, INCREMENT); // 栈S的初始容量为MAXSIZE

    while (N != 0)
    {
        Push_Sq(S, N % 8);  // 将N除以8的余数入栈
        N /= 8;             // N取值为其除以8的商
    }
    while (TRUE != StackEmpty_Sq(S))
    { // 依次输出栈中的余数
        Pop_Sq(S, e);
        printf("%d", e);
    }
}

int main() {
    Conversion(1348);
    return 0;
}