网站出现转站怎么办,找工作求职,古镇网站建设制作,网站500错误是什么意思目录 1. 前言2. 栈2.1 栈的概念及结构2.2 如何实现栈2.3 数组栈实现2.3.1 top怎么确定2.3.2 栈顶插入2.3.2.1 栈顶插入分析2.3.2.2 栈顶插入代码实现 2.3.3 栈顶删除2.3.4 判空2.3.4.1 分析2.3.4.2 代码实现 2.3.5 栈的元素个数2.3.6 栈销毁2.3.7 栈访问数据 3. 源代码3.1 Stac… 目录 1. 前言2. 栈2.1 栈的概念及结构2.2 如何实现栈2.3 数组栈实现2.3.1 top怎么确定2.3.2 栈顶插入2.3.2.1 栈顶插入分析2.3.2.2 栈顶插入代码实现 2.3.3 栈顶删除2.3.4 判空2.3.4.1 分析2.3.4.2 代码实现 2.3.5 栈的元素个数2.3.6 栈销毁2.3.7 栈访问数据 3. 源代码3.1 Stack.h3.2 Stack.c3.3 test.c 1. 前言
在前面我们一起了解的数据结构有顺序表和链表这次来介绍栈。 与顺序表和链表相同的是栈也是常见的数据结构。而与前面两种不同的是它在农村种的存储接下来让我们一起来学习一下。
2. 栈
2.1 栈的概念及结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。
压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。
出栈栈的删除操作叫做出栈。出数据也在栈顶。
2.2 如何实现栈 那该如何实现栈呢 第一种使用数组栈 第二种使用链式栈
链表实现又分为双向链表和单链表。 双向链表实现栈顶可以是尾也可以是头。 单链表实现栈顶只能是头。 如果只选择一种来实现那必然是数组虽然有扩容但不是频繁扩容。还有另外一个优势它访问数据CPU高速缓存命中率比较高访问第一个后面都在缓存了。
2.3 数组栈实现
2.3.1 top怎么确定
我们需要考虑top怎么确定 如果top给0那么表示的是栈顶还是栈顶位置的下一个
如果空的时候top给的是0那么插入一个数据之后top也是0因为top指向栈顶。 此时就出现了歧义。top0是一个元素还是空区分不开。
那该怎么区分呢 第一种如果top指向栈顶元素那么top初始时给-1。 这种插入数据时 要先加加top再在这个位置赋值。
第二种指向栈顶元素的下一个。 此时top初始时就为0。 这种插入数据时 要先在这个位置赋值再加加top。
这里插入就取决于怎么初始化栈。
选择第二种来实现代码这种更简单。
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-top 0;//第二种
}2.3.2 栈顶插入
2.3.2.1 栈顶插入分析
插入的代码非常简单
pst-a[pst-top] x;pst-top;但是在插入之前要先判断一下栈有没有满满的化要进行扩容。
if (pst-top pst-capacity)但我们要初始时候有没有给空间如果有直接扩两倍没有就给初始值4。 使用一个三目表达式
int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;如果没有开空间就直接返回或者结束程序。
if (tmp NULL){perror(realloc fail);return;}2.3.2.2 栈顶插入代码实现
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}2.3.3 栈顶删除
删除很简单直接top–就行但减减之前判断一下top是不是0加一个断言就行。 代码实现
void STPop(ST* pst)
{assert(pst);// 不为空assert(pst-top 0);pst-top--;
}返回栈顶数据的代码:
STDataType STTop(ST* pst)
{assert(pst);// 不为空assert(pst-top 0);return pst-a[pst-top - 1];
}2.3.4 判空
2.3.4.1 分析
判空这里得看刚开始时初始时top为0就要判断top0。初始为-1那么就要判断top-1。 可以用if来判断
if (pst-top 0){return true;}else{return false;}但是有个更简单的bool类型返回就是真假利用返回值当结果就行直接返回pst-top 0。
2.3.4.2 代码实现
代码实现
bool STEmpty(ST* pst)
{assert(pst);/*if (pst-top 0){return true;}else{return false;}*/return pst-top 0;
}2.3.5 栈的元素个数
如果top是指向栈顶元素的下一个那么元素个数就是top。 如果top就是指向栈顶那么元素个数就是top1。
代码实现
int STSize(ST* pst)
{assert(pst);return pst-top;
}2.3.6 栈销毁
直接将元素都free掉再把它们都置为空。把栈顶和栈空间都置为0。
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}2.3.7 栈访问数据
因为栈是后进先出所以栈不能随便打印。 那怎么打印呢 判断栈是否为空然后从栈顶开始访问。 访问了栈顶元素要想访问下一个就要先将栈顶元素弹出直到栈为空就结束。
代码实现
while (!STEmpty(s)){printf(%d , STTop(s));STPop(s);}printf(\n);3. 源代码
3.1 Stack.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDataType;typedef struct Stack
{int* a;int top; // 标识栈顶位置的int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);bool STEmpty(ST* pst);
int STSize(ST* pst);
3.2 Stack.c
#includeStack.hvoid STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;// 表示top指向栈顶元素的下一个位置pst-top 0;// 表示top指向栈顶元素//pst-top -1;
}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);// 不为空assert(pst-top 0);pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);// 不为空assert(pst-top 0);return pst-a[pst-top - 1];
}bool STEmpty(ST* pst)
{assert(pst);/*if (pst-top 0){return true;}else{return false;}*/return pst-top 0;
}int STSize(ST* pst)
{assert(pst);return pst-top;
}3.3 test.c
#includeStack.hint main()
{ST s;STInit(s);STPush(s, 1);STPush(s, 2);STPush(s, 3);printf(%d , STTop(s));STPop(s);printf(%d , STTop(s));STPop(s);STPush(s, 4);STPush(s, 5);// 一 对 多// 入栈顺序 -- 出栈顺序while (!STEmpty(s)){printf(%d , STTop(s));STPop(s);}printf(\n);return 0;
} 文章转载自： http://www.morning.lkrmp.cn.gov.cn.lkrmp.cn http://www.morning.xfxnq.cn.gov.cn.xfxnq.cn http://www.morning.jrbyz.cn.gov.cn.jrbyz.cn http://www.morning.jrwbl.cn.gov.cn.jrwbl.cn http://www.morning.rpljf.cn.gov.cn.rpljf.cn http://www.morning.zfzgp.cn.gov.cn.zfzgp.cn http://www.morning.rbbzn.cn.gov.cn.rbbzn.cn http://www.morning.rwyw.cn.gov.cn.rwyw.cn http://www.morning.fsrtm.cn.gov.cn.fsrtm.cn http://www.morning.dmzmy.cn.gov.cn.dmzmy.cn http://www.morning.rnnwd.cn.gov.cn.rnnwd.cn http://www.morning.jgykx.cn.gov.cn.jgykx.cn http://www.morning.cyjjp.cn.gov.cn.cyjjp.cn http://www.morning.rgtp.cn.gov.cn.rgtp.cn http://www.morning.tmfm.cn.gov.cn.tmfm.cn http://www.morning.pttrs.cn.gov.cn.pttrs.cn http://www.morning.qlwfz.cn.gov.cn.qlwfz.cn http://www.morning.ysrtj.cn.gov.cn.ysrtj.cn http://www.morning.xwlmg.cn.gov.cn.xwlmg.cn http://www.morning.hqbk.cn.gov.cn.hqbk.cn http://www.morning.zrdqz.cn.gov.cn.zrdqz.cn http://www.morning.pmtky.cn.gov.cn.pmtky.cn http://www.morning.zlnkq.cn.gov.cn.zlnkq.cn http://www.morning.zqxhn.cn.gov.cn.zqxhn.cn http://www.morning.dswtz.cn.gov.cn.dswtz.cn http://www.morning.tjsxx.cn.gov.cn.tjsxx.cn http://www.morning.jkrrg.cn.gov.cn.jkrrg.cn http://www.morning.hmdyl.cn.gov.cn.hmdyl.cn http://www.morning.kwrzg.cn.gov.cn.kwrzg.cn http://www.morning.hwbf.cn.gov.cn.hwbf.cn http://www.morning.clqpj.cn.gov.cn.clqpj.cn http://www.morning.tlpgp.cn.gov.cn.tlpgp.cn http://www.morning.rnmmh.cn.gov.cn.rnmmh.cn http://www.morning.jwefry.cn.gov.cn.jwefry.cn http://www.morning.hbywj.cn.gov.cn.hbywj.cn http://www.morning.nzfjm.cn.gov.cn.nzfjm.cn http://www.morning.rrrrsr.com.gov.cn.rrrrsr.com http://www.morning.gnbfj.cn.gov.cn.gnbfj.cn http://www.morning.cryb.cn.gov.cn.cryb.cn http://www.morning.lyjwb.cn.gov.cn.lyjwb.cn http://www.morning.yrbp.cn.gov.cn.yrbp.cn http://www.morning.qsbcg.cn.gov.cn.qsbcg.cn http://www.morning.pmmrb.cn.gov.cn.pmmrb.cn http://www.morning.srwny.cn.gov.cn.srwny.cn http://www.morning.pcjw.cn.gov.cn.pcjw.cn http://www.morning.srrzb.cn.gov.cn.srrzb.cn http://www.morning.dmzmy.cn.gov.cn.dmzmy.cn http://www.morning.bryyb.cn.gov.cn.bryyb.cn http://www.morning.mjgxl.cn.gov.cn.mjgxl.cn http://www.morning.zplzj.cn.gov.cn.zplzj.cn http://www.morning.rjtmg.cn.gov.cn.rjtmg.cn http://www.morning.hwpcm.cn.gov.cn.hwpcm.cn http://www.morning.wjplr.cn.gov.cn.wjplr.cn http://www.morning.kqwsy.cn.gov.cn.kqwsy.cn http://www.morning.swimstaracademy.cn.gov.cn.swimstaracademy.cn http://www.morning.bpmfg.cn.gov.cn.bpmfg.cn http://www.morning.zkdbx.cn.gov.cn.zkdbx.cn http://www.morning.pumali.com.gov.cn.pumali.com http://www.morning.jqllx.cn.gov.cn.jqllx.cn http://www.morning.qfdyt.cn.gov.cn.qfdyt.cn http://www.morning.xknsn.cn.gov.cn.xknsn.cn http://www.morning.ktsth.cn.gov.cn.ktsth.cn http://www.morning.bnbzd.cn.gov.cn.bnbzd.cn http://www.morning.zcsyz.cn.gov.cn.zcsyz.cn http://www.morning.rkrcd.cn.gov.cn.rkrcd.cn http://www.morning.wyrkp.cn.gov.cn.wyrkp.cn http://www.morning.pqfbk.cn.gov.cn.pqfbk.cn http://www.morning.nrchx.cn.gov.cn.nrchx.cn http://www.morning.tkchm.cn.gov.cn.tkchm.cn http://www.morning.jglqn.cn.gov.cn.jglqn.cn http://www.morning.nxdqz.cn.gov.cn.nxdqz.cn http://www.morning.wbnsf.cn.gov.cn.wbnsf.cn http://www.morning.qpfmh.cn.gov.cn.qpfmh.cn http://www.morning.ymjgx.cn.gov.cn.ymjgx.cn http://www.morning.3dcb8231.cn.gov.cn.3dcb8231.cn http://www.morning.cwcdr.cn.gov.cn.cwcdr.cn http://www.morning.xhxsr.cn.gov.cn.xhxsr.cn http://www.morning.gxklx.cn.gov.cn.gxklx.cn http://www.morning.roymf.cn.gov.cn.roymf.cn http://www.morning.ylmxs.cn.gov.cn.ylmxs.cn
