特定ip段访问网站代码,沈阳百度推广排名优化,动态网站的定义,做网站需要什么配置服务器吗目录
一、顺序队列与循环队列
二、代码实现
1.循环队列创建
2.循环队列遍历
3.循环队列入队
4.循环队列出队
5.数据测试
6.完整的程序代码
总结 一、顺序队列与循环队列
在昨天#xff0c;我们提到队列实现除了采用链式存储结构#xff0c;还可以采用顺序存储结构我们提到队列实现除了采用链式存储结构还可以采用顺序存储结构因为队列是线性表所以和线性表一样也有顺序、链式两种存储结构。采用顺序存储结构的队列叫做顺序队列它是用一组地址连续的存储单元依次存放从队头到队尾的队列元素其中需要附设头指针head和尾指针tail分别指向队头元素和队尾元素。
为方便理解下面我们用图示进行相关说明假设队列的总存储空间TOTAL_SPACE 5 可以预测如果我们在元素E之后再插入元素F那么必然会插入失败这是因为此时的尾指针tail已经达到队列的最大长度5所以没办法继续插入元素。但事实上我们可以看到此时下标为0的存储单元其实是空的也就是说实际上此时的队列并没有满这种现象就叫做“假溢出”。
简单来说“假溢出”的原因就是队列在队头出队、队尾入队从而造成队头出现空闲单元未被充分利用。为了解决这种“假溢出”现象避免存储空间浪费我们将队列的数组看作是头尾相接的循环结构这种队列头尾相接的循环顺序存储结构就是循环队列通过这种方式可以重用队头空闲下来的存储单元如下图 在循环队列中进行入队、出队操作头尾指针的指向仍然要1不过不同的是当头尾指针指向TOTAL_SPACE - 1即头尾指针到达队列的最大长度处时此时再1的结果就变成了头尾指针指向队列下标为0的地方。这种循环意义下的1操作可以用以下两种方式进行实现 if( i TOTAL_SPACE - 1) // i表示head或taili 0;
elsei; i (i1) % TOTAL_SPACE; // i表示head或者tail
对于第二种方式很明显当头尾指针指向TOTAL_SPACE - 1即 i TOTAL_SPACE - 1时i 1就等于TOTAL_SPACE进行整除运算后得到余数为0所以i最后等于0其余时候i 1均小于TOTAL_SPACE所以整除后得到的余数即为i 1本身即i最后就等于i 1。
通过上图我们还可以发现当循环队列为空或者已满时头指针head均等于尾指针tail这就会导致一个问题当head tail时到底是判空还是判满
可以通过以下三种方法来解决这个问题在今天的代码实现中我们用的是第二种方法
另外设置一个布尔变量用于区别队空和队满。减少一个存储空间的使用即把TOTAL_SPACE - 1个队列元素视为已满也就是说当下标为TOTAL_SPACE - 2的存储空间被占用尾指针tail指向TOTAL_SPACE - 1时视为已满从而将队空和队满区别开来。因此队空表示为 head tail队满表示为tail 1% TOTAL_SPACE head。 设置一个计数器用于记录当前队列中的元素个数。计数器初始值为0新元素入队则计数器1元素出队则计数器-1当计数器 TOTAL_SPACE时队满当计数器 0时队空。
二、代码实现
1.循环队列创建
首先需要创建类并定义成员变量、成员方法。由于循环队列是基于顺序表所以这里大体上和顺序表的创建差不多只需要再增加头指针head、尾指针tail的声明即可如下
public class CircleIntQueue {/*** The total space. One space can never be used.*/public static final int TOTAL_SPACE 10;/*** The data.*/int[] data;/*** The index for calculating the head. The actual head is head % TOTAL_SPACE.*/int head;/*** The index for calculating the tail.*/int tail;/********************* * The constructor******************* */public CircleIntQueue() {data new int[TOTAL_SPACE];head 0;tail 0;} // Of the first constructor
2.循环队列遍历 /************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString ;if (head tail) {return empty;} // Of iffor (int i head; i tail; i) {resultString data[i % TOTAL_SPACE] , ;} // Of for ireturn resultString;} // Of toString
循环队列的遍历没什么好说的也是通过重写toString()方法基本上与之前顺序表的遍历一样。
3.循环队列入队 /************************ Enqueue.* * param paraValue The value of the new node.**********************/public void enqueue(int paraValue) {if ((tail 1) % TOTAL_SPACE head) {System.out.println(Queue full.);return;} // Of ifdata[tail % TOTAL_SPACE] paraValue;tail;} // Of enqueue
由于顺序表的存储空间有上限所以在入队之前需要先判断是否队满。根据之前的分析得到队满判断条件为(tail 1) % TOTAL_SPACE head确定队列未满后进行入队操作显然此时tail小于TOTAL_SPACE所以tail % TOTAL_SPACE taildata[ tail % TOTAL_SPACE ]就是指已有队列元素后面第一个空的存储单元将新元素赋给其即可完成入队最后不要忘了更新尾指针。
4.循环队列出队 /************************ Dequeue.* * return The value at the head.**********************/public int dequeue() {if (head tail) {System.out.println(No element in the queue);return -1;} // Of ifint resultValue data[head % TOTAL_SPACE];head;return resultValue;} // Of dequeue
出队只需判断是否队空而队空的判断条件也十分简单即head tail判断之后开始出队因为head小于TOTAL_SPACE所以head % TOTAL_SPACE headdata[ head % TOTAL_SPACE ]即为头指针指向的元素也就是队头的第一个元素最后更新头指针并返回删除的队列元素。
5.数据测试
方法创建完毕后进行如下的数据测试 /************************ The entrance of the program.* * param args Not used now.**********************/public static void main(String args[]) {CircleIntQueue tempQueue new CircleIntQueue();System.out.println(Initialized, the list is: tempQueue.toString());for (int i 0; i 5; i) {tempQueue.enqueue(i 1);} // Of for iSystem.out.println(Enqueue, the queue is: tempQueue.toString());int tempValue tempQueue.dequeue();System.out.println(Dequeue tempValue , the queue is: tempQueue.toString());for (int i 0; i 6; i) {tempQueue.enqueue(i 10);System.out.println(Enqueue, the queue is: tempQueue.toString());} // Of for ifor (int i 0; i 3; i) {tempValue tempQueue.dequeue();System.out.println(Dequeue tempValue , the queue is: tempQueue.toString());} // Of for ifor (int i 0; i 6; i) {tempQueue.enqueue(i 100);System.out.println(Enqueue, the queue is: tempQueue.toString());} // Of for i} // Of main
6.完整的程序代码
package datastructure;/*** Circle int queue.**auther Xin Lin 3101540094qq.com.*/
public class CircleIntQueue {/*** The total space. One space can never be used.*/public static final int TOTAL_SPACE 10;/*** The data.*/int[] data;/*** The index for calculating the head. The actual head is head % TOTAL_SPACE.*/int head;/*** The index for calculating the tail.*/int tail;/********************* * The constructor******************* */public CircleIntQueue() {data new int[TOTAL_SPACE];head 0;tail 0;} // Of the first constructor/************************ Enqueue.* * param paraValue The value of the new node.**********************/public void enqueue(int paraValue) {if ((tail 1) % TOTAL_SPACE head) {System.out.println(Queue full.);return;} // Of ifdata[tail % TOTAL_SPACE] paraValue;tail;} // Of enqueue/************************ Dequeue.* * return The value at the head.**********************/public int dequeue() {if (head tail) {System.out.println(No element in the queue);return -1;} // Of ifint resultValue data[head % TOTAL_SPACE];head;return resultValue;} // Of dequeue/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString ;if (head tail) {return empty;} // Of iffor (int i head; i tail; i) {resultString data[i % TOTAL_SPACE] , ;} // Of for ireturn resultString;} // Of toString/************************ The entrance of the program.* * param args Not used now.**********************/public static void main(String args[]) {CircleIntQueue tempQueue new CircleIntQueue();System.out.println(Initialized, the list is: tempQueue.toString());for (int i 0; i 5; i) {tempQueue.enqueue(i 1);} // Of for iSystem.out.println(Enqueue, the queue is: tempQueue.toString());int tempValue tempQueue.dequeue();System.out.println(Dequeue tempValue , the queue is: tempQueue.toString());for (int i 0; i 6; i) {tempQueue.enqueue(i 10);System.out.println(Enqueue, the queue is: tempQueue.toString());} // Of for ifor (int i 0; i 3; i) {tempValue tempQueue.dequeue();System.out.println(Dequeue tempValue , the queue is: tempQueue.toString());} // Of for ifor (int i 0; i 6; i) {tempQueue.enqueue(i 100);System.out.println(Enqueue, the queue is: tempQueue.toString());} // Of for i} // Of main} // Of class CircleIntQueue运行结果 总结
循环队列是一种特殊类型的队列它在传统顺序队列的基础上进行优化通过“环形结构”充分利用存储空间避免了空间浪费虽然相比于链队列循环队列似乎没有那么方便不过在固定大小的缓冲区和任务调度等需要高效处理的数据流场景循环队列还是非常适用的。昨天我们学习了链队列今天学习了循环队列二者都是对于队列实现的模拟这启示我们对于同一种逻辑结构有时是可以采用不同的物理存储结构来实现的。
