无形资产 网站建设,最新项目加盟代理,成都网站设计培训班,网站建设的商品分类编码前言
在进入数据结构初阶的学习之后#xff0c;我们学习了顺序表和链表#xff0c;当然栈也是一种特殊的数据结构#xff0c;他的特点是后进先出。 栈的概念及结构 栈#xff08;stack#xff09;又名堆栈#xff0c;它是一种运算受限的线性表。限定仅在表尾进行插入和删…前言
在进入数据结构初阶的学习之后我们学习了顺序表和链表当然栈也是一种特殊的数据结构他的特点是后进先出。 栈的概念及结构 栈stack又名堆栈它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶相对地把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈它是把新元素放到栈顶元素的上面使之成为新的栈顶元素从一个栈删除元素又称作出栈或退栈它是把栈顶元素删除掉使其相邻的元素成为新的栈顶元素。 我们切记此处的栈是数据结构中的栈与我们操作系统处学习的栈是不同的它是一个数据存储的位置而这里的栈是数据存储时的结构是两个学科中不同的术语。 栈的入数据叫做进栈压栈或者入栈出数据时叫做出栈栈的压栈和出栈都是在栈顶操作的所以符合后进先出或者先进后出。 我们的生活中就有很多关于栈的示例比如我们在坐电梯的时候后上来的人到达目的地之后先出电梯先上来的人后出电梯。 栈的接口实现
我们在学习完顺序表和链表之后我们就要考虑顺序表和链表的优劣点来实现栈我们知道栈的入栈和出栈都是一端所以可以使用顺序表的尾插和尾删也可以使用链表的头插头删以及尾插尾删但是在都可以实现的情况下我们就要选择消耗最小的顺序表。
1定义结构体
typedef int datetype;typedef struct Stack
{datetype* a;int capacity;int top;
}stack;
我们使用typedef定义栈中存储数据的类型这样方便我们在日后的使用中进行修改我们将栈的结构定义为一个动态的顺序表通过a指针来控制同时记录栈顶的位置以及最大容量。
2栈的初始化
void stackInit(stack* p)
{assert(p);p-a NULL;p-capacity 0;p-top 0;
}
对p进行断言能够防止不小心传入NULL后解引用程序崩溃初始化各个数据。
3压栈
void stackPush(stack* p,datetype x)
{assert(p);if (p-capacity p-top){int newCapacity p-capacity 0 ? 4 : 2 * p-capacity;datetype* tmp (datetype*)realloc(p-a, newCapacity * sizeof(datetype));if (tmp NULL){perror(realloc);exit(-1);}p-a tmp;p-capacity newCapacity;}p-a[p-top] x;p-top;
}
同理对指针p进行断言判断栈顶是否达到最大容量处如果没有到达直接将数据插入到top处并且top自加如果到了最大容量我们就对顺序表进行扩容首先判断容量是否为0为0时将容量扩到4个数据的字节数否则容量乘2。
此处的压栈与顺序表的尾插相同。
4出栈
void stackPop(stack* p)
{assert(p);assert(!stackEmpty(p));p-top--;
} 同理对指针进行断言还需要注意的时需要判断顺序表是否为NULL如果为空解引用后程序会崩溃所以我们选择粗暴的方式进行断言然后对栈顶减1不用去处理本来的数据。
5判空
bool stackEmpty(stack* p)
{assert(p);return p-top0;
}
此处我们只想要判断栈顶处是否为0如果为0则说明顺序表为空否则顺序表不为空我们使用了bool类型C语言中并没有布尔类型所以我们要引头文件stdbool.h。
6求栈顶元素
datetype stackTop(stack* p)
{assert(p);assert(!stackEmpty(p));return p-a[p-top-1];
}
断言p以及断言顺序表不为空返回栈顶的值即可。
7求数据个数
int stackSize(stack* p)
{assert(p);return p-top;
}
8销毁栈
void stackDestroy(stack* p)
{assert(p);free(p-a);p-a NULL;p-capacity 0;p-top 0;
}
我们使用malloccallocrealloc申请的空间我们都必须使用free进行销毁。 源码
stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includeassert.h
#includestdbool.h
#includestdlib.htypedef int datetype;typedef struct Stack
{datetype* a;int capacity;int top;
}stack;
//初始化
void stackInit(stack* p);
//销毁
void stackDestroy(stack* p);
//入栈
void stackPush(stack* p, datetype x);
//出栈
void stackPop(stack* p);
//取栈顶数据
datetype stackTop(stack* p);
//数据个数
int stackSize(stack* p);
//判断是否为空
bool stackEmpty(stack* p);
stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#includestack.h
void stackInit(stack* p)
{assert(p);p-a NULL;p-capacity 0;p-top 0;
}
void stackPush(stack* p,datetype x)
{assert(p);if (p-capacity p-top){int newCapacity p-capacity 0 ? 4 : 2 * p-capacity;datetype* tmp (datetype*)realloc(p-a, newCapacity * sizeof(datetype));if (tmp NULL){perror(realloc);exit(-1);}p-a tmp;p-capacity newCapacity;}p-a[p-top] x;p-top;
}void stackPop(stack* p)
{assert(p);assert(!stackEmpty(p));p-top--;
}void stackDestroy(stack* p)
{assert(p);free(p-a);p-a NULL;p-capacity 0;p-top 0;
}datetype stackTop(stack* p)
{assert(p);assert(!stackEmpty(p));return p-a[p-top-1];
}bool stackEmpty(stack* p)
{assert(p);return p-top0;
}
int stackSize(stack* p)
{assert(p);return p-top;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includestack.h
void test()
{stack st;stackInit(st);stackPush(st, 1);stackPush(st, 2);stackPush(st, 3);stackPush(st, 4);printf(%d , stackTop(st));stackPop(st);printf(%d , stackTop(st));stackPop(st);stackPush(st, 5);stackPush(st, 6);//int ret stackTop(st);//printf(%d, ret);while (!stackEmpty(st)){printf(%d ,stackTop(st));stackPop(st);}stackDestroy(st);}int main()
{test();return 0;
}
通过测试我们发现无论什么时候出栈出几个数据都符合栈的特点先进后出后进先出。 总结
今天我通过顺序表的结构来实现了栈向展示并讲解了栈的概念、结构与各接口的实现过程与作用原理当然也可以通过链表的方式来实现希望大家可以多多尝试。
