---栈)
🎈主页传送门:良木生香
🔥个人专栏:《C语言》 《数据结构-初阶》《程序设计》
🌟人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离
目录
一、栈的概念
二、栈的实现
1、栈的结构体
2、栈的初始化
3、入栈
4、出栈
5、计算元素个数
三、代码总和：
上期回顾:我们在上一篇文章中已经学完了带头结点循环双向链表,那么顺序表和链表这一部分内容就算是告一段落了,现在我们要学习的是栈和队列这一块知识
一、栈的概念
栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除的一端我们将其称之为栈顶，另一端不变的我们将其称之为栈底。站中的元素遵循后进先出LIFO(Last in fisrt out)的原则.
我们将栈的插入操作叫做进栈/压栈/入栈
将栈的删除操作叫做出栈,出数据也在栈顶
下面是栈的示意图:
了解了栈的基本特征之后,我们应该用什么样的方式来实现栈呢?是用数组还是链表呢?
如果把栈倒下来看,根据后进先出的特性,那么就相当于我们会在栈尾进行操作更多一点,在数组与链表之间,对于尾部数据进行频繁地修改,数组相对而言就更加合适,代价也比较小,所以我们选择用数组来实现栈
二、栈的实现
1、栈的结构体
用数组来实现栈，那么站的结构体里面就少不了数组，下面是结构体代码：
typedef struct Stack { Elemtype* arr; //指向的是赞栈的栈底 int top; //这个其实是当前整个栈里面的元素个数 int length; //当前栈的容量 }Stack;top可以说一直指向的是栈顶元素的下一个位置,同时top值也代表了当前栈中的元素个数
length代表的是当前栈的总容量,如果top的值达到了length的值,那就要境内扩容操作了
2、栈的初始化
对栈进行初始化其实就是对结构体里面的元素进行初始化。我们让arr指向NULL,将length与top同时置为0,这就完成了栈的初始化:
void Init_Stack(Stack* pStack) { pStack->arr = NULL; pStack->length = pStack -> top = 0; }
3、入栈
入栈就是就相当于在数组的末尾进行操作
既然是入栈，那传入的参数就要有元素x,下面是具体代码：
//入栈操作: void Push_Stack(Stack* pStack,Elemtype x) { //先判断容量是不是足够 if (pStack->top >= pStack->length) { int newlength = pStack->length == 0 ? 4 : 2 * pStack->length; Stack* newbase = realloc(pStack->arr, newlength * sizeof(Elemtype)); if (newbase == NULL) { printf("申请空间失败,扩容失败...\n"); return; } pStack->arr = newbase; pStack->length = newlength; } //pStack->arr[pStack->top++] = x; *(pStack->arr + pStack->top++) = x; }我们在插入之前，先给栈分配4个单位大小的空间，如果超出了，那就再继续扩容
4、出栈
出栈就更加简单了，先看下图：
为什么我们只是将top向前一定了一位就完成了出栈的操作呢??这是因为,top我们定义它代表的是当前栈顶元素的下一个位置,当top向前移动一位,就说明现在的栈顶元素是3,而不是4了,这样在输出的时候就直接忽略掉4这个元素,在我们想要继续增加元素的时候,4也会被重新覆盖掉,所以这个方案巧妙就巧妙在只用移动top.下面是具体的代码:
//出栈操作 void Pop_Stack(Stack* pStack) { assert(!isEmpty(pStack)); pStack->top--; //只用将top进行--即可将元素减一 }看吧,出栈是不是很简单呢?
5、计算元素个数
虽然说是计算元素个数，其实根本不用计算，为什么？因为栈中top的值其实就代表了占中元素的总个数,由此可见,top在整个栈里面是不可或缺的,我们只用返回top值即可,代码如下:
//计算栈里的元素个数 int num(Stack* pStack) { assert(!isEmpty(pStack)); return pStack->top; }
三、代码总和：
栈相对于前面我们学习的数据结构要简单很多，其实就是数组的简单操作，下
#define _CRT_SECURE_NO_WARNINGS 520 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<windows.h> #include<stdbool.h> typedef int Elemtype; typedef struct Stack { Elemtype* arr; //指向的是赞栈的栈底 int top; //这个其实是当前整个栈里面的元素个数 int length; //当前栈的容量 }Stack; //栈的初始化 void Init_Stack(Stack* pStack) { pStack->arr = NULL; pStack->length = pStack -> top = 0; } //栈的销毁 void Destroy_Stack(Stack* pStack) { assert(pStack); if (pStack->arr) { free(pStack->arr); } pStack->arr = NULL; pStack->length = pStack->top = 0; } //判断栈是否为空 bool isEmpty(Stack* pStack) { assert(pStack); return pStack->top == 0; } //入栈操作: void Push_Stack(Stack* pStack,Elemtype x) { //先判断容量是不是足够 if (pStack->top >= pStack->length) { int newlength = pStack->length == 0 ? 4 : 2 * pStack->length; Stack* newbase = realloc(pStack->arr, newlength * sizeof(Elemtype)); if (newbase == NULL) { printf("申请空间失败,扩容失败...\n"); return; } pStack->arr = newbase; pStack->length = newlength; } //pStack->arr[pStack->top++] = x; *(pStack->arr + pStack->top++) = x; } //出栈操作 void Pop_Stack(Stack* pStack) { assert(!isEmpty(pStack)); pStack->top--; //只用将top进行--即可将元素减一 } //取栈顶元素 Elemtype Get_elem(Stack* pStack) { assert(!isEmpty(pStack)); return *(pStack->arr + pStack->top-1); } //计算栈里的元素个数 int num(Stack* pStack) { assert(!isEmpty(pStack)); return pStack->top; } //打印栈 void my_printf(Stack* pStack) { assert(pStack); if (pStack->top == 0) { printf("当前栈里面没有元素...\n"); return; } for (int i = 0; i < pStack -> top; i++) { printf("%d ",*(pStack->arr+i)); } } //打印菜单 void printf_menu() { printf("=========================================\n"); printf("你可以进行以下操作:\n"); printf("1.入栈 2.出栈 3.计算当前元素个数 4.取栈顶元素\n"); printf("=========================================\n"); printf("\n"); } int main() { Stack L; Stack* pStack = &L; Init_Stack(pStack); int choose = 0; do { system("cls"); printf_menu(); printf("当前的栈为:\n"); my_printf(pStack); printf("\n"); printf("请输入你的选择(按-1结束程序):\n"); scanf("%d", &choose); switch (choose) { case 1: { printf("请输入你想输入的元素个数:\n"); int num = 0; Elemtype data = 0; scanf("%d", &num); printf("请输入元素:\n"); for (int i = 0; i < num; i++) { scanf("%d", &data); Push_Stack(pStack, data); } Sleep(1000); printf("正在录入...\n"); Sleep(1000); printf("录入成功!!!\n"); Sleep(2000); break; } case 2: { Pop_Stack(pStack); printf("正在出栈...\n"); Sleep(1000); printf("出栈成功!!!\n"); Sleep(1000); break; } case 3: { int num_elem = num(pStack); printf("正在计算...\n"); Sleep(2000); printf("当前栈的元素个数为: %d", num_elem); Sleep(2000); break; } case 4: { Sleep(1000); printf("当前栈顶元素为: %d", *(pStack->arr + pStack->top - 1)); Sleep(2000); break; } case -1: { printf("正在退出程序...\n"); Sleep(2000); printf("退出成功!!!\n"); Sleep(2000); break; } default: { printf("输入错误,请重新输入...\n"); Sleep(2000); break; } } } while (choose != -1); Destroy_Stack(pStack); pStack = NULL; return 0; }那么以上就是我对栈相关知识的分享了~~~~感谢大佬们的阅读~~~~
文章是自己写的哈，有啥描述不对的、不恰当的地方，恳请大佬指正，看到后会第一时间修改，感谢您的阅读。
