【数据结构与算法】数据结构基础——栈和队列

目录栈和队列1. 栈1.1 栈的概念1.2 栈的实现方式分析1.3 栈的实现1.3.1 栈的初始化与销毁1.3.2 入栈与出栈1.3.3 栈的判空与有效元素个数1.3.4 栈顶元素1.4 栈的扩展1.4.1 两栈共享空间2. 队列2.1 队列的概念2.2 队列的实现方式分析2.3 队列的实现2.3.1 队列的初始化与销毁2.3.2 入队与出队2.3.3 队列的判空与队头队尾2.3.4 队列的有效元素个数2.4 循环队列栈和队列1. 栈1.1 栈的概念栈是一个特殊的线性表。栈只能在一端进行插入元素和删除元素的操作其中能进行操作的一端称为栈顶另一端称作栈底。其具有先进后出LIFO(last in first out)的性质栈的示意图 栈的示意图栈的示意图特殊术语入栈压栈在栈顶插入元素称为入栈出栈在栈顶删除元素称为出栈1.2 栈的实现方式分析【分析】我们根据栈的特殊性质需要选一个更适合的线性结构来实现它对比维度顺序表链表访问元素随机访问时间复杂度 O(1)遍历链表时间复杂度 O(n)插入/删除头部需要移动后面的所有元素O(n)只需修改指针O(1)插入/删除尾部若空间足够O(1)需要遍历到尾部O(n)单链表插入/删除中间需要移动元素O(n)找到位置后修改指针O(1)应用场景需要频繁随机访问、尾部操作密集、数据量相对固定需要频繁在任意位置插入删除、数据量变化大经过顺序表和链表的对比我们发现因为栈只能在栈顶尾部进行插入和删除操作顺序表在尾部的操作时间复杂度是O(1)而链表为O(n)。所以我们更适合使用顺序表来实现栈——【动态顺序表详解】——1.3 栈的实现实现方式顺序表实现动态分配内存typedefintSTDataType;typedefstructStack{STDataType*data;intsize;//顺序表有效元素个数intcapacity;//顺序表的容量}Stack;这里与动态顺序表的定义方式一样就不过多赘述了……1.3.1 栈的初始化与销毁栈的初始化时间复杂度O(1)voidStackInit(Stack*st){assert(st);st-dataNULL;st-sizest-capacity0;};这里关于assert(断言)防止空指针的解引用是一个好习惯可以防止很多莫名其妙的BUG栈的销毁时间复杂度O(1)voidStackDestroy(Stack*st){free(st-data);st-dataNULL;st-sizest-capacity0;}1.3.2 入栈与出栈入栈时间复杂度O(1)voidStackPush(Stack*st,STDataType x){assert(st);//判断容量是否足够 不够就扩容if(st-sizest-capacity){intnewcapacityst-capacity0?4:st-capacity*2;STDataType*tmp(STDataType*)realloc(st-data,newcapacity*sizeof(STDataType));if(tmpNULL)exit(-1);st-datatmp;st-capacitynewcapacity;}//插入元素st-data[st-size]x;st-size;}出栈时间复杂度O(1)voidStackPop(Stack*st){assert(st);assert(!empty(st));//判断栈非空st-size--;}1.3.3 栈的判空与有效元素个数判空时间复杂度O(1)boolempty(Stack*st){assert(st);returnst-size0;}有效元素个数时间复杂度O(1)intsize(Stack*st){returnst-size;}1.3.4 栈顶元素获取栈顶元素时间复杂度O(1)STDataTypetop(Stack*st){returnst-data[st-size-1];//从下标0开始存储元素}小结以上就是栈的基本的实现操作起来并不难不过再提醒一句因为实现数据结构用了大量指针所以在操作时一定要给指针判空和将没有用的指针及时置为NULL1.4 栈的扩展1.4.1 两栈共享空间根据栈的特性我们使用顺序表来实现栈。可是当栈的存储空间满了的时候我们需要去为这个栈扩容每次一满就要扩容这会有很多时间上的消耗。如果此时有两个相同类型的栈一个栈的存储空间快溢出了另外一个确还是有很多空闲的空间那我们何不根据栈的特性让两个栈合并使得空间的使用率更高两个栈合并实际上就是让两个栈共同使用同一个数组顺序表栈1的栈顶指针top1从-1开始栈2的栈顶指针top2从capacity数组的最大容量开始如下图当栈1需要入栈的时候top1指针就像右移栈2需要入栈时top2向左移那么要如何判断栈是否满了呢我们先看两个特殊情况【1】top1直接走到了最右边即两栈共享的空间全部都是栈1的元素此时情况如下此时如果栈满了就会满足top2 - top1 1【2】与第一种情况相反top2直接走到了最左边同理栈满时有top2 - top1 1。此时还有一种一般情况如下也是当top2 - top1 1时栈满了。所以得出结论当top2 - top1 1时栈就满了应用场景两栈共享空间一般在两个栈满足此消彼长的条件时使用即栈1元素增加时栈2的元素就要减少就像买股票当你买入了一份股票之后那一定有人持有的股票减少了相反的如果两个栈都是一直在插入元素的话空间很快就会满而设计这样的结构也就没意义了。两栈共享空间只是一个技巧适合两个栈存储的是相同的数据类型如果是不同的数据类型使用这种存储方式只会使操作更复杂2. 队列2.1 队列的概念队列是一种只能在一端插入数据另一端删除数据FIFO(first in first out)的特殊的线性表。其中插入数据的一端称为队尾删除数据的一端称作队头。队列结构示意图 队列结构示意图队列结构示意图关于队列的特殊术语队头队列出队一端的第一个元素队尾队列入队一端的第一个元素入队在队尾插入元素称为入队出队在队头删除元素称为出队2.2 队列的实现方式分析【分析】根据队列的特殊性质找一种最适合的数据结构来实现它这里再次拿到上面的对比表格对比维度顺序表链表访问元素随机访问时间复杂度 O(1)遍历链表时间复杂度 O(n)插入/删除头部需要移动后面的所有元素O(n)只需修改指针O(1)插入/删除尾部若空间足够O(1)需要遍历到尾部O(n)单链表插入/删除中间需要移动元素O(n)找到位置后修改指针O(1)应用场景需要频繁随机访问、尾部操作密集、数据量相对固定需要频繁在任意位置插入删除、数据量变化大队列与栈不同栈只能在栈顶的一端进行插入删除等操作。而队列是在队头和队尾两端都进行频繁的操作所以考虑两种线性表两端的操作经过对比发现顺序表和链表在头部操作和尾部操作都各自有优势所以我们此时就要考虑使用哪个可以优化或者更方便优化【优化】考虑到链表在尾部的操作是O(n)的原因是每次都需要遍历一遍链表才可以找到尾节点那何不干脆就直接将尾节点保存下来。将链表的尾节点保存下来之后就可以将链表尾部的操作优化到O(1)了【结论】使用链表来实现队列2.3 队列的实现队列的结构typedefintQDataType;//链表节点的结构typedefstructQueueNode{QDataType data;structQueueNode*next;}QueueNode;//队列的结构typedefstructQueue{QueueNode*phead;//指向队列的头节点QueueNode*ptail;//指向队列的尾节点}Queue;2.3.1 队列的初始化与销毁队列的初始化voidQueueInit(Queue*pq){assert(pq);pq-pheadp-ptailNULL;}队列的销毁voidQueueDestory(Queue*pq){assert(pq);QueueNode*pcurpq-phead;while(pcur){QueueNode*pnextpcur-next;free(pcur)pcurpnext;}//最后将头指针和尾指针置为NULL 防止野指针pq-pheadpq-ptailNULL;}【注意】销毁队列后要记得将phead和ptail置为NULL防止野指针2.3.2 入队与出队入队voidpush(Queue*pq,QDataType x){assert(pq);//动态申请节点QueueNode*newNode(QueueNode*)malloc(sizeof(QueueNode));if(newNodeNULL){perror(malloc fail);exit(-1);}newNode-datax;newNode-nextNULL;//如果队列不为空if(pq-phead){pq-ptail-nextnewNode;pq-ptailnewNode;}else{//队列为空pq-pheadpq-ptailnewNode;}}出队voidpop(Queue*pq){assert(pq);assert(!empty(pq));//当队列只有一个节点时if(pq-pheadpq-ptail){free(pq-phead);pq-pheadpq-ptailNULL;}else{QueueNode*pnextpq-phead-next;free(pq-phead);pq-pheadpnext;}}这里要注意出队是要分两种情况【1】当队列只有一个节点时【2】当队列有多个节点时2.3.3 队列的判空与队头队尾//判空boolempty(Queue*pq){returnpq-pheadNULL;}//返回队头元素QDataTypeQueueFront(Queue*pq){assert(pq);assert(!empty(pq));returnpq-phead-data;}//返回队尾元素QDataTypeQueueback(Queue*pq){assert(pq);assert(!empty(pq));returnpq-ptail-data;}2.3.4 队列的有效元素个数intsize(Queue*pq){assert(pq);QueueNode*pcurphead;intsize0;while(pcur){size;pcurpcur-next;}returnsize;}读到这里可能就会有读者有疑惑前面所有的操作时间复杂度都是O(1)怎么到这里时间复杂度就变成O(n)了或许有的人会觉得这就是链表的缺陷是不可更改的但是优化的方法其实很简单。既然前面队列的结构都已经维护头指针和尾指针那干脆就再维护一个队列的长度但是维护一个size就意味着代码会更复杂所以也需要分情况来定义和维护【1】如果在不需要频繁的获取队列的长度的情况下就继续使用之前的方法【2】如过需要频繁获取队列的长度就再维护一个队列长度sizetypedefstructQueue{QueueNode*phead;//指向队列的头节点QueueNode*ptail;//指向队列的尾节点intsize;}Queue;维护 s i z e 的版本 维护size的版本维护size的版本2.4 循环队列引入上文说到实现队列这个数据结构时使用链表实现会更好。原因在于使用顺序表实现队列的优化没有链表好但是使用顺序表来实现队列其实也是有它自己的优化方式的顺序表示实现普通队列如下是一个使用顺序表实现队列的结构初始时定义队头指针front和队尾指针rear指向顺序表的开头上文中提到使用顺序表实现队列最大的问题就在于顺序表头部操作的时间复杂度为O(n)也就是出队需要花费很多时间。但是其实是因为顺序表每次进行头部操作时要移动后面的元素才使得时间效率低所以就在这里对头部操作的优化对于每次出队只需将front指针向后移动即可顺序表实现循环队列到这里用顺序表实现队列在时间上的问题解决了但是此时又发现当rear指针走到顺序表的最后时队列就算满了而队列的前面还有很多的空闲的位置没有使用这样就导致了很多的空间浪费此时就应该想一个方法使得顺序表前面的空间也可以被使用。将队列的整体看成是一个环当rear或front要越界的时候再让它们跳回到顺序表的起始位置就跟一个环一样实现方式每当入队完成时(push)rear (rear 1) % size每当出队完成时(pop)front (front 1) % size【注】size是顺序表的长度循环队列初始状态 循环队列初始状态循环队列初始状态由上述可知当队列为空时front rear再看当队列满了的时候此时的判断条件还是front rear这样的话当front指针等于rear指针时根本就不知道队列此时是空的还是满的所以还需要修改。在顺序表中一直保留一个位置不使用此时判断队列为满的条件就变成了front - rear 1特别的如果需要队列的有效元素的个数的话int length (rear - front size) % size循环队列的代码实现typedefstruct{int*data;intcapacity;intfront;intrear;}MyCircularQueue;//初始化MyCircularQueue*myCircularQueueCreate(intk){//创建循环队列MyCircularQueue*cq(MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq-dataNULL;cq-frontcq-rear0;//分配内存int*tmp(int*)malloc((k1)*sizeof(int));if(!tmp)exit(-1);cq-datatmp;cq-capacityk1;returncq;}//入队 如果入队成功返回true反之返回falseboolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){assert(obj);intsizeobj-capacity;//如果队列满了 就返回falseif((obj-rear1)%sizeobj-front){returnfalse;}else{obj-data[obj-rear]value;obj-rear(obj-rear1)%size;//更新rear的值returntrue;}}//出队 如果出队成功返回true反之返回falseboolmyCircularQueueDeQueue(MyCircularQueue*obj){assert(obj);intsizeobj-capacity;if(obj-rearobj-front){returnfalse;}else{obj-front(obj-front1)%size;returntrue;}}//返回队列头部元素intmyCircularQueueFront(MyCircularQueue*obj){assert(obj);if(obj-rearobj-front){return-1;}else{returnobj-data[obj-front];}}//返回队列队尾元素intmyCircularQueueRear(MyCircularQueue*obj){assert(obj);intsizeobj-capacity;if(obj-rearobj-front){return-1;}else{returnobj-data[(obj-rear-1size)%size];}}//判断是否为空队列boolmyCircularQueueIsEmpty(MyCircularQueue*obj){assert(obj);returnobj-frontobj-rear;}//判断队列是否满了boolmyCircularQueueIsFull(MyCircularQueue*obj){assert(obj);intsizeobj-capacity;return(obj-rear1)%sizeobj-front;}//销毁队列voidmyCircularQueueFree(MyCircularQueue*obj){assert(obj);free(obj-data);obj-dataNULL;obj-rearobj-frontobj-capacity0;free(obj);}