【数据结构】线性数据结构-顺序栈
栈（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;
}
原文地址：https://blog.csdn.net/2301_79728896/article/details/142422875
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！