队列

2020-04-07 16:09:49来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

队列

队列

队列是用数组或链表实现的,遵循先进先出规则的一个有序列表

使用数组模拟队列

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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【从零开始学Java笔记】为什么选择Java(学习资料分享:java四大

下一篇:4 种分布式session解决方案