数据结构之普通队列、循环队列的实现以及它们的区别

队列接口:

package demo;
 
public interface Queue {
	void enqueue(E e);
	E dequeue();
	E getFront();
	int getSize();
	boolean IsEmpty();
	
	
}

普通队列:

package demo;
 
import java.util.*;
 
public class ArrayQueue<E> implements Queue<E> {
	private List queue = new ArrayList();
 
	public ArrayQueue() {
 
	}
 
//	出队
	@Override
	public E dequeue() {
		E e = queue.get(0);
		queue.remove(0);
		return e;
	}
 
//	入队
	@Override
	public void enqueue(E e) {
		queue.add(e);
 
	}
//  获取队列头元素
	@Override
	public E getFront() {
		return queue.get(0);
	}
//  队列大小
	@Override
	public int getSize() {
 
		return queue.size();
	}
//  队列是否为空
	@Override
	public boolean IsEmpty() {
		// TODO Auto-generated method stub
		return queue.size() == 0;
	}
 
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		ArrayQueue other = (ArrayQueue) obj;
		if (queue == null) {
			if (other.queue != null)
				return false;
		} else if (!queue.equals(other.queue))
			return false;
		return true;
	}
 
	@Override
	public String toString() {
		return "[queue=" + queue + "]";
	}
 
}

循环队列:

package demo;
 
import java.util.Arrays;
 
public class LoopQueue<E> implements Queue<E> {
//	此时用list容器没办法做循环队列 所以需要自己定义一个数组
//	循环队列 可以理解为首尾相连的数组队列 
//   其实就是利用取余的原理让 tail 和front 永远在数组限定长度里徘徊不会越界
	private int front;
	private E[] queue;
	private int size;
	private int tail;
 
	public LoopQueue() {
		this.front = 0;
		this.tail = 0;
		this.size = 0;
		this.queue = (E[]) new Object[100000 + 1];
	}
 
	@Override
//	出队列 
	public E dequeue() {
//		出队列前判断一下队列是否为空 不空则置队头元素为null 然后队头++
		E e = null;
		if (IsEmpty()) {
			System.out.println("队列为空");
		} else {
			e = queue[front];
			queue[front] = null;
			front = (front + 1) % queue.length;
			size--;
 
		}
		return e;
	}
//  进队列 
	@Override
	public void enqueue(E e) {
//		进队列前判断一下队列是否满了 没满则在队尾进队
		if ((tail + 1) % queue.length == front) {
			System.out.println("队列 已满");
		} else {
			queue[tail] = e;
			tail = (tail + 1) % queue.length;
			size++;
		}
 
	}
//  获取队列头元素
	@Override
	public E getFront() {
		if (IsEmpty()) {
			System.out.println("队列为空");
		} else {
			return queue[front];
		}
		return null;
 
	}
//	获取当前队列长度
	@Override
	public int getSize() {
 
		return size;
	}
//  是否为空
	@Override
	public boolean IsEmpty() {
 
		return front == tail;
	}
 
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		LoopQueue other = (LoopQueue) obj;
		if (front != other.front)
			return false;
		if (!Arrays.deepEquals(queue, other.queue))
			return false;
		if (size != other.size)
			return false;
		if (tail != other.tail)
			return false;
		return true;
	}
 
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + front;
		result = prime * result + Arrays.deepHashCode(queue);
		result = prime * result + size;
		result = prime * result + tail;
		return result;
	}
 
	@Override
	public String toString() {
		return "[queue=" + Arrays.toString(queue) + ", front=" + front + ", tail=" + tail + ", size=" + size + "]";
	}
 
}

 

© 版权声明
THE END
喜欢就支持以下吧
点赞0
分享
评论 抢沙发