郑州快速排名优化网站,wordpress go跳转页面,wordpress导入sql,深圳网站建设方案优化我们在学习过顺序表和链表之后#xff0c;了解了使用数组存储数据#xff0c;使用结构体来存储数据和有关的指针#xff0c;这些都是底层的东西#xff0c;链表是靠指针的链接#xff0c;顺序表是靠数组的下标才能得以实现增删查改。众多数据结构其实底层都离不开数组了解了使用数组存储数据使用结构体来存储数据和有关的指针这些都是底层的东西链表是靠指针的链接顺序表是靠数组的下标才能得以实现增删查改。众多数据结构其实底层都离不开数组指针和结构体今天我们要学习的栈也不例外话不多说直接上正菜
1. 栈的概念 在这里我先给大家栈的图解通过图来理解概念。
1.1 栈的组成 栈黑色边框及其内部空间为栈 栈顶开口的方向叫做栈顶 栈底闭口的方向叫做栈底 栈内元素蓝色长方形 1.2 栈的进出规则先进后出 首先我们往栈里存入或者删除数据的时候只能在栈顶操作也就是咱们俗话说的从栈顶这一头进行增删的操作那么我们入栈的顺序是1-2-3-4的时候出栈的顺序就是4-3-2-1了。 我们不可以在栈底或者中间直接拿出来数据只能在栈顶拿谁在栈顶先拿谁肯定是最后入栈的数据在栈顶。 所以栈的进出规则是 先进后出 2. 栈的底层架构的选择 我们知道栈的进出规则是先进后出我们秉持着这一理念就可以在顺序表或者链表中进行改造增删查改的规则使其变成栈。那我们该如何选择呢是选择顺序表还是链表呢
2.1 栈的架构为顺序表文末有源码是使用方案
2.1.1 栈和顺序表的比对 首先我们看一下用顺序表来构造栈是如何构造的。 当我们的栈是顺序表构造的时候我们会发现栈底就是顺序表的表头栈顶是顺序表的表尾。那通过顺序表如何对栈进行插入数据和删除数据呢 2.1.2 栈的插入图解 我们对栈的插入一定是在栈顶这边插入那我们对比一下这两张图在栈顶插入就相当于顺序表的尾插对吧我们只需要尾插顺序表就可以完成栈的插入元素了。 2.1.3 栈的删除 栈是只能对栈顶进行增加和删除的所以我们只能在栈顶删除元素那是不是就相当于顺序表的尾删。 所以对于栈的删除我们只需要尾删顺序表就可以了。 2.2 栈的架构为链表 而当我们使用链表作为栈的架构什么样的链表才可以使栈的增添和删除容易呢让我们看图一起寻找吧
2.2.1 单链表构造栈舍弃方案 当我们使用单链表构造栈的时候栈的插入和删除都相当于对单链表的尾部进行操作插入还好直接尾插就行而删除的话删除当前节点就找不到前一个节点了我们还需要保存前一个节点这样很麻烦所以这个方案是舍弃的。 2.2.2 双向链表构造栈舍弃方案 对于双向链表很明显是比单链表好用在出栈的操作我们应该先保存栈顶元素的下一个元素的位置也就是我们要删除图中的3应该先保存2的位置如果我们不保存2的位置直接删除3那么就找不到2的位置了。所以保存2的位置之后删除3再将指向3的指针 重新指向2就可以了。这个方法很明显比单链表好用但是都没有顺序表构造的栈更方便直接大家可以下去尝试使用双向链表模拟实现栈。 最后下面我们来用代码模拟一下栈这里首推顺序表。
3. 栈的模拟实现源代码
3.1 栈的定义
typedef int STDataType;
//用顺序表模拟栈
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
3.2 栈的初始化
void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}
3.3 栈的销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}
3.4 入栈
void STPush(ST* ps, STDataType x)
{assert(ps);// 11:40if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}
3.5 取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);// assert(ps-top 0);return ps-a[ps-top - 1];
}
3.6 出栈
void STPop(ST* ps)
{assert(ps);// assert(ps-top 0);--ps-top;
}
3.7 栈的元素个数
int STSize(ST* ps)
{assert(ps);return ps-top;
}
3.8 栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
3.9 用到的头文件
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h 以上就是栈的模拟实现了下面我们做几个关于栈的习题。
4. 栈的习题
4.1 下列关于栈的叙述正确的是 A.栈是一种“先进先出”的数据结构 B.栈可以使用链表或顺序表来实现 C.栈只能在栈底插入数据 D.栈不能删除数据
答案B
A错误栈是一种先进后出的数据结构队列是先进先出的。
B正确顺序表和链表都可以用来实现栈不过一般都使用顺序表因为顺序表简单。
C错误栈只能在栈顶进行输入的插入和删除操作。
D错误栈是有入栈和出栈的操作出栈就是从栈中删除一个元素。
4.2 一个栈的入栈序列为ABCDE则不可能的出栈序列为 A.ABCDE B.EDCBA C.DCEBA D.ECDBA
答案D
画图解决问题
4.3. 链栈与顺序栈相比比较明显的优点是 A.插入操作更加方便 B.删除操作更加方便 C.入栈时不需要扩容
答案C
A错误如果是链栈在入栈的时候直接尾插就行了跟顺序栈没有多大区别。
B错误如果是链栈在出栈的时候需要继续前一个节点的位置才行要不然无法继续出栈 而顺序栈则可以通过下标快速找到。链表的操作比顺序表复杂因此使用顺序结构实现栈更简单。
C正确链式结构实现栈时每次入栈相当于链表中头插一个节点没有扩容一说。 以上就是本次博文的分享谢谢大家支持
