红酒商城网站建设方案,wordpress主机转移,书画展示网站源码,wordpress安装资料夹一.栈的基本概念1.栈的定义栈#xff08;Stack#xff09;#xff1a;是只允许在一端进行插入或删除的线性表。首先栈是一种线性表#xff0c;但限定这种线性表只能在某一端进行插入和删除操作。其中注意几点#xff1a;栈顶#xff08;Top#xff09;#xff1a;线性表…一.栈的基本概念1.栈的定义栈Stack是只允许在一端进行插入或删除的线性表。首先栈是一种线性表但限定这种线性表只能在某一端进行插入和删除操作。其中注意几点栈顶Top线性表允许进行插入删除的那一端。栈底Bottom固定的不允许进行插入和删除的另一端。空栈不含任何元素的空表。栈又称为后进先出Last In First Out的线性表简称LIFO结构2.栈的常见基本操作/ 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 栈顶int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps); 二.栈的顺序存储结构1.栈的顺序存储采用顺序存储的栈称为顺序栈它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素同时附设一个指针top指示当前栈顶元素的位置。若存储栈的长度为StackSize则栈顶位置top必须小于StackSize。当栈存在一个元素时top等于0因此通常把空栈的判断条件定位top等于-1。当然我们也可以把top初始化成零这样top指针就指向栈顶的下一个元素只不过我们在实现的时候依然是通过指针的偏移量来对栈顶的元素来进行访问所以两种初始化都是可以的都是先存数据在移动指针。2.顺序栈的基本算法#pragma once
#include stdbool.h
#include stdio.h
#include assert.h
#include stdlib.htypedef int STDatatype;
typedef struct Stack
{STDatatype* a;int capacity;int top; // 初始为0表示栈顶位置下一个位置下标
}ST;void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDatatype x);
void StackPop(ST* ps);
STDatatype StackTop(ST* ps);bool StackEmpty(ST* ps);
int StackSize(ST* ps);3.顺序栈的实现#include Stack.hvoid StackInit(ST* ps)
{assert(ps);//ps-a NULL;//ps-top 0;//ps-capacity 0;ps-a (STDatatype*)malloc(sizeof(STDatatype) * 4);if (ps-a NULL){perror(malloc fail);exit(-1);}ps-top 0;ps-capacity 4;
}void StackDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}void StackPush(ST* ps, STDatatype x)
{assert(ps);// if (ps-top ps-capacity){STDatatype* tmp (STDatatype*)realloc(ps-a, ps-capacity * 2 * sizeof(STDatatype));if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity * 2;}ps-a[ps-top] x;ps-top;
}// 20:20
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps-top--;
}STDatatype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top - 1];
}bool StackEmpty(ST* ps)
{assert(ps);/*if (ps-top 0){return true;}else{return false;}*/return ps-top 0;
}int StackSize(ST* ps)
{assert(ps);return ps-top;
}4.测试程序#includestack.h
void test(void)
{ST ST1;StackInit(ST1);StackPush(ST1, 1);StackPush(ST1, 2);StackPush(ST1, 3);StackPush(ST1, 4);while (!StackEmpty(ST1)){printf(%d\n, StackTop(ST1));StackPop(ST1);}StackDestroy(ST1);
}
int main()
{test();
}三.栈的链式存储结构链栈和顺序表一样针对顺序栈的缺点我们可以设计出链栈采用链式存储的栈称为链栈链栈的优点是便于多个栈共享存储空间和提高其效率且不存在栈满上溢的情况。通常采用单链表实现并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头节点指针Lhead指向栈顶元素如下图所示。2.链栈的定义typedef struct Stack
{Datetype x;//数据域ST *next // 指针域
}ST;3.性能分析链栈的进栈push和出栈pop操作都很简单时间复杂度均为O(1)。对比一下顺序栈与链栈,它们在时间复杂度上是一样的,均为O(1)。对于空间性能,顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便,而链栈则要求每个元素都有指针域,这同时也增加了一些内存开销,但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样,如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。四.共享栈(节省空间)1.共享栈概念利用栈底位置相对不变的特征可让两个顺序栈共享一个一维数组空间将两个栈的栈底分别设置在共享空间的两端两个栈顶向共享空间的中间延伸如下图所示两个栈的栈顶指针都指向栈顶元素top0-1时0号栈为空top1MaxSize时1号栈为空仅当两个栈顶指针相邻top01top1时判断为栈满。当0号栈进栈时top0先加1再赋值1号栈进栈时top1先减一再赋值出栈时则刚好相反。2.设计一个共享栈/*两栈共享空间结构*/
#define MAXSIZE 50 //定义栈中元素的最大个数
typedef DataType int; //ElemType的类型根据实际情况而定这里假定为int
/*两栈共享空间结构*/
typedef struct{DataType a[MAXSIZE];int top0; //栈0栈顶指针int top1; //栈1栈顶指针
}SqDoubleStack;
