wordpress访问量,佛山市seo推广联系方式,上海网站建设海淘科技,网站空间是不是服务器受限线性表
对于一般线性表#xff0c;虽然必须通过遍历逐一查找再对目标位置进行增、删和查操作#xff0c;但至少一般线性表对于可操作元素并没有限制。说到这里#xff0c;大家应该明白了#xff0c;所谓的受限线性表#xff0c;就是可操作元素受到了限制。 受限线性表…受限线性表
对于一般线性表虽然必须通过遍历逐一查找再对目标位置进行增、删和查操作但至少一般线性表对于可操作元素并没有限制。说到这里大家应该明白了所谓的受限线性表就是可操作元素受到了限制。 受限线性表可分为栈Stack和队列Queue如下图所示这是比较特珠但很重要的数据结构一定要掌握。
1.栈
栈讲究的是“先进后出”即最先进栈的数据最后出栈。就像箱子我们整理东西时先放进箱于里的东西会被压在最下面后放进箱子里的东西会被放在最上面等到从箱子里往外拿东西时需要先把上面的东西拿出来才能拿到箱子最底下的东西这就叫“先进栈的后出栈后进栈的先出栈”。这与线性表分为顺序表和链表一样栈也分为顺序栈和链栈。
(1)顺序栈
顺序栈也属于线性存储结构而且和顺序表的数组结构极为相似如下图所示。 可以看出在这个数组中我们先把1放了进去然后依次是2、3和4当我们要取出1时必须先依次取出4、3和2。
(2)链栈
链栈的原理和顺序核很相似。顺序栈是将顺序表的一端封死作为栈底将另一端作为栈顶。链栈也是如此它把链表一端尾部封死作为栈底将另一端头部作为栈顶如下图所示。 可以看出链栈其实就是一个只能用头插法插入和删除元素的链表。问题来了如此限制链表有什么好处呢有那就是可以提高效率。在我们只开放链表头部进行插入和删除元素的同时避免了大量遍历链表所带来的耗时操作。
2. 队列
队列讲究的是“先进先出”即最先进队列的数据最先出队列。队列就像一根吸管队列里的元素就像珍珠奶茶里的珍珠——最先进入吸管的珍珠将最先离开吸管当然是被你吃了。这就叫“先进队的先出队后进队的后出队”。 生活中的队列应用也很多如排队买票。前面的人比你先到因此他先买然后才轮到你。队列和栈一样也可以分为顺序队列和链式队列。
(1)顺序队列
顺序队列其实就是在顺序表上实现队列结构。它和顺序栈的区别是顺序栈是一边开口而顺序队列是两边开口如下图所示。 聪明的读者肯定会发现一个问题顺序队列一直在往前“蹭”前面的存储空间无法再次使用这样会造成很大的空间浪费而且还很容易导致数组溢出引发错误。 那应该怎么办呢读者肯定以为笔者要讲链式队列吧然而并不是。不知读者是否还记得前面我们讲过的“环”环就是解决这个问题的基本思路。我们完全可以用一个环状的顺序队列把它的头尾巧妙地连接在一起即可实现存储空间的循环使用如下图所示。 剩下的就让 top 和rear 这两个指针像仓鼠玩跑轮一样去工作就可以了。
(2)链式队列
链式队列也叫链队列可以说是单链表和顺序队列的结合体它的初始状态如下图所示。 此时队列里什么都没有因此top 和 rear 指针同时指向了头节点。当我们试图添加新的数据元素时需要按照以下3 步来操作 1创建一个该数据元素的新节点。 2将队尾指针 rear所指向的节点的指针指向新节点。 3将队尾指针 rear 指向新节点。 当我们试图删除数据元素时可以按照以下3步来操作 1创建一个新指针p指向将出队的节点首元节点。 2将头节点的指针指向p指针所指向节点的下一个节点。 3释放p指针所指向的节点回收内存空间。 如果该链式队列没有头节点则第1步应改为将队头指针 top指向p指针所指向节点的下一个节点。
