网站分享对联广告,网页设计报价,义乌外贸公司网站,网站搭建维护淄博个人主页 #xff1a; 个人主页 个人专栏 #xff1a; 《数据结构》 《C语言》 文章目录 前言一、栈的实现思路1. 结构的定义2. 初始化栈(StackInit)3. 入栈(StackPush)4. 出栈(StackPop)5. 获取栈顶元素(StackTop)6. 检查栈是否为空(StackEmpty)7. 销毁栈(StackDestroy) 二、… 个人主页 个人主页 个人专栏 《数据结构》 《C语言》 文章目录 前言一、栈的实现思路1. 结构的定义2. 初始化栈(StackInit)3. 入栈(StackPush)4. 出栈(StackPop)5. 获取栈顶元素(StackTop)6. 检查栈是否为空(StackEmpty)7. 销毁栈(StackDestroy) 二、代码实现总结 前言
栈一种特殊的线性结构其只允许在一端进行插入删除数据。允许操作数据的一端被称为栈顶另一端被称为栈底。 本篇博客将要实现的是数组栈。 一、栈的实现思路
对于栈的特殊性用数组(在数组尾部插入删除数据) 和 链表(头插头删数据)实现栈的时间复杂度都是O(1)难度不大。 数组栈的优劣 优
数组支持随机访问(用下标访问数据)许多算法需要随机访问的支持如二分法…缓存利用率高
劣
空间不够时要扩容有时会造成空间浪费
1. 结构的定义
栈的结构非常简单 一个指向动态开辟空间的指针一个记录实际空间大小的变量一个记录栈顶元素的下标即可。 typedef int STDataType;typedef struct Stack
{STDataType* data;int top;//栈顶下标int capacity;//空间大小
}Stack;2. 初始化栈(StackInit)
data指针指向动态开辟的空间capacity记录此时空间大小top置为0。
top 置0表示栈顶数据将要插入的位置。top 置-1表示此时栈顶数据的位置。
这里采用top 置0。 //初始化栈#define SIZE 4void StackInit(Stack* ps)
{assert(ps);ps-data (STDataType*)malloc(sizeof(STDataType) * SIZE);if (ps-data NULL){perror(malloc);exit(-1);}ps-top 0;ps-capacity SIZE;
}3. 入栈(StackPush)
因为top初始化为0所以直接在top下标处入数据即可。但要注意在入数据前要检查容量如果top capacity 要扩容。
此处检查容量的操作可以封装成一个函数但没必要因为栈的操作只有入栈要检查容量其它的操作并不需要检查容量封装成一个函数反而效率减低了(函数的调用要形成函数栈帧)。 //入栈
void StackPush(Stack* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){STDataType* tmp (STDataType*)realloc(ps-data, sizeof(STDataType) * (ps-capacity * 2));if (tmp NULL){perror(realloc);exit(-1);}ps-data tmp;ps-capacity * 2;}ps-data[ps-top] x;ps-top;
}4. 出栈(StackPop)
top 表示的是栈顶数据将要入栈的位置那么出栈操作只需要让top 减 1即可。(下次入栈数据会直接覆盖) 但要注意top 0 时表示栈内没有数据不能进行出栈操作。
出栈操作不能获取数据 //出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-top ! 0);ps-top--;
}5. 获取栈顶元素(StackTop)
top 指向的是数据将要入栈的位置也就是栈顶数据的下一个位置。 那么要获取栈顶数据只需要读取top - 1处即可。但要注意如果top 0那么top - 1 -1会越界访问所以top 0 时不能获取栈顶元素。 //获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-data[ps-top - 1];
}6. 检查栈是否为空(StackEmpty)
top 指向的是数据将要入栈的位置其数值也表示栈内数据个数。 所以我们只需要进行 top 0 的判断即可知道栈是否为空。
//检查栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}7. 销毁栈(StackDestroy)
free掉动态开辟的空间使capacity 置 0top 置 0。
//销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-data);ps-top 0;ps-capacity 0;
}二、代码实现
Stack.h 文件存放的是函数的声明头文件的引用结构体的定义 Stack.c 文件存放的是函数的实现
//Stack.h 文件#pragma once#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h#define SIZE 4typedef int STDataType;typedef struct Stack
{STDataType* data;int top;int capacity;
}Stack;//初始化栈
void StackInit(Stack* ps);//入栈
void StackPush(Stack* ps, STDataType x);//出栈
void StackPop(Stack* ps);//获取栈顶元素
STDataType StackTop(Stack* ps);//检查栈是否为空
bool StackEmpty(Stack* ps);//销毁栈
void StackDestroy(Stack* ps); //Stack.c 文件#include Stack.h//初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-data (STDataType*)malloc(sizeof(STDataType) * SIZE);if (ps-data NULL){perror(malloc);exit(-1);}ps-top 0;ps-capacity SIZE;
}//入栈
void StackPush(Stack* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){STDataType* tmp (STDataType*)realloc(ps-data, sizeof(STDataType) * (ps-capacity * 2));if (tmp NULL){perror(realloc);exit(-1);}ps-data tmp;ps-capacity * 2;}ps-data[ps-top] x;ps-top;
}//出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-top ! 0);ps-top--;
}//获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-data[ps-top - 1];
}//检查栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}//销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-data);ps-top 0;ps-capacity 0;
}总结
以上就是我对于栈的实现。
