前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Java 模拟队列(一般队列、双端队列、优先级队列)[通俗易懂]

Java 模拟队列(一般队列、双端队列、优先级队列)[通俗易懂]

作者头像
全栈程序员站长
发布2022-07-07 17:52:04
4820
发布2022-07-07 17:52:04
举报

大家好,又见面了,我是全栈君。

队列:

先进先出,处理类似排队的问题,先排的。先处理,后排的等前面的处理完了,再处理

对于插入和移除操作的时间复杂度都为O(1)。从后面插入,从前面移除

双端队列:

即在队列两端都能够insert和remove:insertLeft、insertRight。removeLeft、removeRight

含有栈和队列的功能,如去掉insertLeft、removeLeft,那就跟栈一样了。如去掉insertLeft、removeRight。那就跟队列一样了

一般使用频率较低,时间复杂度 O(1)

优先级队列:

内部维护一个按优先级排序的序列。插入时须要比較查找插入的位置,时间复杂度O(N), 删除O(1)

代码语言:javascript
复制
/* * 队列	先进先出。一个指针指示插入的位置,一个指针指示取出数据项的位置 */public class QueueQ<T> {	private int max;	private T[] ary;	private int front; //队头指针  指示取出数据项的位置	private int rear;  //队尾指针  指示插入的位置	private int nItems; //实际数据项个数		public QueueQ(int size) {		this.max = size;		ary = (T[]) new Object[max];		front = 0;		rear = -1;		nItems = 0;	}	//插入队尾	public void insert(T t) {		if (rear == max - 1) {//已到实际队尾,从头開始			rear = -1;		}		ary[++rear] = t;		nItems++;	}	//移除队头	public T remove() {		T temp = ary[front++];		if (front == max) {//列队到尾了,从头開始			front = 0;		}		nItems--;		return temp;	}	//查看队头	public T peek() {		return ary[front];	}		public boolean isEmpty() {		return nItems == 0;	}		public boolean isFull() {		return nItems == max;	}		public int size() {		return nItems;	}		public static void main(String[] args) {		QueueQ<Integer> queue = new QueueQ<Integer>(3);		for (int i = 0; i < 5; i++) {			queue.insert(i);			System.out.println("size:" + queue.size());		}		for (int i = 0; i < 5; i++) {			Integer peek = queue.peek();			System.out.println("peek:" + peek);			System.out.println("size:" + queue.size());		}		for (int i = 0; i < 5; i++) {			Integer remove = queue.remove();			System.out.println("remove:" + remove);			System.out.println("size:" + queue.size());		}				System.out.println("----");				for (int i = 5; i > 0; i--) {			queue.insert(i);			System.out.println("size:" + queue.size());		}		for (int i = 5; i > 0; i--) {			Integer peek = queue.peek();			System.out.println("peek:" + peek);			System.out.println("size:" + queue.size());		}		for (int i = 5; i > 0; i--) {			Integer remove = queue.remove();			System.out.println("remove:" + remove);			System.out.println("size:" + queue.size());		}	}	}
代码语言:javascript
复制
/*
 * 双端队列<span style="white-space:pre">	</span>两端插入、删除
 */
public class QueueQT<T> {
	private LinkedList<T> list;

	public QueueQT() {
		list = new LinkedList<T>();
	}

	// 插入队头
	public void insertLeft(T t) {
		list.addFirst(t);
	}

	// 插入队尾
	public void insertRight(T t) {
		list.addLast(t);
	}

	// 移除队头
	public T removeLeft() {
		return list.removeFirst();
	}

	// 移除队尾
	public T removeRight() {
		return list.removeLast();
	}

	// 查看队头
	public T peekLeft() {
		return list.getFirst();
	}

	// 查看队尾
	public T peekRight() {
		return list.getLast();
	}

	public boolean isEmpty() {
		return list.isEmpty();
	}

	public int size() {
		return list.size();
	}

}
代码语言:javascript
复制
/*
 * 优先级队列	队列中按优先级排序。是一个有序的队列
 */
public class QueueQP {
	private int max;
	private int[] ary;
	private int nItems; //实际数据项个数
	
	public QueueQP(int size) {
		this.max = size;
		ary =  new int[max];
		nItems = 0;
	}
	//插入队尾
	public void insert(int t) {
		int j;
		if (nItems == 0) {
			ary[nItems++] = t;
		} else {
			for (j = nItems - 1; j >= 0; j--) {
				if (t > ary[j]) {
					ary[j + 1] = ary[j]; //前一个赋给后一个  小的在后		相当于用了插入排序。给定序列本来就是有序的。所以效率O(N)
				} else {
					break;
				}
			}
			ary[j + 1] = t;
			nItems++;
		}
		System.out.println(Arrays.toString(ary));
	}
	//移除队头
	public int remove() {
		return ary[--nItems]; //移除优先级小的
	}
	//查看队尾 优先级最低的
	public int peekMin() {
		return ary[nItems - 1];
	}
	
	public boolean isEmpty() {
		return nItems == 0;
	}
	
	public boolean isFull() {
		return nItems == max;
	}
	
	public int size() {
		return nItems;
	}
	
	public static void main(String[] args) {
		QueueQP queue = new QueueQP(3);
		queue.insert(1);
		queue.insert(2);
		queue.insert(3);
		int remove = queue.remove();
		System.out.println("remove:" + remove);
		
	}
	
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116477.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年1月2,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档