郑州做网站九零后,装饰公司网站建设方案,中国住房和城乡建设部网站注册中心,软件下载网站地址前言
介绍
#x1f343;数据结构专区#xff1a;数据结构
参考
该部分知识参考于《数据结构#xff08;C语言版 第2版#xff09;》55 ~ 59页
#x1f308;每一个清晨#xff0c;都是世界对你说的最温柔的早安#xff1a;ૢ(≧▽≦)و✨ 1、栈的基本概念 栈#x…
前言
介绍
数据结构专区数据结构
参考
该部分知识参考于《数据结构C语言版 第2版》55 ~ 59页
每一个清晨都是世界对你说的最温柔的早安ૢ(≧▽≦)و✨ 1、栈的基本概念 栈Stack是一种遵循后进先出LIFO, Last In First Out原则的有序集合。 数组实现使用数组的一个连续空间来存储栈中的元素通常使用一个指针或索引来指示栈顶的位置。数组实现的栈在添加和删除元素时如果数组已满或为空可能需要进行扩容或缩容操作这可能会涉及到额外的性能开销。链表实现使用链表的头部或尾部取决于具体实现作为栈顶通过修改链表的头指针或尾指针来实现元素的添加和删除。链表实现的栈在添加和删除元素时不需要进行扩容或缩容操作因此通常具有更好的性能。 2、数组栈的实现
2.1 宏定义
#includeiostream
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;2.2 数组栈的结构体定义
#define MAXSIZE 100 //顺序表的存储范围
#define STACK_INCREMENT 2 //存储空间分配增量//这里假定SElemType是int类型
typedef int SElemType;typedef struct
{SElemType* base; //栈底指针SElemType* top; //栈顶指针int stacksize; //栈可用的最大容量
}SqStack;2.3 初始化数组栈
//初始化栈
Status InitStack(SqStack S)
{S.base new SElemType[MAXSIZE];if (!S.base)exit(OVERFLOW);S.top S.base; //top初始化为base空栈S.stacksize MAXSIZE; //stacksize的最大容量为MAXSIZEreturn OK;
}2.4 销毁数组栈
//销毁栈
Status DestroyStack(SqStack S)
{free(S.base);S.base NULL;S.top NULL; //规范指针S.stacksize 0;return OK;
}
2.5 清空数组栈
//清除栈
Status CleanStack(SqStack S)
{S.top S.base; //让top指针指回栈底即可return OK;
}
2.6 判空
//判空
Status StackEmpty(SqStack S)
{if (S.top S.base) //如果栈顶和栈底指向同一个位置则证明栈为NULLreturn OK;elsereturn ERROR;
}
2.7 获取栈内元素个数
//获取栈内元素数量
int StackLength(SqStack S)
{return S.top - S.base;
}
2.8 获取栈顶元素
//获取栈顶元素
SElemType GetTop(SqStack S)
{//判断栈是否为空if (!StackEmpty(S))//不为空即可获取元素{return *(--S.top);}else{return ERROR;}
}
2.9 入栈
//入栈
Status Push(SqStack S, SElemType e)
{//插入元素为新的栈顶元素if (S.top - S.base S.stacksize)//满栈{S.base (SElemType*)realloc(S.base, (S.stacksize STACK_INCREMENT) * sizeof(SElemType));//判断是否扩容成功if (!S.base)exit(OVERFLOW);//如果扩容失败退出程序S.top S.base S.stacksize;}*(S.top) e; //这里是先对S.top解引用后存入数据e随后将top指针向后移动一位
}
2.10 出栈
//出栈
Status Pop(SqStack S, SElemType e)
{//删除栈顶元素并返回其值if (!StackEmpty(S)) //栈不为空进行操作{e *(--S.top);return OK;}elsereturn ERROR;
}2.11 visit()函数
// 定义一个函数visit用于打印元素
void visit(SElemType e)
{std::cout e ;
}
2.12 遍历数组栈
// 定义一个函数用于遍历栈中的元素并对每个元素执行visit函数
void StackTraverse(SqStack S, void(*visit)(SElemType))
{SElemType* p S.base;while (S.top p) //p指向栈元素visit(*p); //对该栈调用visit()p指针上移一个存储单元printf(\n);
}2.13 整体代码含测试代码
#includeiostream
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;#define MAXSIZE 100 //顺序表的存储范围
#define STACK_INCREMENT 2 //存储空间分配增量//这里假定SElemType是int类型
typedef int SElemType;typedef struct
{SElemType* base; //栈底指针SElemType* top; //栈顶指针int stacksize; //栈可用的最大容量
}SqStack;//SqStack S; //声明该栈//初始化栈
Status InitStack(SqStack S)
{S.base new SElemType[MAXSIZE];if (!S.base)exit(OVERFLOW);S.top S.base; //top初始化为base空栈S.stacksize MAXSIZE; //stacksize的最大容量为MAXSIZEreturn OK;
}//销毁栈
Status DestroyStack(SqStack S)
{free(S.base);S.base NULL;S.top NULL; //规范指针S.stacksize 0;return OK;
}//清除栈
Status CleanStack(SqStack S)
{S.top S.base; //让top指针指回栈底即可return OK;
}//判空
Status StackEmpty(SqStack S)
{if (S.top S.base) //如果栈顶和栈底指向同一个位置则证明栈为NULLreturn OK;elsereturn ERROR;
}//获取栈内元素数量
int StackLength(SqStack S)
{return S.top - S.base;
}//获取栈顶元素
SElemType GetTop(SqStack S)
{//判断栈是否为空if (!StackEmpty(S))//不为空即可获取元素{return *(--S.top);}else{return ERROR;}
}//入栈
Status Push(SqStack S, SElemType e)
{//插入元素为新的栈顶元素if (S.top - S.base S.stacksize)//满栈{S.base (SElemType*)realloc(S.base, (S.stacksize STACK_INCREMENT) * sizeof(SElemType));//判断是否扩容成功if (!S.base)exit(OVERFLOW);//如果扩容失败退出程序S.top S.base S.stacksize;}*(S.top) e; //这里是先对S.top解引用后存入数据e随后将top指针向后移动一位
}//出栈
Status Pop(SqStack S, SElemType e)
{//删除栈顶元素并返回其值if (!StackEmpty(S)) //栈不为空进行操作{e *(--S.top);return OK;}elsereturn ERROR;
}// 定义一个函数visit用于打印元素
void visit(SElemType e)
{std::cout e ;
}// 定义一个函数用于遍历栈中的元素并对每个元素执行visit函数
void StackTraverse(SqStack S, void(*visit)(SElemType))
{SElemType* p S.base;while (S.top p) //p指向栈元素visit(*p); //对该栈调用visit()p指针上移一个存储单元printf(\n);
}int main() {int j;SqStack s;SElemType e;InitStack(s);for (j 1; j 12; j)Push(s, j);printf(栈中元素依次为\n);StackTraverse(s, visit);Pop(s, e);printf(弹出的栈顶元素e %d\n, e);printf(栈空否? %d (1:空 0:否)\n, StackEmpty(s));e GetTop(s);printf(栈顶元素e %d,栈的长度为%d\n, e, StackLength(s));CleanStack(s);printf(清空栈后栈空否? %d (1:空 0:否)\n, StackEmpty(s));DestroyStack(s);printf(销毁栈后s.top %u,s.base %u,s.stacksize %d\n, s.top, s.base, s.stacksize);
}
3、链表栈的实现
3.1 宏定义
#includeiostream
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;3.2 链表栈的结构体定义
typedef int SElemType;
typedef struct StackNode
{SElemType data;struct StackNode* next;
}StackNode, *LinkStack;3.3 初始化链表栈
//初始化
Status InitStack(LinkStack S)
{//让栈顶指针指向NULL即可S NULL;return OK;
}3.4 清空栈
//清空栈
Status ClearStack(LinkStack S)
{//创建一个临时指针遍历该链表后依次释放各个节点StackNode* p;while (S){p S;S S-next;delete p;}return OK;
}3.5 判空
//判空
Status StackEmpty(LinkStack S)
{return S NULL;
}
3.6 销毁链表栈
//销毁
Status DestroyStack(LinkStack S)
{ClearStack(S);S NULL;return OK;
}3.7 入栈
//入栈
Status Push(LinkStack S, SElemType e)
{//在栈顶位置插入元素eStackNode* p new StackNode;p-data e;p-next S; //将新结点插入栈顶S p; //修改栈顶指针为preturn OK;
}
3.8 出栈
//出栈
Status Pop(LinkStack S, SElemType e)
{//删除栈顶元素并返回该元素if (S NULL)return ERROR;StackNode * p S;e p-data;S S-next;delete p;return OK;
} 3.9 获取栈顶元素
//获取栈顶元素
SElemType GetTop(LinkStack S)
{//返回S的栈顶元素并不改变栈顶指针的位置if (S ! NULL){return S-data;}
}
3.10 遍历打印
// 遍历栈并打印
void StackTraverse(LinkStack S)
{StackNode* p S;while (p) {printf(%d , p-data);p p-next;}printf(\n);
}3.11 整体代码含测试代码
#includeiostream
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;typedef int SElemType;
typedef struct StackNode
{SElemType data;struct StackNode* next;
}StackNode, *LinkStack;//初始化
Status InitStack(LinkStack S)
{//让栈顶指针指向NULL即可S NULL;return OK;
}//清空栈
Status ClearStack(LinkStack S)
{//创建一个临时指针遍历该链表后依次释放各个节点StackNode* p;while (S){p S;S S-next;delete p;}return OK;
}//判空
Status StackEmpty(LinkStack S)
{return S NULL;
}//销毁
Status DestroyStack(LinkStack S)
{ClearStack(S);S NULL;return OK;
}//入栈
Status Push(LinkStack S, SElemType e)
{//在栈顶位置插入元素eStackNode* p new StackNode;p-data e;p-next S; //将新结点插入栈顶S p; //修改栈顶指针为preturn OK;
}//出栈
Status Pop(LinkStack S, SElemType e)
{//删除栈顶元素并返回该元素if (S NULL)return ERROR;StackNode * p S;e p-data;S S-next;delete p;return OK;
}//获取栈顶元素
SElemType GetTop(LinkStack S)
{//返回S的栈顶元素并不改变栈顶指针的位置if (S ! NULL){return S-data;}
}// 遍历栈并打印
void StackTraverse(LinkStack S)
{StackNode* p S;while (p) {printf(%d , p-data);p p-next;}printf(\n);
}int main()
{LinkStack S;InitStack(S);int e;Push(S, 1);Push(S, 2);Push(S, 3);printf(现在栈内元素为(后进先出));StackTraverse(S);printf(栈顶元素为%d\n, GetTop(S));Pop(S, e);printf(现在栈内元素为(后进先出));StackTraverse(S);printf(弹出一个元素后栈顶元素为%d\n, GetTop(S));ClearStack(S);if (StackEmpty(S)) {printf(清空栈后栈为空\n);}else {printf(清空栈后栈不为空证明有问题\n);}DestroyStack(S);return 0;
}结语
到此我们的两种栈的实现代码就完成了我们可以发现在实现栈的过程中远没有当初学习顺序表那么困难那是因为栈其实就是一种特殊结构的顺序表并且在前面的学习顺序表过程中我故意将ElemType写为一种结构体类型让我们在学习顺序表时写起来就有些困难在前面学会之后看到这里就游刃有余了
