网站管理端怎么做,信息发布型企业网站的特点,网页设计和网站开发的区别,wordpress 大型站本文的所有代码均由C编写 引用及参考资料#xff1a; 王道数据结构大话数据结构超硬核十万字#xff01;全网最全 数据结构 代码#xff0c;随便秒杀老师/面试官#xff0c;我说的_hebtu666-CSDN博客 5 栈
5.1 引入
在前面学习线性表的时候#xff0c;我们给出了线性表的… 本文的所有代码均由C编写 引用及参考资料 王道数据结构大话数据结构超硬核十万字全网最全 数据结构 代码随便秒杀老师/面试官我说的_hebtu666-CSDN博客 5 栈
5.1 引入
在前面学习线性表的时候我们给出了线性表的定义
线性表是具有相同数据类型的n个数据元素的有限序列。其中n为表长当n0的时候线性表是一个空表。若用L命名线性表即L(a1,a2,a3….,an)L (a_1,a_2,a_3….,a_n)L(a1,a2,a3….,an)。
实际上栈Stack是一类特殊的线性表它只允许在一端进行插入或删除操作。栈在一些其他科目中也被叫做堆栈。这样从数学角度来看仿佛很抽象能不能有一个形象地比喻呢 这里我们引入的是《大话数据结构》中的例子。 假设现在有一把手枪从结构上看一颗子弹打出去后另一颗子弹就会上膛但是如果上膛的是一颗坏掉的子弹那手枪能够换下一颗吗如果在不自己手动拆出弹夹更换的情况下是做不到的。 这里引入的第二个例子是王道数据结构视频的例子。 当在不抱起所有盘子且不移动其他盘子的情况下如果我们要拿起一个盘子或者放一个盘子只能在最上面下手吧。同样的如果我们要吃一支烤串在不咬烂肉的情况下想要吃到第二个肉必须先吃第一个再吃第二个吧。 由上面的例子可以总结出栈实际上是一个先进后出的结构且只能在一端进行操作。
5.2 重要术语说明
如果栈内没有任何一个元素我们称其为空栈。 我们把允许插入和删除的那一端叫做栈顶另一端叫做栈底不含任何数据元素的栈叫做空栈。由此我们可以发现第一个进去的元素在最底下所以栈又称为后进先出(Last In First Out)的线性表。我们也把栈的结构叫做LIFO结构。
栈的插入操作我们也叫进栈也称压栈或入栈。类似子弹入弹夹。
栈的删除操作我们也叫出栈也称弹栈。如同弹夹中子弹出夹。 5.3 进栈出栈变化形式
有些人受到固定思维意味栈中最先进栈的元素一定是最后出栈的其实不一定。比如123依次入栈那会有很多种结果。
第一种1、2 、3进再1 、2 、3出。第二种1进1出2进2出3进3出。第三种1进2进2出1出3进3出。第四种1进1出2进3进3出2出。第五种1进2进2出3进3出1出。
从这里我们可以看出三个元素就有5种变化那么当元素数目变多时变化就有可能更多。在考研或者其他面试中最喜欢的就是考查栈的合法出栈顺序所以这里一定要搞清楚。
5.4 栈的抽象数据类型
前面说过栈是一种特殊的线性表所以线性表中有的操作栈都有。需要注意的是前面我们在谈论基本操作的名称写法时说过名称一定要能让人看懂。在严蔚敏一版的教材中我们采用如下抽象数据结构。
ADT 栈(stack)
Data同线性表。元素具有相同的类型相邻元素具有前驱和后继关系。
OperationInitStack(*S):初始化操作建立一个空栈s。DestroyStack(*S):若栈存在则销毁它。ClearStack(*S):将栈清空。StackEmpty(S):若栈为空返回true否咋返回false。GetTop(S,*e):若栈存在且非空用e返回s的栈顶元素。Push(*S,e):若栈S存在插入新元素e则栈S中并成为栈顶元素。Pop(*S,e):删除栈S中栈顶元素并用e返回其值。StackLength(S):返回栈S的元素个数。
endADT5.5 顺序栈
5.5.1 顺序栈的定义
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{ElemType data[MaxSize]; //静态数组存放栈中元素int top; //栈顶指针
}SqStack;在栈的定义中我们用了top来指明栈顶元素在数组中的位置top就如同老师用的游标卡尺中的游标一般其可以来回移动但是游标不能超过尺即栈顶指针不能超过定义的数组容量。一般来说如果空栈意味着栈中没有元素此时我们的top -1。
在这里要科普一些关于栈顶指针和栈的一些知识。 栈顶指针也叫堆栈指针一般堆栈的栈底不能动所以数据入栈前要先修改堆栈指针使它指向新的空余空间然后再把数据存进去出栈的时候相反。 堆栈指针随时跟踪栈顶地址按先进后出的原则存取数据。 计算机中的堆栈主要用来保存临时数据局部变量和中断/调用子程序程序的返回地址。 ARM处理器中通常将寄存器R13作为堆栈指针SP。ARM处理器针对不同的模式共有 6 个堆栈指针SP其中用户模式和系统模式共用一个SP每种异常模式都有各自专用的R13寄存器SP。它们通常指向各模式所对应的专用堆栈也就是ARM处理器允许用户程序有六个不同的堆栈空间。这些堆栈指针分别为R13、R13_svc、R13_abt、R13_und、R13_irq、R13_fiq。 5.5.2 初始化以及判空
如果要对栈进行初始化根据上面说过top-1为空栈的情况我们可以写出如下所示的初始化代码
void InitStack(SqStack S)
{S.top -1;
}根据初始化的特点如果我们想要判断栈是否为空只需
bool StackEmpty(SqStack S)
{if(S.top-1)return true;elsereturn false;
}5.5.3 进栈操作
对于进栈操作push我们可以
bool Push(SqStack S,ElemType x)
{if(S.top MaxSize-1) //栈满报错return false;S.data[S.top] x; //移动堆栈指针并且给堆栈指针指向的栈顶元素赋值return true;
}5.5.4 出栈操作
对于出栈操作pop我们可以
bool Pop(SqStack S,ElemType x)
{if(S.top-1)return false;x S.data[S.top--]; //先返回元素给x再移动堆栈指针return true;
}这里要注意的是我们并没有把出栈元素的数据清空所以虽然出栈但是只是逻辑上被删除了实际上数据还残留在内存中。
5.5.5 读栈操作
对于读栈一般我们都是读栈顶元素。如下所示
bool GetTop(SqStack S,ElemType x)
{if(S.top -1)return false;x S.data[S.top];return true;
}5.5.6 关于栈顶指针的指向问题
有时候栈顶指针会在初始化的时候不是指向-1而是指向0而当栈满的时候不是指向栈顶元素而是指向栈顶元素的下一位此时上面的判空、初始化、读栈、进栈操作和出栈操作中代码都会有些小小的不一样需要大家注意这在考试中可能会出现。
5.5.7 共享栈
顾名思义共享栈就是两个栈共用一个栈空间。
在顺序栈的设计过程中我们可以发现其用的是静态数组来分配的栈空间这就导致可能栈空间内存不足如果要使用动态数组的方式去分配内存这么做很麻烦。
但是两个栈就不一样了我们可以把两个栈用一个很大的数组放着其中这个数组是两个栈的共享栈空间。如果你用的多我用的少那我就多给你一点空间这样很容易协调空间的分配。
两个栈的空间放置如下我们可以看成是两个栈顶面对面放置。 两个栈的栈指针移动时如下所示 共享栈代码如下
//定义共享栈
#define MaxSize 10
typedef struct
{ElemType data[MaxSize];int top0;int top1;
}shstack;//初始化共享栈
void InitStack(ShStack S)
{S.top0 -1;S.top1 MaxSize;
}如果栈满了其条件是两指针对应的栈谁再进栈一次都会重合。
top0 1 top15.6 链栈
5.6.1 概述
我们把栈的链式存储结构叫做链栈。
相对于链栈来说我们需要考虑第一个问题
我们要把栈顶放在链表的头部还是尾部。
对于链表来说链表不管是带头结点还是不带头结点都带有一个头指针如果栈顶不处于链表头部的话那么我们就要再声明一个指针作为栈顶指针这显然很麻烦。既然这样我们不如把栈顶指针和头指针合二为一即可。需要注意的是合二为一的前提是栈顶实际上就是第一个结点如果你带头结点那么第一个结点就不能放元素了这不太符合栈的定义了所以在链栈中我们一般不会再用到学习单链表所用到的头结点了。
对于链栈就不存在顺序栈那样空间不足的问题了除非是内存不足。
5.6.2 链栈的定义
链栈中的定义在不同的书上有不同的方式如果你想记录栈的长度那么我推荐你使用下面的方式
//结点定义
typedef struct StackNode
{int data;StackNode* next;
}StackNode,*LinkStackptr;//链栈定义
typedef struct LinkStack
{LinkStackptr top;//指针int Length;
}LinkStack5.6.3 链栈的初始化
对于链栈初始化就是把传入的链栈指向空并且设置栈长为0。
//初始化
bool LinkStackInit(LinkStack S)
{S.top NULL;S.Length 0;return true;
}5.6.4 链栈的进栈
对于链栈的进栈考虑带头结点的情况我们可以发现实际上就是指定只能在头结点后插这样的话根据之前在单链表学过的后插操作可以自行写出代码这里不再赘述。
但是如果是不带头结点那么我们可以如下所示
//进栈
bool push(LinkStack S, int e)
{ //生成新节点并且把添加值加入StackNode *newnode new StackNode;newnode-data e;//开始添加结点变换指针顺序newnode-next S.top;S.top newnode;//添加完成,计入表长S.Length;return true;
}5.6.5 链表的出栈
对于不包含头结点链表的出栈无非就是对栈顶指针后的结点删除需要注意的是当栈中结点剩余0和1的时候我们需要设置额外情况。
//弹栈
bool pop(LinkStack S, int e)
{if (S.Length 0) {return false;}//生成指针用于记录删除结点所在地址StackNode *p new StackNode;//返回删除结点中的值e S.top-data;//将指针移向栈顶p S.top;//栈顶位置改变S.top S.top-next;//释放原栈顶delete(p);//表长改变S.Length--;return false;
}5.6.6 输出链栈
输出链栈也很容易只需指定一根指针从栈顶扫向栈底即可。扫的时候依次输出每个结点中的数据。
bool CoutStack(LinkStack S)
{StackNode* p S.top;cout 由栈顶到栈底 ;while (p) {cout p-data endl;p p-next;}cout endl;return true;
}5.6.7 输出栈顶元素
//输出栈顶元素
bool GetTop(LinkStack S, int e)
{if (S.Length 0)return false;e S.top-data;return true;
}5.7 链栈和顺序栈的对比
对比顺序栈和链栈它们的时间复杂度一样均为O(1)。对于空间性能顺序栈的空间是死的是固定的而对于链栈虽然空间没有限制但是也可能面临内存不足的问题。
