顺序栈的定义
栈（stack），是仅限在表尾进行插入或者删除操作的线性表，因此，对栈来说，表尾端有其特殊含义，称为栈顶，表头端则称为栈底，不含元素的空表称为空栈。栈的修改是按照后进先出的原则进行的，因此，栈也被称为后进先出的线性表。
结构体定义
我们定义一个栈顶指针top和一个栈底指针base，栈顶指针和栈顶指针一开始指向同一片空间。
所以top==base可以作为栈空的标记。
当插入一个新数据时，栈顶指针加一，删除一个元素时，栈顶指针减一。
所以当顺序栈非空时，栈顶指针永远在栈顶元素的下一位。
#include<stdio.h> #include<stdlib.h> #include<errno.h> #define maxsize 100 #define inc 10 typedef struct Sqstack { int* base;//栈顶指针 int* top;//栈底指针 int stacksize;//栈的容量 }stack;
顺序栈的初始化
上面也说了，顺序栈一开始栈顶指针和战地指针是指向一块空间的，因此这里就让栈顶指针和栈底指针相等。
我们使用动态内存开辟空间，先给栈一个默认的空间大小。
如果不够，后面的入栈会检测到并开辟空间。
如果空间开辟失败，就退出。
void InitStack(stack& s) { s.base = (int*)malloc(sizeof(int) * maxsize); if (!s.base) exit(0); s.top=s.base; s.stacksize = maxsize; }
判断顺序栈是否为空
这里没什么好说的，如果栈顶指针和栈底指针指向同一片空间，那就说明它们中间没有数据，顺序栈是空栈。
int isEmpty(stack s) { if (s.base==s.top) { return 1; } return 0; }
求顺序栈的长度
栈顶指针减去栈底指针的值即为顺序栈的长度。
int stacklength(stack s) { return s.top - s.base; }
清空顺序栈
如果顺序栈不是空栈，就让栈顶指针等于栈底指针，这就在逻辑上清空了顺序栈的元素。
如果顺序表是空栈，就表明顺序栈已经清空，不需要重复操作。
void stackclean(stack& s) { if (s.base) { s.top = s.base; printf("顺序栈清空成功\n"); } else { printf("顺序栈已清空，无需再次重复操作\n"); } }
销毁顺序栈
我们直接用delete函数来销毁栈底指针所指向的空间，也就是顺序栈。
之后不要忘记将栈顶指针和栈底指针置空，否则会造成内存泄露的问题 。
void destorystack(stack& s) { if (s.base) { delete(s.base); s.stacksize = 0; s.base = NULL; s.top = NULL; printf("销毁成功\n"); } else { printf("栈已经被销毁，无需销毁\n"); } }
顺序栈的入栈
当顺序栈里的空间不够用的时候，就需要动态的开辟空间。
使用realloc函数来开辟新的空间，并让栈底指针指向这一片空间。
需要注意的是，栈顶指针和栈底指针在新空间的位置需要我们重新定义。
stacksize也要加上我们之前定义的增加量。
void push(stack& s,int e) { if ((s.top - s.base) >= s.stacksize) { s.base = (int*)realloc(s.base, (maxsize + inc) * sizeof(int)); if (!s.base) perror("realloc"); s.top = s.base + s.stacksize; s.stacksize += inc; } else { *(s.top) = e; s.top++; printf("添加成功\n" ); } }
顺序栈的出栈
这里用到了之前判断顺序栈是否为空的函数。
如果为空，则打印无法弹出。
不为空，先让栈顶指针减一到栈顶第一个元素的位置，再将其值复制给指针变量e。成功弹出元素。
void pop(stack& s,int &e) { if (isEmpty(s)) { printf("栈为空，无法弹出\n"); } else { if (s.top != s.base) { s.top--; e = *(s.top); printf("成功弹出\n"); } } }
求栈顶元素
求栈顶元素的操作看起来和出栈的操作一模一样。
是不是有的小伙伴会担心这里的操作会把数据弹出？？
那你就忽略了一个点，这里函数声明里所传的是一级指针，并没有改变实参的能力。
也就是说，这里函数声明里的形参只是实参的临时拷贝而已。翻不起风浪。
int top(stack s) { if (isEmpty(s)) { printf("栈为空，没有栈顶元素\n") ; return -1; } else { s.top--; return *(s.top); } }
顺序栈的遍历
这里需要用到上面求长度的函数，求出长度遍历并打印顺序栈元素即可。
void traverse(stack s) { int length = stacklength(s); if (length > 0) { for (int i = 0; i < stacklength(s); i++) { printf("%d ", s.base[i]); } } else { printf("顺序栈为空\n"); } }
菜单的打印
void menu() { printf("**********************************\n"); printf("1.初始化\n"); printf("2.判断栈是否为空\n"); printf("3.求栈的长度\n"); printf("4.清空栈\n"); printf("5.销毁栈\n"); printf("6.入栈\n"); printf("7.出栈\n"); printf("8.求栈顶元素\n"); printf("9.遍历顺序栈\n"); printf( "10.退出\n"); printf( "**********************************\n" ); }
顺序栈的代码实现
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<errno.h> typedef struct Sqstack { int* base;//栈顶指针 int* top;//栈底指针 int stacksize;//栈的容量 }stack; #define maxsize 100 #define inc 10 void InitStack(stack& s) { s.base = (int*)malloc(sizeof(int) * maxsize); if (!s.base) exit(0); s.top=s.base; s.stacksize = maxsize; } int isEmpty(stack s) { if (s.base==s.top) { return 1; } return 0; } int stacklength(stack s) { return s.top - s.base; } void stackclean(stack& s) { if (s.base) { s.top = s.base; printf("顺序栈清空成功\n"); } else { printf("顺序栈已清空，无需再次重复操作\n"); } } void destorystack(stack& s) { if (s.base) { delete(s.base); s.stacksize = 0; s.base = NULL; s.top = NULL; printf("销毁成功\n"); } else { printf("栈已经被销毁，无需销毁\n"); } } void push(stack& s,int e) { if ((s.top - s.base) >= s.stacksize) { s.base = (int*)realloc(s.base, (maxsize + inc) * sizeof(int)); if (!s.base) perror("realloc"); s.top = s.base + s.stacksize; s.stacksize += inc; } else { *(s.top) = e; s.top++; printf("添加成功\n" ); } } void pop(stack& s,int &e) { if (isEmpty(s)) { printf("栈为空，无法弹出\n"); } else { if (s.top != s.base) { s.top--; e = *(s.top); printf("成功弹出\n"); } } } void traverse(stack s) { int length = stacklength(s); if (length > 0) { for (int i = 0; i < stacklength(s); i++) { printf("%d ", s.base[i]); } } else { printf("顺序栈为空\n"); } } int top(stack s) { if (isEmpty(s)) { printf("栈为空，没有栈顶元素\n") ; return -1; } else { s.top--; return *(s.top); } } void menu() { printf("**********************************\n"); printf("1.初始化\n"); printf("2.判断栈是否为空\n"); printf("3.求栈的长度\n"); printf("4.清空栈\n"); printf("5.销毁栈\n"); printf("6.入栈\n"); printf("7.出栈\n"); printf("8.求栈顶元素\n"); printf("9.遍历顺序栈\n"); printf( "10.退出\n"); printf( "**********************************\n" ); } int main() { int choice; stack s; int e1, e2; while (1) { menu(); scanf("%d",&choice); switch (choice) { case 1: InitStack(s); printf( "初始化成功\n" ); break; case 2: if (isEmpty(s)) printf("栈为空\n" ); else printf("栈不为空\n"); break; case 3: printf("栈的长度为%d\n", stacklength(s)); break; case 4: stackclean(s); break; case 5: destorystack(s); break; case 6: printf("请输入想要入栈的元素值:>"); scanf("%d",&e1); push(s, e1); break; case 7: pop(s, e2); printf("弹出的元素为%d\n" ,e2 ); break; case 8: if (top(s) != -1) printf("栈顶元素为%d\n" , top(s) ); break; case 9: traverse(s); printf("\n"); break; case 10: printf ( "成功退出\n" ); exit(0); default: printf ("输入有误，请重新输入\n" ); break; } } }
运行实例
总结
感谢观看，本文到这里就结束了，如果觉得有帮助，请给文章点个赞吧，让更多的人看到。🌹 🌹 🌹
也欢迎你，关注我。👍 👍 👍
原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！💕 💕 💕 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！下期再见。🎉
