文档章节

数据结构——队列——循环队列

清风傲剑
 清风傲剑
发布于 2014/09/20 21:02
字数 731
阅读 21
收藏 0
package jxau.lyx.queue;

/**
 * 
 * @author liyixiang
 * @2014-9-20
 * @DataStrutureType: 队列之循环队列
 * @TODO:
 * 		基本队列结构:
 * 		队列是先进先出 那么队头为出口 队尾为入口
 * 		以前队列的理解是一个元素出队列后,后面元素自动前进(例如排队)
 * 现在发现是队头指针和队尾指针的移动!
 * 		循环队列的含义是:
 * 使用环绕式处理 让队头队尾指针绕回到数组开始的位置(解决假溢出)
 * 		
 * 		假溢出:
 * 		由于队尾指针rear的值和队头指针front的值不能由所定义存储空间的最大值自动转
 * 为所定义存储空间的最小值而产生
 * 
 * 		注意:
 * 		当队列满时,front与rear指针取一定的位置,但是当队列为空时,也可能呈现相同
 * 的位置关系,于是在同一时间,队列似乎是满的,也可能是空的。
 * 		解决:
 * 		1.让数组容量比队列数据项个数的最大值还要大一。
 * 			rear+1 = front
 * 		2.设置一个标志位
 * 			入队tag++ 出队tag--
 * 		3.设置一个计数器
 * 			count == 0(类似于代码中的nItems)  不仅可以计数,还具有标志位的功能。
 */
public class Queue {

	private int maxSize;                      //队列最大空间
	private Object[] queueArray;            //队列空间
	private int front;                          //队头索引
	private int rear;                           //队尾索引
	private int nItems;                        //队中含有的元素个数
	
	/**
	 * 初始化
	 * @param s:队空间大小
	 */
	public Queue(int s){
		maxSize = s;
		queueArray = new Object[maxSize];
		front = 0;
		rear = -1;
		nItems = 0;
	}
	
	/**
	 * 
	 *@liyixiang
	 *@2014-9-20
	 *@param:obj 入队元素
	 *@return:void
	 *@TODO:
	 *		入队:
	 *方法运行的前提条件是队列不满,通常应该先调用isFull方法判断队列是否为满
	 *更通常的做法是在insert方法中就加入检查队列是否满的判定,如果出现向已满
	 *队列里插入数据项的情况就抛出异常
	 *		循环队列解决基本队列的假溢出
	 */
	public void insert(Object obj){
		if(rear == maxSize-1){                //队尾索引已达最大空间
			rear = -1;							  //队尾指针回绕
		}
		
		queueArray[++rear] = obj;            //队尾
		nItems++;
	}
	
	/**
	 * 
	 *@liyixiang
	 *@2014-9-21
	 *@param
	 *@return:Object:移除元素
	 *@TODO:
	 *		出队
	 *		运行的前提条件是队列不空,在调用这个方法之前应该先调用isEmpty方法确保
	 *队列不空,或者在remove方法里加入这种出错检查机制
	 */
	public Object remove(){
		
		Object temp = queueArray[front++];       //移除队头元素
		if(front == maxSize){                        //队头指针达最大空间
			front = 0;                                 //将队头置0
		}
		
		nItems--;                                     
		return temp;
	}
						
	/**
	 * 
	 *@liyixiang
	 *@2014-9-21
	 *@param
	 *@return:Object
	 *@TODO:
	 *		获取队头元素
	 */
	public Object peekFront(){
		 return queueArray[front];
	}
	
	/**
	 * 
	 *@liyixiang
	 *@2014-9-21
	 *@param
	 *@return:boolean
	 *@TODO:
	 *		判断队列是否为空
	 */
	public boolean isEmpty(){
		return (nItems == 0);
	}
	
	/**
	 * 
	 *@liyixiang
	 *@2014-9-21
	 *@param
	 *@return:boolean
	 *@TODO:
	 *		判断队列是否为满
	 *
	 */
	public boolean isFull(){
		return nItems == maxSize;
	}
	
	/**
	 * 
	 *@liyixiang
	 *@2014-9-21
	 *@param
	 *@return:int
	 *@TODO:
	 *		获取当前队列元素个数
	 */
	public int size(){
		return nItems;
	}
}


© 著作权归作者所有

清风傲剑
粉丝 31
博文 75
码字总数 40365
作品 0
蚌埠
高级程序员
私信 提问
《数据结构与算法之美》——队列

什么是队列 队列是一种线性表数据结构,和栈类似 它操作受限,表现为先进先出,后进后出 它有头指针和尾指针之分,删除元素从head操作,添加元素从tail操作 基于以上特点,我们看到队列是这样...

Jackie_Zheng
2018/12/15
0
0
数据结构与算法之美——队列——学习笔记

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq_26545305/article/details/88076737 一、前言 众所周知,CPU资源是有限的,任务的处理速度与线程个数并不是...

LemmonTreelss
03/17
0
0
小蚂蚁学习数据结构(6)——线性结构——队列的介绍

队列: 定义:一种可以实现“先进先出”的存储结构 分类: 链式队列——用链表实现 静态队列——用数组实现 静态队列通常都必须是循环队列 循环队列的讲解: 1,静态队列为什么必须是循环队列...

嗜学如命的小蚂蚁
2016/01/03
61
0
nginx源码分析—队列结构ngx_queue_t

本博客(http://blog.csdn.net/livelylittlefish )贴出作者(阿波)相关研究、学习内容所做的笔记,欢迎广大朋友指正! Content 0. 序 1. 队列结构 2. 队列操作 2.1 在头节点之后插入 2.2 ...

晨曦之光
2012/03/09
248
2
前端应该了解的数据结构-栈与队列

一、为什么需要学习数据结构? 1、编程思维是相通的   人们常说,编程语言是相通的,掌握了一门,其他语言很容易掌握。个人觉得这个观点需要辩证看待。   每门编程语言都离不开变量、数组...

小铭子
06/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

linux 定时脚本

1.定时任务基本用法 linux设置定时任务的关键字是:crontab查看当前定时任务:crontab -l新建定时任务的命令是:crontab -e 打开类似vi编辑器向里面新增内容即可 2.参数说明 时间的格...

半张一块
15分钟前
2
0
免费好用的常用软件

UninstallTool 比控制面板的卸载好用的多很小 Everything硬盘搜索快 QuickLook快速查看预览文件不用打开 7Z 、Bandizip比winrar没广告 gogs,gitlab 自架git 服务器 VisualSVN Server,svn服...

momo1987
15分钟前
2
0
@Transactional事务几点注意及其属性Propagation的使用

@Transactional事务几点注意 这里面有几点需要大家留意: A. 一个功能是否要事务,必须纳入设计、编码考虑。不能仅仅完成了基本功能就ok。 B. 如果加了事务,必须做好开发环境测试(测试环境...

小海bug
19分钟前
2
0
10套精美可视化数据分析PPT图表,职场必备

在日常工作当中制作PPT的时,一些麻烦的数据什么的,我们常会用到图表展示,但是图表制作过程中难免会遇到一些问题,可能表达不清楚,或者可能有做得不好看的情况出现等等!其实如果有一些好...

TeFuiro
24分钟前
3
0
拐点已至,云原生引领数字化转型升级

作者 | 易立 阿里云资深技术专家 本文整理自易立在 2019 携程技术峰会上发表的题目为《拐点已至,云原生引领数字化转型升级》的演讲。 关注“阿里巴巴云原生”公众号,回复关键词“转型”即可...

阿里巴巴云原生
26分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部