佛山网站建设网站制作公司哪家好,seo是怎么优化推广的,做自己的网站流量怎么,wordpress棋牌模板一. 栈的基本概念#x1f4ab;栈是一种特殊的线性表。其只允许在固定的一端进行插入和删除元素的操作#xff0c;进行数据的插入和删除的一端称作栈顶#xff0c;另外一端称作栈底。栈不支持随机访问#xff0c;栈的数据元素遵循后进先出的原则#xff0c;即LIFO#xff…一. 栈的基本概念栈是一种特殊的线性表。其只允许在固定的一端进行插入和删除元素的操作进行数据的插入和删除的一端称作栈顶另外一端称作栈底。栈不支持随机访问栈的数据元素遵循后进先出的原则即LIFOLate In First Out。也许有人曾经听说过压栈和入栈的术语以下是它们的定义压栈栈的插入操作叫做进栈/压栈/入栈插入数据是在栈顶 出栈栈的删除操作叫做出栈/弹栈删除数据也是在栈顶 我们结合动图来理解栈的后进先出二. 栈实现方法的分析与选择2.1 引入我们可以使用顺序存储结构或者链式存储结构来实现栈。换句话来说我们可以使用之前学习过的顺序表或者链表来实现栈它们各自有自己的优缺点下面我们就来分析分析。2.2 用顺序表来实现以下是动态顺序表实现栈的结构体声明和图示typedef struct StackList
{STDataType* a; //指向动态开辟的空间int top; //栈顶所在下标相当于元素个数int capacity;//顺序表容量
}ST;优点由于栈的插入和删除数据符合后进先出的原则我们把顺序表末端当作栈顶则插入数据和删除数据就是尾插和尾删。而前面我们知道顺序表的尾插和尾删效率非常高时间复杂度为O1。缺点存在容量限制当容量不足是需要扩容扩容需要成本。2.3 用链表来实现2.3.1 单链表实现(尾为栈顶)typedef struct StackNode
{STDataType x;//数据域StackNode* nest;//指针域指向下一结点
}ST;
struct Stack
{ST* phead;//指向第一个结点ST* tail;//指向尾结点
}假如我们使用链表尾当作栈顶则对应的插入删除就是尾插和尾删。我们知道单链表的尾插和尾删要先找到链表尾时间复杂度是O(N)。可能有人会想那我定义一个尾指针来记录链表尾部想法很好但是这样虽然解决了尾插效率低的问题但是尾删除了要找到最后一个结点还要找到其前面的结点由于链表单向最终还是要遍历链表没有什么意义。2.3.2 单链表实现(头为栈顶)我们知道和顺序表相反单链表头插和头删效率较高时间复杂度为O1。我们就可以将链表头当作栈顶这样插入就相当于头插删除就相当于头删如下2.3.3 双向链表实现如果一定要使用链表以及把链表尾当作栈顶为了解决删除需要找到尾结点的前驱结点时间效率低的问题我们可以用双向链表来实现栈。双向链表除了后继指针还增加了前驱指针来指向上一个结点利用这个结构可以直接得到上一个结点无需再遍历链表时间复杂度为O1。typedef struct StackNode
{STDataType x;//数据域StackNode* nest;//后继指针域指向下一结点StackNode* prev;//前驱指针域指向上一结点
}ST;
struct Stack
{ST* phead;//指向第一个结点ST* tail;//指向尾结点
}2.3.4 总结如果没有要求栈顶的位置则我们还是使用单链表来实现将头作为栈顶。这是因为双向链表比单链表的结点多占用了一个前驱指针的空间虽然现代计算机空间已然构不成太大问题但是能省则省大伙们懂的。 如果题目要求栈顶在链表尾的话那还是老老实实用双向链表实现吧。 使用链表的缺点就是每次插入都要malloc新结点会消耗一定的时间成本。2.4 选择我们推荐采用顺序表来实现对栈的操作原因如下1. 栈的特性完美避开了顺序表尾插尾删效率过低的问题虽然需要扩容但是链表创建结点也同样需要成本而顺序表扩容频率不像链表一样如此频繁。2. 我们知道CPU与主存速度上存在巨大差距为了提高效率CPU和主存之间还存在着cache高速缓存。CPU访问cache的速度是快于主存的。每次CPU取数据时会访问cache看看存不存在所需的数据如果不存在才会访问主存然后将数据所在的内存块加载到cache中。由于顺序表空间是连续的根据cache的空间局部性原理采用顺序表cache的命中率会高于链表效率高。三. 接口的实现✈3.1 栈的声明本文我们采用动态顺序表来实现栈结构体的声明如下typedef int STDataType;
typedef struct StackList
{STDataType* a;//指向动态开辟的空间int top; //栈顶所在下标相当于元素个数int capacity;//栈的容量
}ST;和前面链表顺序表一样我们不直接指定数据的类型而是将类型重定义为STDataType这样做有利于提高代码的可维护性。3.2 初始化和销毁和其他数据结构一样当我们使用栈结构之前需要对其进行初始化当我们不再使用它是要对它进行销毁具体代码如下//初始化栈
void StackInit(ST* ps) //需要改变实参传指针
{assert(ps);//确保传入的指针不为空ps-a (STDataType*)malloc(4 * sizeof(STDataType));//起初先分配四个字节空间ps-capacity 4;ps-top 0;
}//销毁栈
void StackDestroy(ST* ps)
{assert(ps);free(ps-a);//将栈空间释放掉//将栈结构中的信息清空ps-capacity 0;ps-top 0;ps-a NULL;
}3.3 入栈由于栈只允许在固定的一端插入我们又将末端当作栈顶因此入栈就是尾插。而顺序表的尾插我们已经很清楚了往栈顶所在下标放入数据然后栈顶下标加1即可。效果和代码如下//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity) //元素个数等于容量栈满了先扩容{STDataType* temp (STDataType*)realloc(ps-a, 2 * ps-capacity*sizeof(STDataType));if (temp NULL)//失败则退出程序{printf(扩容失败\n);exit(-1);}else{ps-a temp;ps-capacity * 2;temp NULL;}}(ps-a)[ps-top] x;//入栈(ps-top);//更新栈顶位置
}3.4 出栈 和入栈一样出栈也只在固定的一端进行。入栈是尾插则出栈就是尾删。而我们用顺序表来实现栈因此尾删只需要将栈顶退后一位即可。这里有人可能会将栈顶的元素置0然后再将栈顶位置后退一位。实际上这种方法并不可取有以下两种原因1. 如果栈顶的元素本身就是0那我们的行为就失去了意义。2. 栈的元素类型不一定是整形如果是浮点型或者结构体我们赋值为0显然是不妥的。//出栈
void StackPop(ST* ps)
{assert(ps);//确保传入指针不为空assert(ps-top);//确保栈存在元素(ps-top)--;//更新栈顶
}3.5 求栈顶元素很简单我们可以直接根据栈顶所在的下标得到栈顶元素如下//求栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(ps-top);//确保栈中存在元素return ps-a[ps-top - 1];//栈顶元素所在下标即为top-1
}3.6 判空在我们设计的栈结构中top实际上就等价于元素个数通过判断top是否为0就可以知道栈是否为空。我们使用了C语言stdbool.h头文件中的bool类型其只能用来存放true(1)和false(0)两个值分别代表真和假。代码如下//判空
bool StackEmpty(ST* ps)
{assert(ps);return ps-top;//top为0则返回false不为零返回true
}3.7 求栈的元素个数根据我们构造的栈结构体栈顶top的值就是栈的元素个数直接返回即可//求栈的元素个数
int StackSize(ST* ps)
{assert(ps);return ps-top;
}3.8 思考会不会有人会有以下思考1. 求栈顶元素判空求元素个数都是用一行直接返回这些接口会不会有些许多余直接访问结构体相应成员不就好了2. 为什么没有实现查找打印修改等接口下面我们来分析一下我们要知道数据结构的实现方式多种多样在本文我们将栈元素个数作为栈顶的下标那可不可以将最后一个元素的下标作为栈顶下标呢实际上完全可以。那么就会出现一个问题如果我们使用别人已经封装好的栈我们要怎么知道栈顶元素下标是top还是top-1呢我们要怎么知道是top0为空还是top-1为空呢我们要怎么知道元素个数是top还是top1呢我们完全不知道只有设计者才知道因此设计者往往会将这些功能再封装成函数供我们直接调用。这是因为栈是一种限制型数据结构其不支持随机访问只允许在固定的一端(栈顶)进行插入和删除操作不允许在其他的位置进行任何操作。因此栈不存在查找打印修改等对除栈顶之外的位置进行操作的接口否则会破坏栈的特性。为了遵循栈的特性我们就不实现这些接口。四. 完整代码及效果展示按照以往惯例我们采用多文件编写的形式将上述接口的定义实现放在Stack.c文件中然后将接口的声明和结构体的定义放于Stack.h头文件中以达到封装的效果。这样我们如果需要使用栈就只需要在文件中包含对应的头文件Stack.h就可以使用我们上面定义的各种接口。以下为本文实现的栈完整代码以及效果展示//Stack.h文件用于声明接口函数定义结构体
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int STDataType;
typedef struct StackList
{STDataType* a;//指向动态开辟的空间int top; //栈顶所在下标相当于元素个数int capacity;//栈的容量
}ST;//初始化
void StackInit(ST* ps);
//销毁
void StackDestroy(ST* ps);
//出栈
void StackPop(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//求栈顶元素
STDataType StackTop(ST* ps);
//求栈元素个数
int StackSize(ST* ps);
//判空
bool StackEmpty(ST* ps);//Stack.c文件用于定义接口函数
#includeStack.h//初始化栈
void StackInit(ST* ps) //需要改变实参传指针
{assert(ps);//确保传入的指针不为空ps-a (STDataType*)malloc(4 * sizeof(STDataType));//起初先分配四个字节空间ps-capacity 4;ps-top 0;
}//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity) //元素个数等于容量栈满了先扩容{STDataType* temp (STDataType*)realloc(ps-a, 2 * ps-capacity * sizeof(STDataType));if (temp NULL)//失败则退出程序{printf(扩容失败\n);exit(-1);}else{ps-a temp;ps-capacity * 2;temp NULL;}}(ps-a)[ps-top] x;//入栈(ps-top);//更新栈顶位置
}//出栈
void StackPop(ST* ps)
{assert(ps);//确保传入指针不为空assert(ps-top);//确保栈存在元素(ps-top)--;//更新栈顶
}//求栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(ps-top);//确保栈中存在元素return ps-a[ps-top - 1];//栈顶元素所在下标即为top-1
}//求栈的元素个数
int StackSize(ST* ps)
{assert(ps);return ps-top;
}//判空
bool StackEmpty(ST* ps)
{assert(ps);return ps-top;//top为0则返回false不为零返回true
}//销毁栈
void StackDestroy(ST* ps)
{assert(ps);free(ps-a);//将栈空间释放掉//将栈结构中的信息清空ps-capacity 0;ps-top 0;ps-a NULL;
} 最后 我们在tesst.c文件调用栈各个接口进行测试如下//test.c文件用于测试
#includeStack.hvoid test01()
{ST s1;//初始化StackInit(s1);//求元素个数printf(入栈前栈的元素个数为:%d\n, StackSize(s1));//入栈StackPush(s1,1);StackPush(s1, 2);StackPush(s1, 3);StackPush(s1, 4);printf(入栈后栈的元素个数为:%d\n, StackSize(s1));//由于无法遍历打印我们就交替使用 求栈顶元素-出栈 来显示栈中元素printf(栈中元素: );while (StackEmpty(s1))//栈不为空则继续{//求栈顶元素printf(%d , StackTop(s1));//出栈StackPop(s1);}//全部出栈printf(\n全部出栈后栈的元素个数为:%d\n, StackSize(s1));//销毁StackDestroy(s1);
}int main()
{test01();return 0;
}以下是测试的最终效果以上就是本期的全部内容啦制作不易能否点个赞再走呢
