当前位置：网站首页 > 技术资源 > 正文

稀疏数组和队列(二)（组稀疏表示算法）

off999 2024-11-14 16:54 28 浏览 0 评论

队列的介绍

队列以一种先入先出（FIFO）的线性表，还有一种先入后出的线性表（FILO）叫做栈。

教科书上有明确的定义与描述。类似于现实中排队时的队列（队尾进，队头出），队列只在线性表两端进行操作，插入元素的一端称为表尾，删除（取出）元素的一端称为表头。分别对应于入队和出队操作。

存储结构：

· 线性存储结构，称为顺序队列，使用数组实现

· 链式存储结构，称为链队，使用链表实现。

图解入队操作

图解出队操作

队列的使用场景

数组模拟顺序队列

代码实现：

/** 
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title: ArrayQueue.java 
 * @Package com.tuling.queue2 
 * @Description: 
 * @author: 小白 
 * @Date 2019年11月11日 下午5:54:51 
 * @version V1.0 
 * @Copyright: 
 */ 
package com.tuling.queue2;

/**
 * @ClassName ArrayQueue
 * @Description 
 * @Author 北京图灵学院
 * @Date 2019年11月11日 下午5:54:51
 */
public class ArrayQueue {
	
	//定义一个数组，用来模拟队列，存储数据
	private Integer[] arr;
	//定义一个变量，用来指向队列头
	private int front;
	//定义一个变量，用来指向队列尾
	private int rear;
	
	
	/**
	 * 
	 * @Title: ArrayQueue 
	 * @Description: 构造方法 
	 * @param queueSize：队列初始化容量。 
	 * @throws 
	 */
	public ArrayQueue(int queueSize) {
		if(queueSize < 0) {
			throw new IllegalArgumentException("初始化容量不能小于0");
		}
		
		arr = new Integer[queueSize];
		front = 0;
		rear = 0;
		
	}
	
	/**
	 * 
	 * @Title: addQueue 
	 * @Description: 入队操作：
	 * 		1、首先判断队列容量情况
	 * 		2、如果队列未满，队列头不变，向队列尾下标位置插入数据，同时，队列尾+1
	 * @param: @param num 
	 * @return: void 
	 * @throws
	 */
	public void addQueue(int num) {
		if(isFull()) {
			throw new IllegalArgumentException("队列已满！");
		}
		
		arr[rear] = num;
		rear++;
		
	}
	
	/**
	 * 
	 * @Title: isFull 
	 * @Description: 判断队列是否已满
	 * @return: boolean 
	 * @throws
	 */
	public boolean isFull() {
		return rear == arr.length;
	}
	
	/**
	 * 
	 * @Title: getQueue 
	 * @Description: 出队操作
	 * 		1、先判读当前队列是否为空
	 * 		2、每次从队列头开始出队，出队一个元素，队列头+1 
	 * @param: 
	 * @return: int 
	 * @throws
	 */
	public int getQueue() {
		if(isEmpty()) {
			throw new IllegalArgumentException("队列为空！");
		}
		
		return arr[front++];
	}
	
	/**
	 * 
	 * @Title: isEmpty 
	 * @Description: 判断当前队列是否为空 
	 * @return: boolean 
	 * @throws
	 */
	public boolean isEmpty() {
		return front == rear;
	}
	
	/**
	 * 
	 * @Title: showQueue 
	 * @Description:显示队列的所有数据 
	 * @param: 
	 * @return: void 
	 * @throws
	 */
	public void showQueue() {
		if(isEmpty()) {
			throw new IllegalArgumentException("队列为空！");
		}
		for (int i = front; i < rear; i++) {
			System.out.println(i + " --> " + arr[i]);
		}
	}
}





/** 
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title: ArrayQueueDemo.java 
 * @Package com.tuling.queue2 
 * @Description: 
 * @author: 小白 
 * @Date 2019年11月11日 下午6:22:00 
 * @version V1.0 
 * @Copyright: 
 */ 
package com.tuling.queue2;

/**
 * @ClassName ArrayQueueDemo
 * @Description 
 * @Author 北京图灵学院
 * @Date 2019年11月11日 下午6:22:00
 */
public class ArrayQueueDemo {

	/** 
	 * @Title: main 
	 * @Description: 
	 * @param: @param args 
	 * @return: void 
	 * @throws 
	 */
	public static void main(String[] args) {
		ArrayQueue aq = new ArrayQueue(5);
		
		aq.addQueue(5);
		aq.addQueue(8);
		aq.addQueue(7);
		aq.showQueue();
		System.out.println("------------------------------------");

		aq.addQueue(2);
		aq.addQueue(9);
//		aq.addQueue(9);
		aq.showQueue();
		System.out.println("------------------------------------");
	
		System.out.println("出队");
		aq.getQueue();
		aq.showQueue();
		
		System.out.println("------------------------------------");
		System.out.println("出队");
		aq.getQueue();
		aq.showQueue();
		
		System.out.println("------------------------------------");
		System.out.println("出队");
		aq.getQueue();
		aq.showQueue();
		
		System.out.println("------------------------------------");
		System.out.println("出队");
		aq.getQueue();
		aq.showQueue();
		
		System.out.println("------------------------------------");
		System.out.println("出队");
		aq.getQueue();
		aq.showQueue();
	
	}

}

顺序队列的溢出现象

· "下溢"现象：当队列为空时，做出队运算产生的溢出现象。"下溢"是正常现象，常用作程序控制转移的条件。

· "真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。"真上溢"是一种出错状态，应设法避免。

· "假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

数组模拟环形队列

为了解决顺序队列中"假上溢"的现象，同时更好的利用内存空间，我们将其实现为环形队列。

理解环形队列

首先我们要说明的是循环队列仍然是基于数组实现的。但是为了形象化的说明问题，我们如下图所示

1．图中有两个指针(其实就是两个整数型变量，因为在这里有指示作用，所以这里理解为指针)front、rear,一个指示队头，一个指示队尾。

2． rear和front互相追赶着，这个追赶过程就是队列添加和删除的过程，如果rear追到head说明队列满了，如果front追到rear说明队列为空。

3．我们把它掰弯，用的是求余，这样两个值就不会跑出最大范围，并且可以实现弯曲的效果，所以说对于循环队列我们必须给定最大值。这其实是我们臆想的，我们要做的就是利用循环来解决空间浪费的问题。

环形队列的实现过程

· 当添加一个元素时,(rear+1)%MAXQSIZE; //理解为什么求余？

· 当删除一个元素时,(front+1)%MAXQSIZE；//理解为什么求余？

· 当rear=front的时候，队列可能是满，也可能是空。

· 因为存在满和空两种情况，我们需要分别判断：

· 满：当队列添加元素到rear的下一个元素是head的时候，也就是转圈子要碰头了，我们就认为队列满了。(rear+1)%MAXSIZE=Q.front

· 空：当队列删除元素到head=rear的时候，我们认为队列空了。rear==front,不一定为0

环形队列代码实现

CircularQueue.java 类代码如下：

/** 
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title: CircularQueue.java 
 * @Package com.tuling.circular 
 * @Description: 
 * @author: 北京图灵学院 
 * @date: 2019年11月13日 下午5:13:16 
 * @version V1.0 
 * @Copyright: 
 */
package com.tuling.circular;

/**
 * @ClassName CircularQueue
 * @Description 
 * @Author 北京图灵学院
 */
public class CircularQueue {
	//该数组模拟环形队列，存储数据
	private Integer[] arr;
	
	//该变量指向队头
	private int front;
	
	//该变量指向队尾
	private int rear;
	
	//该变量表示当前队列的最大容量
	private int maxSize;
	
	//该变量表示当前队列有效数据的个数
	private int elementCount;
	
	/**
	 * 
	 * @param queueSize:队列的初始容量
	 */
	public CircularQueue(int queueSize) {
		if(queueSize < 0) {
			throw new IllegalArgumentException("初始化容量不能小于0！");
		}
		
		arr = new Integer[queueSize];
		maxSize = queueSize;
		front = 0;
		rear = 0;
		elementCount=0;
	}
	
	/**
	 * 
	 * @Title: addQueue 
	 * @Description:入队操作
	 * 		思路：
	 * 			1、判断队列是否已满
	 * 			2、向队尾插入数据 
	 * 			3、将有效数据的个数 + 1
	 * @param: num 
	 * @return: void 
	 * @throws
	 */
	public void addQueue(int num) {
		if(isFull()) {
			throw new IllegalArgumentException("队列已满！");
		}
		
		//队列未满，可以继续入队操作
		//想队尾插入数据
		arr[rear] = num;
		
		//移动尾指针
		rear = (rear + 1) % maxSize;
		elementCount+=1;
	}
	
	/**
	 * 
	 * @Title: isFull 
	 * @Description:判断当前队列是否已满
	 * 		判满条件：
	 * 			1、空出一个元素位置，区别队列判空的条件
	 * 			2、保证队尾指针的范围在数组下标范围内，解决方案：对Maxsize取余
	 * 				(rear + 1) % maxSize == front 
	 * @param: 
	 * @return: boolean 
	 * @throws
	 */
	public boolean isFull() {
		return (rear + 1) % maxSize == front;
	}
	
	/**
	 * 
	 * @Title: showQueue 
	 * @Description:显示队列当中的所有数据 
	 * @param: 
	 * @return: void 
	 * @throws
	 */
	public void showQueue() {
		if(isEmpty()) {
			throw new IllegalArgumentException("队列为空！");
		}
		
		for(int i = front; i < (front+elementCount);i++) {
			System.out.println((i%maxSize) + " --> " + arr[i%maxSize]);
		}
		
	}
	
	/**
	 * 
	 * @Title: isEmpty 
	 * @Description:判断当前队列是否为空 
	 * @param: 
	 * @return: boolean 
	 * @throws
	 */
	public boolean isEmpty() {
		return front == rear;
	}
	
	/**
	 * 
	 * @Title: getQueue 
	 * @Description: 出队操作
	 * 			思路：出队需要操作队头后移，还需要注意队头的值范围。 
	 * 			1、先用一个临时变量存储当前队头
	 * 			2、将队头后移
	 * 				front = (front + 1) % maxSize
	 * 			3、将有效数据个数 -1
	 * 			4、return
	 * @param: 
	 * @return: int 
	 * @throws
	 */
	public int getQueue() {
		if(isEmpty()) {
			throw new IllegalArgumentException("队列为空！");
		}
		
		int tempHead = arr[front];
		front = (front + 1) % maxSize;
		elementCount-=1;
		return tempHead;
	}
	
	/**
	 * 
	 * @Title: showHead 
	 * @Description:显示当前队列头，不进行出队操作 
	 * @param: 
	 * @return: void 
	 * @throws
	 */
	public void showHead() {
		if(isEmpty()) {
			throw new IllegalArgumentException("队列为空！");
		}
		System.out.println("当前队列的队列头为：" + front + " --> " + arr[front]);
	}
}

测试代码：

/** 
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title: CircularQueueDemo.java 
 * @Package com.tuling.circular 
 * @Description: 
 * @author: 北京图灵学院 
 * @date: 2019年11月13日 下午5:30:43 
 * @version V1.0 
 * @Copyright: 
 */
package com.tuling.circular;

/**
 * @ClassName CircularQueueDemo
 * @Description 
 * @Author 北京图灵学院
 */
public class CircularQueueDemo {

	/** 
	 * @Title: main 
	 * @Description: 
	 * @param: @param args 
	 * @return: void 
	 * @throws 
	 */
	public static void main(String[] args) {
		CircularQueue cq = new CircularQueue(5);
		
		System.out.println("--------------------------1.入队操作-----------------------------");
		cq.addQueue(5);
		cq.addQueue(8);
		cq.addQueue(7);
		cq.addQueue(2);
//		cq.addQueue(9);
		
		cq.showQueue();
		
		
		System.out.println("--------------------------2.入队操作-----------------------------");
		System.out.println("出队：" + cq.getQueue());
		cq.showHead();
		System.out.println("出队：" + cq.getQueue());
		cq.showHead();
		System.out.println("出队：" + cq.getQueue());
		cq.showHead();
		System.out.println("出队：" + cq.getQueue());
		
		System.out.println("--------------------------3.入队操作-----------------------------");
		cq.addQueue(5);
		cq.addQueue(8);
		cq.addQueue(7);
		cq.addQueue(2);
		cq.showQueue();
	}

}

python判断数组为空