데이터 구조의 링크 와 배열 (1) - 배열 구현 대기 열

데이터 구조의 링크 와 배열 (1) - 배열 구현 대기 열
1. 배열 과 링크 안내
 
        한 그룹의 데이터 에 대해 컴퓨터 의 메모리 에 저장 되 는 형식 은 연속 저장 과 분 산 된 저장 두 가지 로 나 눌 수 있 는데 이것 은 우리 가 흔히 말 하 는 배열 과 링크 에 대응 된다.메모리 공간 에 충분 한 연속 공간 이 있 을 때 데 이 터 를 메모리 에 연속 적 으로 저장 할 수 있 습 니 다. 각종 프로 그래 밍 언어 중의 배열 은 보통 이런 방식 으로 저장 합 니 다.메모리 에 분 산 된 사용 가능 한 공간 만 있 을 때 이 공간 에 저 장 된 데 이 터 를 연결 시 키 기 위해 서 는 이전 데이터 의 저장 공간 에 다음 데이터 의 주 소 를 기록 해 야 한다. 그러면 첫 번 째 메모리 공간의 주 소 를 알 면 데이터 세트 전 체 를 연결 시 킬 수 있다. 이것 이 바로 링크 가 데 이 터 를 저장 하 는 방식 이다.
        배열 은 연속 으로 저장 되 기 때문에 배열 의 데 이 터 를 조작 할 때 첫 번 째 주소 에서 의 오프셋 에 따라 해당 위치 에 있 는 데 이 터 를 직접 액세스 할 수 있 습 니 다. 그러나 데이터 그룹 에서 임 의 위치 에 요 소 를 삽입 하려 면 먼저 뒤의 요 소 를 단체 로 뒤로 이동 시 켜 저장 공간 을 비 워 야 합 니 다.반면에 링크 는 분 산 된 저장 이기 때문에 데 이 터 를 삽입 할 때 새로운 공간 을 신청 한 다음 에 그 중의 연결 관 계 를 수정 하면 되 지만 링크 에서 데 이 터 를 찾 을 때 하나씩 옮 겨 다 녀 야 한다.이상 의 총 결 을 고려 해 보면 배열 과 링크 는 각각 장단 점 이 있다.구체 적 으로 사용 할 때 는 구체 적 인 상황 에 따라 선택해 야 한다.데 이 터 를 많이 찾 을 때 배열 을 사용 하 는 것 이 좋 습 니 다.데이터 가 집 중 된 데 이 터 를 추가 하거나 삭제 할 때 링크 를 선택 하 는 것 이 좋 습 니 다.  
 
 
2. 배열 실현 대기 열
다음은 배열 을 통 해 데 이 터 를 조작 하 는데 주요 기능 은 다음 과 같다.
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;
	}

 
       이상 은 자신 이 정의 한 배열 을 위 한 대기 열 을 실현 합 니 다. 또한 자바 에서 정 의 된 ArrayList 류 를 사용 하여 대기 열 데 이 터 를 조작 할 수 있 습 니 다. 자세 한 설명 은 하지 않 습 니 다.