数据结构之链表与数组(一)—数组实现队列

数据结构之链表与数组(一)—数组实现队列

一、数组与链表简介

 

        对于一组数据，在计算机的内存中的存储形式可以分为连续存储和离散存储两种，它们对应了我们通常所说的数组和链表。当内存空间中有足够大的连续空间时，可以把数据连续的存放在内存中，各种编程语言中的数组一般都是按这种方式存储的；当内存中只有一些离散的可用空间时，为了能把这些空间中存储的数据联系起来，需要在前一块数据的存储空间中记录下一块数据的地址，这样只要知道第一块内存空间的地址就能环环相扣地把数据集整体联系在一起了， 这便是链表存储数据的方式。

        由于数组是连续存储的，在操作数组中的数据时就可以根据离首地址的偏移量直接存取相应位置上的数据，但是如果要在数据组中任意位置上插入一个元素，就需要先把后面的元素集体向后移一位为其空出存储空间。与之相反，链表是离散存储的，所以在插入一个数据时只要申请一片新空间，然后将其中的连接关系做一个修改就可以，但是显然在链表上查找一个数据时就要逐个遍历了。考虑以上的总结可见，数组和链表各有优缺点。在具体使用时要根据具体情况选择。当查找数据操作比较多时最好用数组；当对数据集中的数据进行添加或删除比较多时最好选择链表。  

 

 

二、数组实现队列

下面通过数组对数据进行操作，主要功能有：

1、在队列末尾添加数据；

public void add(Object obj) {
		// 实例化一个新数组对象，其长度比原数组大一
		Object[] arr2 = new Object[arr.length+1];
		//将原来的数组复制到新的数组
		for(int i=0;i<arr.length;i++){
			arr2[i] = arr[i];
		}
		//在arr2数组的最后添加obj
		arr2[arr.length-1] = obj;
		//覆盖原数组
		arr = arr2;
	}

 

 

2、从队列中取指定位置的数据；

public Object get(int index) {
		// TODO Auto-generated method stub
		//判断index是否超出队列
		if( index < 0 || index >arr.length-1){
			//提示错误
			System.out.println("index= "+index+" 超出队列范围");		}
		//返回该数据
		else{
			return arr[index-1];
		}
	}

 

 

 

3、删除队列中指定位置的数据，并且返回被指定删除的数据；

public Object remove(int index) {
		// TODO Auto-generated method stub
		//判断index是否超出队列
		if( index < 0 || index >arr.length-1){
			//提示错误
			System.out.println("index= "+index+" 超出队列范围");
		}
		else{
			//新建一个数组
			Object[] arr2 = new Object[arr.length-1];
                 //将该数据保存
			Object a = arr[index-1];
			//把要删除的数据之前的数据复制到新数组
			for(int i = 0 ; i < index; i++){
				arr2[i] = arr[i];
			}
			//将之后的数据复制到新数组
			for(int i = index-1;i < arr2.length;i++){
				arr2[i] = arr[i+1];
			}
			//覆盖原数组
			arr = arr2;
			//返回被删除的数据
			return a;
		}
		
	}

 

 

 

4、插入数据到队列中的某个位置；

 

//将数据obj插入到队列的index位置
	public void inser(int index, Object obj) {
		// TODO Auto-generated method stub
		//判断index是否超出队列
		if( index < 0 || index >arr.length-1){
			System.out.println("index= "+index+" 超出队列范围");
		}
		else{
			Object[] arr2 = new Object[arr.length+1];
			//复制index位置前的数据
			for(int i = 0 ; i < index-2;i++){
				arr2[i] = arr[i];
			}
			//复制index位置后的数据
			for(int i = index; i < arr.length;i++){
				arr2[i] = arr[i];
			}
			//插入新数据
			arr2[index-1] = obj;
			//覆盖原数组
			arr = arr2;
		}
	}

 

5、返回原队列中数据的长度；

public int size() {
		// TODO Auto-generated method stub
		return arr.length;
	}

 

       以上为自己定义的数组实现队列，此外，我们仍可以使用Java中已定义好的ArrayList类来对队列数据进行操作，此处不详细介绍。