图文详解:数据结构与算法中的队列
发表时间: 2019-08-16 11:26
基本属性
队头front:
队尾rear:
enQueue(入队):
deQueue(出队):
普通队列
按照上述的介绍,我们很容易知道数组实现的方式。用数组模拟表示队列。要考虑初始化,插入,问题。
但是很容易发现问题,每个空间域只能利用一次。造成空间极度浪费。并且非常容易越界!
循环队列
针对上述的问题。有个较好的解决方法!就是对已经申请的(数组)内存重复利用。这就是我们所说的循环队列。
而数组实现的循环队列就是在逻辑上稍作修改。我们假设(约定)数组的最后一位的下一个index是首位。因为我们队列中只需要front和tail两个指标。不需要数组的实际地址位置相关数据。和它无关。所以我们就只需要考虑尾部的特殊操作即可。
这里面有几个大家需要注意的,就是指标相加如果遇到最后需要转到头的话。可以判断是否到数组末尾位置。也可以直接+1求余。其中maxsize是数组实际大小。
链式实现
对于链表实现的队列,要根据先进先出的规则考虑头和尾的位置
我们知道队列是先进先出的,对于链表,我们能采用单链表尽量采用单链表,能方便尽量方便,同时还要兼顾效率。
主要操作为:
public class listQueue<T> { static class node<T> { T data;// 节点的结果 node next;// 下一个连接的节点 public node() {} public node(T data) { this.data = data; } } node front;//相当于head 带头节点的 node rear;//相当于tail/end public listQueue() { front=new node<T>(); rear=front; }
数组实现
package 队栈;public class seqQueue<T> { private T data[];// 数组容器 private int front;// 头 private int rear;// 尾 private int maxsize;// 最大长度 public seqQueue(int i)// 设置长为i的int 型队列 { data = (T[]) new Object[i+1]; front = 0; rear = 0; maxsize = i+1; } public int lenth() { return (rear+maxsize-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 va=data[front]; front=(front+1)%maxsize; return va; } } public String toString()// 输出队 { String va="队头: "; int lenth=lenth(); for(int i=0;i<lenth;i++) { va+=data[(front+i)%maxsize]+" "; } return va; }}
链式实现
package 队栈;public class listQueue<T> { static class node<T> { T data;// 节点的结果 node next;// 下一个连接的节点 public node() {} public node(T data) { this.data = data; } } node front;//相当于head 带头节点的 node rear;//相当于tail/end public listQueue() { front=new node<T>(); rear=front; } public int lenth() { int len=0; node team=front; while(team!=rear) { len++;team=team.next; } return len; } public boolean isempty() { return rear == front; } public void enQueue(T value) // 入队.尾部插入 { node va=new node<T>(value); rear.next=va; rear=va; } public T deQueue() throws Exception// 出队 { if (isempty()) throw new Exception("已空"); else { T va=(T) front.next.data; front.next=front.next.next; return va; } } public String toString() { node team=front.next; String va="队头: "; while(team!=null) { va+=team.data+" "; team=team.next; } return va; }}
测试