数组队列学习

数组队列

队列这个名词，字面上除了让人想着他可能是军训的时候我们排着的一对或一列之外，没有别的很直面意思。

     学习后大概了解到，在程序语言上，队列归属于一种数据存储结构。刚接触的时

候，一提到队列，“先进先出”四个字就在脑袋里晃啊晃，其修改原理就是秉着“先进先出”的原则~~~

   好比我们在排队买票的时候，排在队伍前面的人先买，后面来的人只能往队伍后面站，强行硬插的话就会被人指责一样，先排队的先办完事走人。

 

 

      队列的操作可以由数组和链表两种形式实现。

     上一篇博客有写过链表实现队列的过程，这一篇来总结一下数组实现队列的过程！！

  I think：

       相比链表，数组实现队列的代码会比较好写一些，他不用像链表一样需要通过引用来从头开始查找，而是直接用下标就可以找到相应位置的数据。

        只是数组在一开始就要必须定义他的大小，如果小了就会越界，过大又会浪费内存。

        要改动数据时，得再定义一个数组，将改动后不会变的初始数组元素与改动数据一个一个的重新赋予给新的数组，最后再把新数组的地址传让初始的数组。

 

.额......还是直接上代码来说明一切吧~

 

首先目标是：通过数组队列，存储学生信息，实现学生信息的添加，删除，修改，查找,插入等方法。

 

一，定义一个学生类，存储学生的姓名和学分信息。

 

public class Students {
	
		private String name;//声明姓名属性
		private int score;//声明学分属性
		
		/**
		 * 构造方法，用来创建对象的（类名 对象名 = new 构造方法(参数值,...);）
		 */
		public Students(String name,int score){
			this.name = name;
			this.score = score;
		}
		/**
		 * 给姓名属性设置值的方法
		 * @param name要赋给属性的参数
		 */
		public void setName(String name){
			this.name = name;
		}
		/**
		 * 获取姓名属性值的方法
		 * @return name姓名属性的值
		 */
		public String getName(){
			return name;
		}
		
		public void setScore(int score){
			this.score = score;
		}
		
		public int getScore(){
			return score;
		}
		/**
		 * 重写一个toString方法
		 */
		public String toString(){
			return "姓名："+name+"   学分："+score;
		}
		
	}

 

二，定义一个数组队列类

 

public class StuArrayQueue {
	// 声明一个初始数组
	private Students[] array;
	// 声明一个存储元素总数的计数器
	private int size = 0;
	// 声明一个变量，用来计算数组中能存储多少个元素
	private int length;

	/**
	 * 构造方法
	 */
	public StuArrayQueue() {
		array = new Students[0];
	}

	/**
	 * 构造方法
	 * 
	 * @param length表示初始数组队列的大小
	 */
	public StuArrayQueue(int length) {
		this.length = length;
		array = new Students[length];
	}

	/**
	 * 向数组队列中添加元素的方法
	 * 
	 * @param stu就是要添加到数组队列中的元素
	 */
	public void add(Students stu) {
		if (length <= size) {// 如果初始数组队列的大小<=元素的个数
			// 创建一个新数组，是初始数组的长度+1.
			Students[] temp = new Students[size + 1];
			// 将初始数组中的数据存入到temp中
			for (int i = 0; i < array.length; i++) {
				temp[i] = array[i];
			}
			temp[size++] = stu;// 将新数据存入到temp数组的末尾

			array = temp;// 将temp数组名中存储的地址赋给array
		} else {
			array[size++] = stu;
		}
	}

	/**
	 * 获取指定索引位置的元素
	 * 
	 * @param index指定的索引位置
	 * @return 返回null表示索引不存在，否则会返回对应索引的元素
	 */
	public Students get(int index) {
		if (index < 0 || index >= size) {
			throw new RuntimeException("索引越界！");
		}
		return array[index];
	}

	/**
	 * 移除索引位置的元素值
	 * 
	 * @param index
	 */
	public Students remove(int index) {
		Students a = array[index];
		if (index < 0 || index > size) {
			throw new RuntimeException("索引越界");
		} else {
			Students[] temp = new Students[array.length - 1];// 重新定义一个数组temp，长度比Array小一

			for (int i = 0; i < index; i++) {// index之前的temp值都与Array相等
				temp[i] = array[i];
			}
			for (int j = index; j < array.length - 1; j++) {

				temp[j] = array[j + 1];
			}
			array = temp;// 不可少
		}
		size--;// 数组元素个数递减
		return a;
	}

	/**
	 * 在在数组队列中插入元素
	 * 
	 * @param s为要插入的元素
	 * @param index为想要插入元素的位置
	 *            
	 */
	public void addNew(Students stu, int index) {
		if (index < 0 || index > size) {
			throw new RuntimeException("索引越界");
		} else {
			Students[] temp = new Students[array.length + 1];
			for (int i = 0; i < index; i++) {
				temp[i] = array[i];
			}
			temp[index] = stu;
			for (int j = index; j < array.length; j++) {

				temp[j + 1] = array[j];
			}
			array = temp;// 不可少
		}
		size++;
	}
	/**
	 * 根据内容得出元素所在的位置
	 * @param stu 想要找到的元素的数据
	 * @return j 为元素所在的位置
	 */
	public int get(Students stu){
		int j=0;
		for (int i = 0; i < size; i++) {
		    if(array[i].getName()==stu.getName() && array[i].getScore()==stu.getScore()){
		    	j=i;
		    }
		}
		return j;
	}
	/**
	 * 根据内容删除
	 * @param stu 想要删除的内容
	 */
	public void remove(Students stu){
		remove(get(stu));
	}

	/**
	 * 获取数组队列中存储的元素总数
	 * 
	 * @return 返回size
	 */
	public int size() {
		return size;
	}
}

 

三，然后就是检验方法是否有效的测试类了。

 

public class StuQueueTest {

	public static void main(String[] args) {
		//创建数组队列的对象
		StuArrayQueue queue = new StuArrayQueue();
		//添加数据
		queue.add(new Students("张三",50));
		queue.add(new Students("李四",62));
		queue.add(new Students("王五",64));
		queue.add(new Students("赵六",60));
		queue.add(new Students("李明",90));
		
		//检验添加
		System.out.println("增加后长度为"+queue.size());
		System.out.println("增加后为" );
		for(int i=0;i<queue.size();i++){
			System.out.println(queue.get(i).toString());
		}
		System.out.println();
		
		//检验索引
		System.out.println("索引位置的值为");
		System.out.println(queue.get(0));
		System.out.println(queue.get(1));
		System.out.println(queue.get(2));
		System.out.println(queue.get(3));
		System.out.println(queue.get(4));
		System.out.println();
		
		//检验删除
		System.out.println("删除的为"+queue.remove(4));
		System.out.println("删除后长度为"+queue.size());
		System.out.println("删除后为" );
		for(int i=0;i<queue.size();i++){
			System.out.println(queue.get(i).toString());
		}
		System.out.println();
		
		//检验插入
		queue.addNew(new Students("小风",50),4);
		System.out.println("添加长度为"+queue.size());
		System.out.println("添加后为" );
		for(int i=0;i<queue.size();i++){
			System.out.println(queue.get(i).toString());
		}
		System.out.println();
		
		//检验根据内容查找
		System.out.println("在"+queue.get(new Students("李四",62)));
		System.out.println();
		
		//检验根据内容删除
		queue.remove(new Students("李四",62));
		System.out.println("删除后长度为"+queue.size());
		System.out.println("删除后为" );
		for(int i=0;i<queue.size();i++){
			System.out.println(queue.get(i).toString());
		}
		System.out.println();
	}
}

 

后记:

     相比之前写链表，数组队列的实现耗时还是比较短的。

     但是现在在学习的哈夫曼，编码那一块儿又遇到了瓶颈，百思不得其解的感觉相当的不好,.

     虽然觉得时间紧迫，但是也知道一口就想吃成胖子的想法很不好，循序渐进，多复习多积累吧。

 

                                                   ------------I am a slow walker,but I never walk backwards.

(Abraham.Lincoln America)

评论

1 楼 java--hhf 2014-11-20  

一手沙发，绝对新鲜