队列
2020-04-07 16:09:49来源:博客园 阅读 ()
队列
队列
队列是用数组或链表实现的,遵循先进先出规则的一个有序列表
使用数组模拟队列
public class ArrayQueue<T> {
private Object[] arr;
private int front;
private int rear;
private int capacity;
public ArrayQueue() {
this.capacity=10;
this.front=-1;
this.rear=-1;
this.arr=new Object[this.capacity];
}
public ArrayQueue(int capacity) {
this.capacity=capacity;
this.front=-1;
this.rear=-1;
this.arr=new Object[this.capacity];
}
public boolean add(T t) {
if(this.rear<this.capacity-1) {
this.arr[++rear]=t;
return true;
}
throw new RuntimeException("队列已满!");
}
public T remove() {
if(this.rear==this.front) {
throw new RuntimeException("队列为空,不能出队列!");
}
return (T)this.arr[++front];
}
public T poll() {
if(this.rear==this.front) {
return null;
}
return (T)this.arr[++front];
}
public T peek() {
if(this.rear==this.front) {
return null;
}
return (T)this.arr[++front];
}
@Override
public String toString() {
String str= "ArrayQueue [";
for(int i=front+1;i<=rear;i++) {
str+=this.arr[i]+" ";
}
return str+="]";
}
public static void main(String[] args) {
ArrayQueue<Integer> queue=new ArrayQueue<>(4);
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
System.out.println(queue);
Integer remove1 = queue.remove();
System.out.println(remove1);
Integer remove2 = queue.remove();
System.out.println(remove2);
Integer remove3 = queue.remove();
System.out.println(remove3);
Integer remove4 = queue.remove();
System.out.println(remove4);
queue.add(5);
}
}
输出:
ArrayQueue [1 2 3 4 ]
1
2
3
4
Exception in thread "main" java.lang.RuntimeException: 队列已满!
分析:虽然队列中的元素已经全部出队,但是由于我们的队列是使用数组模拟的,而且每次入队的时候,头指定都后移,当我们入队次数增加,总有一时刻,头指针指向数组最大下标,尽管我们有出队,但是任然不能入队元素,我们可以使用数组模拟循环队列来解决这个问题
使用数组模拟循环队列
分析
我们可以做这样一个约定,在数组中空一个位置,当(rear+1)%capacity==front来表示队满,当front==rear时表示队空
这个时候,那么计算队列中元素个数公式为:size=(rear+capacity-front)%capacity
public class CircleArrayQueue<T> {
private Object[] arr;
private int front;
private int rear;
private int capacity;
public CircleArrayQueue() {
this.capacity=10;
this.front=0;
this.rear=0;
this.arr=new Object[this.capacity];
}
public CircleArrayQueue(int capacity) {
this.capacity=capacity;
this.front=0;
this.rear=0;
this.arr=new Object[this.capacity];
}
public boolean add(T t) {
if((rear+1)%capacity==front) {//队列已满
throw new RuntimeException("队列已满!");
}
//rear下标超出最大下标,那么取模
rear=(rear+1)%capacity;
this.arr[rear]=t;
return true;
}
public T remove() {
if(this.rear==this.front) {
throw new RuntimeException("队列为空,不能出队列!");
}
return (T)this.arr[++front];
}
public T poll() {
if(this.rear==this.front) {
return null;
}
return (T)this.arr[++front];
}
public T peek() {
if(this.rear==this.front) {
return null;
}
return (T)this.arr[++front];
}
public int size() {
return (rear+capacity-front)%capacity;
}
@Override
public String toString() {
String str= "ArrayQueue [";
int total=size();
int index=front+1;
for(int i=0;i<total;i++) {
str+=arr[index]+" ";
index=(index+1)%capacity;
}
return str+="]";
}
public static void main(String[] args) {
CircleArrayQueue<Integer> queue=new CircleArrayQueue<>(4);
//由于需要空一个,capacity为4也只能存放三个元素
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println(queue);
Integer remove = queue.remove();
System.out.println(remove);
queue.add(4);
System.out.println(queue);
}
}
输出:
ArrayQueue [1 2 3 ]
1
ArrayQueue [2 3 4 ]
链队列
使用节点来包装值,好处是使用链表可以不用考虑大小的问题,队列永远不可能满
public class LinkedQueue<T> {
static class Node<T>{
T val;
Node next;
public Node(T val, Node next) {
super();
this.val = val;
this.next = next;
}
public Node(T val) {
this.val=val;
}
}
private int size;
private Node<T> front;
private Node<T> rear;
public LinkedQueue() {
this.size=0;
}
public void add(T t) {
Node<T> node=new Node<T>(t);
this.size++;
if(rear==null) {
rear=node;
front=node;
}
rear.next=node;
rear=node;
}
public T remove() {
if(size<=0) {
throw new RuntimeException("队列为空,不能出队!");
}
size--;
Node<T> n=front;
if(size==0) {
front=null;
rear=null;
return n.val;
}
front=front.next;
return n.val;
}
public T poll() {
if(size<=0) {
return null;
}
size--;
Node<T> n=front;
if(size==0) {
front=null;
rear=null;
return n.val;
}
front=front.next;
return n.val;
}
public T peek() {
if(this.size<=0) {
return null;
}
return front.val;
}
public int size() {
return size;
}
@Override
public String toString() {
String str= "LinkedQueue [";
Node<T> n=front;
while(n!=null) {
str+=n.val+" ";
n=n.next;
}
str+="]";
return str;
}
public static void main(String[] args) {
LinkedQueue<Integer> queue =new LinkedQueue<>();
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println(queue);
Integer remove1 = queue.remove();
System.out.println(remove1);
Integer remove2 = queue.remove();
System.out.println(remove2);
Integer remove3 = queue.remove();
System.out.println(remove3);
queue.remove();
}
}
输出:
LinkedQueue [1 2 3 ]
1
2
3
Exception in thread "main" java.lang.RuntimeException: 队列为空,不能出队!
原文链接:https://www.cnblogs.com/moyuduo/p/12657160.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 一口气说出 6种 延时队列的实现方案,面试稳稳的 2020-06-08
- Java笔记:数组,异常,泛型 2020-06-08
- 数据结构之链式队列的代码实现及有趣应用 2020-05-29
- 数组小Demo 2020-05-25
- 从零开始的数组,这么设计么是为什呢? 2020-05-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash