企业网站优化服务公司,怎么做外国网站卖东西,整合营销传播简称,设计网站高级感前言栈和队列是一对好兄弟#xff0c;前面我们介绍过数据结构与算法—栈详解#xff0c;那么栈的机制相对简单#xff0c;后入先出#xff0c;就像进入一个狭小的山洞#xff0c;山洞只有一个出口#xff0c;只能后进先出(在外面的先出去)。而队列就好比是一个隧道#…前言栈和队列是一对好兄弟前面我们介绍过数据结构与算法—栈详解那么栈的机制相对简单后入先出就像进入一个狭小的山洞山洞只有一个出口只能后进先出(在外面的先出去)。而队列就好比是一个隧道后面的人跟着前面走前面人先出去(先入先出)。日常的排队就是队列运转形式的一个描述所以队列的核心理念就是先进先出队列的概念队列是一种特殊的线性表特殊之处在于它只允许在表的前端front进行删除操作而在表的后端rear进行插入操作和栈一样队列是一种操作受限制的线性表。进行插入操作的端称为队尾进行删除操作的端称为队头。同时阅读本偏文章最好先弄懂顺序表的基本操作和栈的数据结构学习效果更佳队列介绍基本属性队头front删除数据的一端。对于数组从后面插入更容易前面插入较困难所以一般用数组实现的队列队头在前面。(删除直接index游标前进不超过队尾即可)。而对于链表。插入删除在两头分别进行那么头部(前面)删除尾部插入是最方便的选择队尾rear插入数据的一端同上在数组和链表中通常均在尾部位置。当然其实数组和链表的front和rear还有点小区别后面会具体介绍。enQueue(入队)在队尾rear插入元素deQueue(出队)在对头front删除元素普通队列按照上述的介绍我们很容易知道数组实现的方式。用数组模拟表示队列。要考虑初始化插入问题。初始化数组的front和rear都指向0.入队队不满数组不越界先队尾位置传值再队尾下标1出队队不空先取队头位置元素在队头1但是很容易发现问题每个空间域只能利用一次。造成空间极度浪费。并且非常容易越界循环队列针对上述的问题。有个较好的解决方法就是对已经申请的(数组)内存重复利用。这就是我们所说的循环队列。而数组实现的循环队列就是在逻辑上稍作修改。我们假设(约定)数组的最后一位的下一个index是首位。因为我们队列中只需要front和tail两个指标。不需要数组的实际地址位置相关数据。和它无关。所以我们就只需要考虑尾部的特殊操作即可。初始化数组的front和rear都指向0.入队队不满先队尾位置传值再rear(rear 1) % maxsize;出队队不空先取队头位置元素front(front 1)%maxsize;是否为空return rear front;大小return (rearmaxsize-front)%maxsize;这里面有几个大家需要注意的就是指标相加如果遇到最后需要转到头的话。可以判断是否到数组末尾位置。也可以直接1求余。其中maxsize是数组实际大小。链式实现对于链表实现的队列要根据先进先出的规则考虑头和尾的位置我们知道队列是先进先出的对于链表我们能采用单链表尽量采用单链表能方便尽量方便同时还要兼顾效率。方案一 如果队头设在链表尾队尾设在链表头。那么队尾进队插入在链表头部插入没问题。容易实现但是如果队头删除在尾部进行如果不设置尾指针要遍历到队尾但是设置尾指针删除需要将它指向前驱节点那么就需要双向链表。都挺麻烦的。方案二但是如果队头设在链表头队尾设在链表尾部那么队尾进队插入在链表尾部插入没问题(用尾指针可以直接指向next)。容易实现如果队头删除在头部进行也很容易就是我们前面常说的头节点删除节点。所以我们最终采取的是方案2的带头节点带尾指针的单链表!主要操作为初始化public class listQueueT {static class nodeT {T data;// 节点的结果node next;// 下一个连接的节点public node() {}public node(T data) {this.data data;}}node front;//相当于head 带头节点的node rear;//相当于tail/endpublic listQueue() {frontnew nodeT();rearfront;}入队rear.nextva;rearva;va为被插入节点出队队不空front.nextfront.next.next;经典带头节点删除是否为空return rear front;大小节点front遍历到rear的个数。具体实现数组实现package 队栈;public class seqQueueT {private T data[];// 数组容器private int front;// 头private int rear;// 尾private int maxsize;// 最大长度public seqQueue(int i)// 设置长为i的int 型队列{data (T[]) new Object[i1];front 0;rear 0;maxsize i1;}public int lenth() {return (rearmaxsize-front)%maxsize;}public boolean isempty() {return rear front;}public boolean isfull() {return (rear 1) % maxsize front;}public void enQueue(T i) throws Exception// 入队{if (isfull())throw new Exception(已满);else {data[rear] i;rear(rear 1) % maxsize;}}public T deQueue() throws Exception// 出队{if (isempty())throw new Exception(已空);else {T vadata[front];front(front1)%maxsize;return va;}}public String toString()// 输出队{String va队头: ;int lenthlenth();for(int i0;ilenth;i){vadata[(fronti)%maxsize] ;}return va;}}链式实现package 队栈;public class listQueueT {static class nodeT {T data;// 节点的结果node next;// 下一个连接的节点public node() {}public node(T data) {this.data data;}}node front;//相当于head 带头节点的node rear;//相当于tail/endpublic listQueue() {frontnew nodeT();rearfront;}public int lenth() {int len0;node teamfront;while(team!rear){len;teamteam.next;}return len;}public boolean isempty() {return rear front;}public void enQueue(T value) // 入队.尾部插入{node vanew nodeT(value);rear.nextva;rearva;}public T deQueue() throws Exception// 出队{if (isempty())throw new Exception(已空);else {T va(T) front.next.data;front.nextfront.next.next;return va;}}public String toString(){node teamfront.next;String va队头 ;while(team!null){vateam.data ;teamteam.next;}return va;}
}测试总结对于队列来说数据结构相比栈复杂一些但是也不是很难搞懂先进先出然后就用数组或者链表实现即可。对于数组队尾tail指向的位置是空的而链表的fronthead一样为头指针为空的所以在不同结构实现相同效果的方法需要注意一下。对于双向队列大家可以自行了解双向队列两边均可插入删除能够实现堆栈公用等更加灵活调用的结果。(参考java的ArrayDeque).并且现在的消息队列等很多中间件都是基于队列模型延申。所以学会队列很重要最后笔者水平有限如果有纰漏和不足之处还请指出。另外如果感觉不错可以点个赞关注个人公众号bigsai 更多经常与你分享关注回复数据结构获取精心准备的数据结构和算法资料多份
