Think Different and Hunger for

테이블 - 키를 통해서 탐색대상을 담번에 찾을 수 있는 자료구조 형태 

그러므로 시간 복잡도 가 O(1)  이다 

하지만 테이블에 문제점이 있다  

문제점 1. 조회번호 의 범위가 생성한 배열의 인덱스 값보다 큰 경우

   2. 그러므로 조회번호의 범위를 수용 할 수 있는  매우 큰 배열이 필요하다.

위 두가지 문제점을 해결 해주는것이 해쉬 함수 이다 

어느회사의 직원의 조회번호를 입사년도와 입사순서로 조합 했다고 가정하자 예로 2012년 3번째 입사한사람의 조회번호는20120003 이다 

이 조회 번호를  getHashValue 라는 함수에 넣어서 해쉬값을 구한다는 전제하에 간단한 getHashValue 함수를 작성하겠다 

public int getHashValue(int 조회번호){

reurn 조회번호 % 100 ; 

}

20120003 넣었을시 03 이 답이다 

위의 함수의 의미는 100 으로 % 연산을 햇는데 즉  여덟자리의 수로 이뤄진 조회번호를 두자리의 수로 변경한다  이다 

위와 같은 함수를 해쉬 함수라고 한다 . 해쉬 함수의 역할은 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다.

위와 같이 해쉬 함수를 이용했을때 문제가 발생한다 예로 2012년에 100명 이상의 직원이 채용된경우 20120003 과 20120103을 부여받은 직원이 생겨나는데 둘다 위 해쉬 함수에 넣으면 같은 해쉬 값인 3을 얻게 된다 . 

즉 해쉬값 충돌이라는 문제가 생기게 된다 .

이 해쉬값 충돌로 인해서 좋은 해쉬 함수와 좋지 않은 해쉬 함수가 구분이 되는데 

예로  

1..좋은 해쉬 함수의 메모리 구성 12개의 데이터가 입력되있경우 

|        |      ||   |     |       |     |     |     |  |   |

메모리의 시작                                        메모리의 끝  

2.좋지 않은 해쉬 함수의 메모리 구성 12개의 데이터가 입력되있경우

|     |    |     ||||||                |||                  |

메모리의 시작                                     메모리의 끝

결론은 좋은 해쉬 를 쓰면  데이터가 골고루 저장 되고  나쁜 해쉬를 쓰면 데이터가 골고루 저장이 안된다. 

좋은 해쉬 함수를 구성하기위한 일반적인 조언은 - 작은 수의 데이터의 조합으로 해쉬값을 생성할때 보다 다양한 수의 데이터 조합으로 했을때 다양한 해쉬값이 나오고 데이터는 다양한곳에 메모리 골고루에 저장된다

데이터 조합 방법으로는 -자릿수 선택 방법과 자릿수 폴딩 방법 

충돌 해결 방법 

1.열린어드레싱방법 -- 충돌이 나면 그곳을 피해서 값을 집어 넣는다 

즉  충돌이 나면 빈곳이 어딘가 탐색해서 빈곳에 값을 넣는식이다 .

그러므로 탐색 방법에 의해서 구분이 된다 

1-1. 선형 조사 방법 -- 위의  20120003 과 20120103을 부여받은 직원이 생겨나는데 둘다 위 해쉬 함수에 넣으면 같은 해쉬 값인 3을 얻게 된다 .  경우를 예를 들어서 얘기하겠다 

위와 같은 경우 3의 바로 옆자리인 4의 자리에 데이터의 값을 넣는다.만약에 4의 자리도 빈곳이 아니라면 5가 비었는지 본다 

이와 같이 충돌이 일어나는 곳의 바로 옆을 탐색한다. 

선형 조사의 탐색 순서는 그러므로 다음과 같이 전개된다.

f(k)+1 -> f(k)+2 -> f(k) +3  ......... 

그러므로 클러스터 현상(한곳에 밀집되서 충돌이 계쏙 일어나는 현상)이 일어난다는 단점이 있다 

이러한 점을 극복하기 위해 이차 조사방법이 나왔다.

1-2.이차 조사 방법 -- 1.1의 문제점을 극복하기 위해서 " 좀 더 멀리 떨어진 곳에서 빈곳을 찾으면 어떨까라는 "생각에 맞춘 조사 방법 

이와 같은 생각에 근거해서 이차조사방법의 전개도는 아래와 같다.

f(k)+1^2 -> fi(k)+2^2 -> f(k)+2^3 -> f(k)+2^4 -> f(k)+2^5 -> f(k)+2^6 ....

즉 선행 조사법은 충돌시 n칸 옆으로 이동하면서 조사를 한다면 이차 조사법은 충돌시 n^2칸 옆으로 이동하면서 빈칸이 없는지 조사를 한다 .

단점 -- k가 다르더라도 f(k)에 대한 해쉬 값이 같아면  일정한 부분만 조사하게 되서 클러스터 현상이 발생할 확률은 여전히 높다.

1-3. 이중 해쉬 - 이차 조사 방법의 단점을 해결하기 위한 가장 이상적인 충돌 해결책  

이차 조사법의 단점을 극복하기 위해서 

이중 조사법은 좀 멀리서 빈공간을 찾긴 하지만  그 빈 공간을 선택하는 방식이 한칸 , 네칸 , 아흡칸  이런식으로 규칙적인 부분을  좀 불규칙하게 구성 하면 된다 .

1차 해쉬 함수  - 키를 근거로 저장위치를 결정하기 위한 것 

2차 해쉬 함수 - 충돌 발생시 몇 칸 뒤를 살필지 결정하기 위한 것 

예로  1차 해쉬 함수 를  아래와 같이 정의한다고 가정하자

H1(K)=K%15

위의 식의 근거로 이중해쉬의 2차 해쉬 함수를 결정하게 된다 

H2(K)=1+(K%C)

위의 2차 해쉬 함수식이 절대적인 것은 아니지만 일반적인 형태이다.

이러한 식에서 C를 구해주는 방법은  1차 해쉬 함수를 %15로 결정한 것으로 보아 , 배열의 길이가  15라고 예상해 볼 수 있다 . 

 이와 같이 가급적 2차해쉬 값이 1차 해쉬 값을 넘어서지 않게 하기 위함은  1차 해쉬 최대값이 14인데 2차 해쉬의 최대 값이 32 라면 빈자리를 찾아서 몇 바퀴 돌아야 할 지 모르기 때문이다.

즉  위와 같은 경우 C는  15보다 작은  그러면서도 소수 중 하나로 결정을 하면된다.

여기서 C를 소수로 결정하는 이유는  소수 선택했을 시 클러스터 현상의 발생 확류를 현저히 낮춘다는 통계를 근거로 한다. 

그리고 먼저 1을 더하는 이유는  2차 해쉬 값이 0이 되는 것을 막기 위해서이다.

위를 기준으로  2차함수를  H2(K)=1+(K%C) 로 한다는 전제하에 예를 들겠다. 

예로  키 3  , 18 , 33 을 넣었을때 생기는 과정을 보여주겠다.

H1(3)=3%15=3

H1(18)=18%15=3

H1(35)=33%15=3

이러한경우 18 35는 해쉬 값이 같아서 충돌이 발생하므로 2차 해쉬 함수에 넣어준다 

H2(18)=1+18%7=5 

H2(33)=1+33%7=6

위 와 같이 1차 해쉬 값은 같아도 2차 해쉬 값은 다르다 그리고 이 2차 해쉬 값을 근거로 빈슬룻을 찾는 과정은 각각 다음과 같이 전개가 된다 

H2(18) -> H2(18)+5*1 -> H2(18)+5 *2 -> H2(18)+ 5*3 .....

H2(33) -> H2(33) + 6*1 -> H2(33)+6*2 -> H2(33) +6*3 ....

위 와 같이 2차 해쉬 값의 크기만큼 건너 뛰면서 빈 슬룻을 찾게 되므로  키가 다르면 건너 뛰는 길이도 달라져서 클러스터 현상의 발생확률을 현저히 낮출 수 있다.

2. 닫힌어드레싱방법--충돌이 나도 반드시 그자리에  값을 집어 넣는다 

체이닝

2-1. 배열기반 

2-2. 링크드 리스트 기반 

아래는 간단한 배열 기반 테이블 소스 

package Datastructure;

import java.util.Scanner;

public class Tablearray {

int prinum;

int age;

public static void main(String[] args) {

Tablearray []ta= new Tablearray[1000];

Tablearray tmp;

Tablearray t= new Tablearray();

int searchnum;

Scanner sc = new Scanner(System.in);

System.out.println("사번입력:");

t.prinum=sc.nextInt();

System.out.println("나이 입력:");

t.age=sc.nextInt();

ta[t.prinum]=t;// 여기가 포인트 

System.out.println(" 조회할 사번:");

searchnum=sc.nextInt();

    tmp=ta[searchnum];

    System.out.println("나이 :"+tmp.age +","+"검색 키:"+ tmp.prinum);

}

}

이중 해쉬를 구성할 시에  슬롯의 상태 정보를 별도로 관리 해야한다 

그러한 이유는  예로  해싱 함수가 key% 7  인 경우로 예를 들겠다.

key 값이 9인 데이타의  해쉬 값은 2이다 

그림 아래와 같이 9가 2에 들어가게 될것이다        

   9

|0 | 1| 2 | 3 | 4 |  5 |  6 | 7 | 8 | 9 | 

이어서 키값이 2인 데이터 가 등장하면  똑같이 해쉬 값이 2가된다 

여기서 선형조사법식으로 값을 넣는다면 아래와 같을 것입니다.

   9   2

|0 | 1| 2 | 3 | 4 |  5 |  6 | 7 | 8 | 9 | 

이러한 상태에서  9를 삭제한다고 한다면 

아래와 같이 됩니다.

        2   

|0 | 1| 2 | 3 | 4 |  5 |  6 | 7 | 8 | 9 | 

 E  E  D  I    E    E   E    E   E   E

슬롯의 상태는 아래와 같습니다.  

EMPTY - 이 슬룻에는 데이터가 저장된 바가 없다.

DELETED -이 슬롯에는 데이터가 저장된바 있으나 현재는 비워진 상태이다.

INUSE - 이 슬룻에는 현재 유효한 데이터가 저장되어 있다.

슬롯의 상태를 주는 궁극적인 이유는  데이터가 삭제된 슬룻의 상태 정보를 DELETE로 두어 EMPTY 와 구분 하였다는 것입니다. 

위와 같은 상황에서 키가 2인 데이터를 탐색을 진행하기 위해서는 %7의 해쉬 함수를 거친다. 그리고 그결과로 얻은 2를 인덱스 값으로 하여 탐색을 진행 하게 된다 . 만약에 그위치의 슬롯 상태가 EMPTY 라면 데이터가 존재하지 않는다고 판단 탐색을 종료 한다 . 그 옆자리를 확인 하지 않은 채 말이다. 

반면 DELETED 상태임을 확인한다면 충돌이 발생했음을 의심하여 선형  조사법에 근거한 탐색의 과정 진행한다.

http://blog.daum.net/_blog/BlogTypeView.do?blogid=0MMaA&articleno=8039326&categoryId=719070&regdt=20120915060134

체이싱

http://sowlgns.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%ED%95%B4%EC%8B%B1

각각의 노드는 유일한 키 값을 가지게 되는데, 노드 중에서 최대값이나 최소값을 빠른시간 내에 찾기 위해서 만든 자료구조가 바로 힙(Heap)이다. 

우선 배열로 트리를 구성하기 위해서 노드에 고유한 번호를  부여한다  그리고 

각 번호가  각 노드의 데이터가  저장될  배열의 인덱스 값이 된다 

  1:A

2:B        3:C

4:D   5:E

구현의 편의를 위해서 인덱스 0의 위치의 배열 요소는 사용하지 않는다 .

배열 기반의 힙을 구성하기 위해서 알아야 할것들 

1. 왼쪽과 오른쪽 자식노드의 인덱스의 값을 얻는 방법 

2. 부모의 인덱스를 얻는 방법 

왼쪽 자식 노드의 인덱스 값 -- 부모노드의 인덱스 값 * 2

오른쪽 자식 노드의 인덱스 값 -- 부모노드의 인덱스 값 * 2+1

부모노드의 인덱스 값-- 자식 노드의 인덱스 값 /2

자식의 노드의 인덱스 값을 얻는 이유는 데이터의 삭제를 위해서 

부모의 노드의 인덱스 값을 얻는 이유는 데이터 추가를 위해서 

여기서 부모노드의 인덱스 값을 구할때 정수 형 나눗셈이다  즉 5를 2로 나누었을때 결과는 2.5 가 아닌 2이다 .

1.힙 구현 삽입시

힙을 구현 하기위해서는  마지막 위치(마지막 레벨 노드에 오른쪽 위치)에 노드 추가 한후  그리고 마지막위치에 추가한 노드와 그의 부모노드를 계속해서 비교해서 제대로된 위치에 위치 시킵니다.

2. 힙 구현 삭제시 

-1 루트 삭제 

-2 맨 아래 레벨의 오른쪽 노드를  비어져 있는 루트에 옮겨 놓고 옮겨진 루트의 자식노드 두개중에 우선순위가 높은것과 비교해서 올바른 자리를 자리를 찾아간다 .

2-1. 루트의 자식노드 두개중과 우선순위가 낮은것과 비교해서 스왑을 안하는 이유는 그렇게 했을 경우 힙의 기본조건이 무너지기 때문이다. 

힙을 구현을 할려면 링크드리스트 ? 배열 ? 어느것이 원칙일까?

답은 배열이다 

왜냐하면  연결리스트를 기반으로 힙을 구현 하면 새로운 노드를  힙의 마지막의 위치에 추가 하는것이 쉽지 않다 .

힙 소스의  * Hinsert --힙에 데이터 삽입  ,* Hdelete --힙에 데이터 삭제  는  우선순위 큐의 enqueue , dequeue 연산 결과와 일치한다   

package Datastructure;

/*GetparentIdx -- 부모 노드의 인덱스 값 반환 

 * GetRchildIdx --  오른쪽 자식노드의 인덱스 값 반환 

 * GetLchildIdx -- 왼쪽 자식노드의 인덱스 값 반환 

 * minHeapify--  루트와 자식노드를 비교 해서 루트와 자식 값 변경 해주는 함수 삭제시 이용한다 

 * isLeaf -- 비교할 자식이 있는가  

 * Hinsert --힙에 데이터 삽입 

 * Hdelete --힙에 데이터 삭제 

 * MinHeap 으로 구현 할것이다

 * root 값이 가장 작다 

 *1.힙 구현 삽입시

힙을 구현 하기위해서는  마지막 위치(마지막 레벨 노드에 오른쪽 위치)에 노드 추가 한후  그리고 마지막위치에 추가한 노드와 그의 부모노드를 계속해서 비교해서 제대로된 위치에 위치 시킵니다.

2. 힙 구현 삭제시 

-1 루트 삭제 

-2 맨 아래 레벨의 오른쪽 노드를  비어져 있는 루트에 옮겨 놓고 옮겨진 루트의 자식노드 두개중에 우선순위가 높은것과 비교해서 올바른 자리를 자리를 찾아간다 .

 *

 */

public class Heaparray {

int [] heap;

int heapsize;

//int priority;

int capacity; 

public Heaparray(int size){

heap = new int [size];

heapsize=1;

this.capacity =size;

}

public boolean isempty(){

if(heapsize==0){

return true;

}

else {

return false;

}

}

public boolean isfull(){

if(heapsize ==capacity){

return true;

}else{

return false;

}

}

public void Hinsert(int input){

if(isfull()){

System.out.println("heap overflow error");

}

else {

heap[heapsize]=input;

int current=this.heapsize;// 이게 포인트다 이 부분을 안해주고 heapsize를 이용해서 while문을 돌리면 current=GetparentIdx(current)에서 heapsize를 건드려줘서 소스가 꼬인다

while(heap[GetparentIdx(current)]>heap[current]){//minheap 구현 전제하로  마지막노드랑 부모랑 비교 해서 마지막노드가 부모노드 보다 값이 작으면 바꿔줘야한다 

int tmp = heap[current];

heap[current]=heap[GetparentIdx(current)];

heap[GetparentIdx(current)]=tmp;

current=GetparentIdx(current); // 부모로 따라 올라가게 하기 위한 한줄 

}

this.heapsize++;

}

}

public boolean isLeaf(int idx){//비교할 자식이 있는가?

//마지막  바로윗레벨 과 제일 마지막 레벨에서 부모와 자식은 힙이 성립 하는 이상 비교 할필요가 없으므로 마지막 바로전 레벨에 도착하면 이함수를 끝내준다

if(idx>=(heapsize/2)&& idx<heapsize){// insert 마지막에 heapsize++를 해줘서 < 로 해줌  

//GetparentIdx(idx)>=1&&idx<this.heapsize 자식인가의 조건이 아님 

//heap[idx]>heap[1]&&heap[heapsize-1]>=heap[idx] 이조건은 실패 

System.out.println("비교할자식이 없다");

return false; //

}else{

System.out.println("비교할자식이 있다");

return true; // 

}

}

public void minHeapify(int idx){

if(isLeaf(idx)){// 비교할 자식이 있다면 

if(heap[idx]>heap[GetLchildIdx(idx)]|| heap[idx]>heap[GetRchildIdx(idx)]){

if(heap[GetLchildIdx(idx)] <heap[GetRchildIdx(idx)]){// 왼쪽자식이 작은경우 왼쪽자식이랑 루트랑 바꺼줌

int tmp=heap[idx];

heap[idx]=heap[GetLchildIdx(idx)];

heap[GetLchildIdx(idx)]=tmp;

minHeapify(GetLchildIdx(idx));

}else{// 오른쪽 자식이 작은경우 오른쪽 자식이랑 루트랑 바꺼줌

int tmp=heap[idx];

heap[idx]= heap[GetRchildIdx(idx)];

heap[GetRchildIdx(idx)]=tmp;

minHeapify(GetRchildIdx(idx));

}

}

}

}

public void Hdelete(){

int front=1;

heap[front]=heap[heapsize-1];// insert heapsize++; 때문에

heap[heapsize-1]=0;

heapsize--;

minHeapify(front);// 루트부터 자식들을 비교하는 과정 

}

public int GetparentIdx(int idx){

return idx/2;

}

public int GetLchildIdx(int idx){

return idx*2;

}

public int GetRchildIdx(int idx){

return idx*2+1;

}

public void see(int a[]){

for(int i=0; i<this.heapsize; i++){

System.out.println(a[i]);

}

}

public static void main(String[] args) {

Heaparray h = new Heaparray(7);

h.Hinsert(5);

h.Hinsert(6);

h.Hinsert(3);

h.Hinsert(1);

h.Hinsert(2);

h.Hinsert(4);

//h.see(h.heap);// 일단 insert 부분 성공 

h.Hdelete();

h.Hdelete();

h.see(h.heap);

//h.isLeaf(7);

//System.out.println(h.heapsize);

//System.out.println(h.heap[h.heapsize]);// heapsize를 인서트문에서 올려줘서 outofboundexception 뜬다

// 정렬 이 안되서 맨마지막 노드가 5인데  5보다 커서  즉 인덱스가 루트인덱스 부터 마지막 인덱스까지 인경우  이런식 접근으로 하면안돌거같은데

// 부모가 존재하는지 

}

}

/*test

 * int a[]= new int [2];

a[0]=Integer.MIN_VALUE;

System.out.println(a[0]);*/

                                               1

                                   2                     4

                          6           3          5

이런식으로 나왔습니다  

모든 부모들은 자식보다는 작은 값이라는 전제는 전부 지켜졌습니다. 

하지만  2의 오른쪽 자식 노드 값 3은  1의 오른쪽 자식 노드 보다 작은 값이지만 더 낮은 레벨에 있습니다 . 

이상태여도 힙인 상태인지 의문이 들었는데요 

이 의문에 대한 답은 힙이다  

두번째 의문  2의 왼쪽 자식과 오른쪽 자식의 값이 왠지  바껴야 힙이 될거 같지만  지금 이대로도 힙이 성립 되는것이다 .

위 소스 결과 값 

                      1

                                   2                     4

                          6           3          5

delete 하고 나서 

2

3 4

6 5

delete  하고 나서    

3

5 4

6

http://lemeraldl.tistory.com/admin/entry/post/?id=168

http://www.sanfoundry.com/java-program-implement-binary-heap/

http://www.sanfoundry.com/java-program-implement-min-heap/

우선순위 큐 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

구현 방법 

1. 배열 기반 

2. 힙 기반 

3. 링크드 리스트 기반

하지만 1번과 3번 같은경우 두가지 큰단점이 있다 

1.데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다 

2. 삽입의 위치를 찾기 위해서 배열에 저장된 모든데이터와 우선순위의 비교를 진행해야 할 수도 있다,

힙 의 종류 - 최대힙(루트값이 가장 크다) , 최소힙(루트가 가장 작다) 

이러한 단점을 극복하기위해 우선순위 큐는 주로 힙으로 구현된다 

주의 해야할 점은 힙과 우선순위 큐를 동일하게 인식 하면 안된다 .

즉 우선순위 큐와 힙을 어느정도 구분 할 줄 알아야한다 . 

힙은 우선순위 큐의 구현에 딱 어울리는 완전 이진트리의 일종이라는 사실을 기억해야 한다.

우선순위큐를 구현하기위해서 

1. 힙을 구현 

2. 힙 구현 기반으로 우선순위 큐 구현

1.힙 구현 삽입시

힙을 구현 하기위해서는  마지막 위치(마지막 레벨 노드에 오른쪽 위치)에 노드 추가 한후  그리고 마지막위치에 추가한 노드와 그의 부모노드를 계속해서 비교해서 제대로된 위치에 위치 시킵니다.

2. 힙 구현 삭제시 

-1 루트 삭제 

-2 맨 아래 레벨의 오른쪽 노드를  비어져 있는 루트에 옮겨 놓고 옮겨진 루트의 자식노드 두개중에 우선순위가 높은것과 비교해서 올바른 자리를 자리를 찾아간다 .

힙을 구현을 할려면 링크드리스트 ? 배열 ? 어느것이 원칙일까?

답은 배열이다 

왜냐하면  연결리스트를 기반으로 힙을 구현 하면 새로운 노드를  힙의 마지막의 위치에 추가 하는것이 쉽지 않다 .

이어서 http://lemeraldl.tistory.com/admin/entry/post/?id=171

[자료 구조] 힙(Heap)

자바(Java)예제로 구현한 힙(Heap) 자료 구조

힙(Heap) 이란 무었인가?

힙(Heap)은 완전 이진 트리(Complete Binary Tree)로, 각각의 노드가 자신의 부모 노드보다 작거나 같은 값을 저장하는 자료형 이다. 힙(Heap)은 완전 이진 트리(Complete Binary Tree)라 가장 아래에 있는 노드들을 제외한 모든 노드들이 두 자식 노드를 모두 가지고 있거나 아예 자식 노드를 가지지 않는 특성을 가진다.

• 만약 부모 노드가 자식 노드보다 크거나 같다면 그건 "Max Heap"(최대 힙)
• 부모 노드가 자식 노드보다 작거나 같다면 "Min Heap"(최소 힙) 이라 불린다.

힙(Heap) 컨셉

힙(Heap)은 실제로 어디에 사용될까?

• Heapsort(힙 정렬)
• 우선 순위 큐(Priority Queue)
• 힙 자료 구조는 우선 순위 큐를 구현하는데 많이 쓰인다
• 다양한 알고리즘(Algorithm) 구현

참조 사이트 

http://muckycode.blogspot.kr/2015/01/heap_11.html 

스택과 큐의 차이점이 앞에서 꺼내느냐 뒤에서 꺼내느냐에 있으니 , 이전에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하면 큐가 될 것 같다.  라고 착각을 했지만 

큰 차이가 있다 

아래는 enqueue 과정 입니다.

배열 A   1   

F R

enqueue 1    2

F    R

enqueue 1    2    3

 F        R

위 배열은 F 가 가리키는 것이 큐의 머리이고 , R 이 가리키는 것이 큐의 꼬리 이다 . 

따라서 enqueue 연산 시 R이 그다음 칸을 가리키게 되고 그자리에 새데이터가 저장된다 

그렇다면 dequeue 연산 시에는 어떠한 데이타를 반환 하고 소멸해야 하겠는가?  F가 가리키는 데이터가 저장 순서가 가장 앞선 데이터이므로 F가 가리키는 데이터를 대상으로 dequeue 연산을 진행해야한다 

즉 F를 참조하여 dequeue 연산을 하고 , R 을 참조하여 enqueue 연산을 한다 . 

즉 큐는  뒤로넣고 앞으로 빼는 자료구조이다. 

package Datastructure;

/*

 * isEmpty -- empty 상태인지 확인

 * clear -- 큐내부의 모든 자료들을 삭제한다

 * isFull

 * enQueue-- que의 rear부분에 새로운 데이터 삽입

 * dequeue-- que의 front 부분에서 가장 front쪽의 데이터를 삭제 

 * peek -- front 위치의 데이터를 반환 

 */

public class Quepractice {

Object queue[];

int rear ;// enqueue에 이용

int front ;// dequeue에 이용 

int size ;

public Quepractice(int size){

queue=new Object[size];

rear=front=-1;

this.size=size;

}

public boolean isempty(){

if(rear==-1){

return true;

}

else{

return false;

}

}

public boolean isfull(){

if(rear==this.size -1){

return true;

}

else{

return false;

}

}

public void clear(){

}

public void enqueue(Object input){

if(isfull()){

System.out.println("error");

}else{

rear++;

queue[rear]=input;

}

}

public void dequeue(){

if(this.front>this.size-1){

System.out.println("error");

return;

}

else{

this.front++;

queue[front]=0;

rear--;

}

}

public Object peek(){

System.out.println(queue[rear]);

return queue[rear];

}

public void see(){

for(int i=0; i<rear+1; i++){

System.out.println(queue[i]);

}

}

public static void main(String[] args) {

Quepractice q= new Quepractice(6);

q.enqueue(1);

q.enqueue(2);

q.enqueue(3);

q.enqueue(4);

q.enqueue(5);

q.enqueue(6);

//q.enqueue(7);// 6개 공간만 만들어졌다 배열은 인덱스 6까지로 착각함 

q.dequeue();

q.dequeue();

q.dequeue();

q.dequeue();

q.dequeue();

q.dequeue();

//q.dequeue(); //7번째 아웃오브 인덱스 뜸 

q.see();

//System.out.println(q.isfull());

//System.out.println(q.isempty());

// test 

/* int a[]= new int [6];

for(int i=0; i<a.length;i++){

System.out.println(i);

}*/

}

}

package Datastructure;

import java.util.Stack;

/*

 * empty();-- 스택이 비어있는지 검사 

 * peek(); 스택 맨위의 객체 리턴 

 * pop();  스택 맨위 객체 삭제 

 * push(); 새객체를 스택 맨위에 삽입

 * search(); 원하는 객체의 위치를 리턴 

 * 

 */

public class Stackpracticearray {

 int top=0;

 Object stack[];

 int size=0;

 public Stackpracticearray(int size){

stack = new Object [size];

this.size=size;

 }

 public boolean empty(){

if(top==-1 ){

return true;

}

else{

return false;

}

 }

 public Object peek(){

System.out.println(stack[this.top-1]);

return stack[this.top];

 }

  public void pop(){

if(top<0){

System.out.println("error");

}

else{

top--;

stack[top]=0;

}

  }

  public void push(Object input){

  if(top> size-1){

  System.out.println("error");

  }

  else{

  //top++;

  stack[top++]=input;// top -1로 두면 아웃오브 인덱스 뜸  이렇게 하고 -1 을 하면 -1에는 아무것도 없고 0에서 부터 채워서 그런듯?

  }

  }

  public int search(Object search){

  Object s=null;

  for(int i=0; i<top;i++){

  s=stack[i];

  if(s == search)

  {

  search=s;

  }

  }

return (Integer) search;

  }

  public void see(){

  Object s=null;

  for(int i=0; i<top;i++){

  s=stack[i];

  System.out.println(s);

  }

  }

  public static void main(String[] args) {

  Stackpracticearray s = new Stackpracticearray(6);

  s.push(1);

  s.push(2);

  s.push(3);

  s.push(4);

  s.push(5);

  s.push(6);

  //s.push(7);

  s.pop();

  s.pop();

  s.see();

  s.peek(); // -1 을 위해서 안해주니깐 다음인덱스가 나왔다 

  //System.out.println(s.stack[3]);

  /*int a=s.search(3);

  System.out.println(3);*/

  //System.out.println(s.peek());

}

}

※ 주의

수도코드에서는 스택의 최근 데이터 위치를 가르키는 top 이 0 인경우 데이터가 없다는 것으로 간주 합니다.

하지만 실제 소스코드 작성시 배열을 사용한다면 배열의 시작은 0 이기 때문에

top 을 -1 로 초기화 해야 합므로 주의 하세요!

http://globalbiz.tistory.com/78

package Datastructure;

public class Linkpractice {

Node head;

Node tail;

int size=0;

public class Node{

Node next;

Object data;

public Node(Object data){

this.next=null;

this.data=data;

}

}

public void addfirst(Object data){

if(head==null){

this.head= new Node(data);

size++;

}

else{

Node n = new Node(data);

n.next=this.head;

if(this.head.next==null){

this.tail=this.head;

}

this.head=n;

size++;

}

}

public void see(){

while(head.next !=null){

Object c =head.data;

System.out.println(c);

head=head.next;

}

System.out.println(tail.data);

}

public void addlast(Object data){

if(this.tail==null){

Node n=new Node(data);

this.head=n;

this.tail=n;

size++;

}

else{

Node n1=new Node(data);

this.tail.next=n1;

this.tail=n1;

size++;

}

}

public Node searchnode(int index){

Node s = this.head;

for(int i=0; i<index; i++){

s=s.next;

}

return s;

}

public void add(int index , Object data){

// 위치 0에 넣는다면 

if(index == 0){

addfirst(data);

}

else{// 위치 인덱스에 데이타를 넣겠다.

Node n= new Node(data);

Node pre=null;

pre=searchnode(index-1);

Node after=pre.next;

pre.next=n;

n.next=after;

size++;

//searchnode(index);

// n.next 뒤에 아무것도 안오는경우 

if(n.next==null){

this.tail=n;

}

}

}

// 처음 노드를 삭제 

public void removefirst(){

if(this.head==null){

return ;

}else{

Node tmp=null;

tmp=this.head;

this.head=null;

this.head=tmp.next;

size--;

}

}

// 중간 노드를 삭제 

public void remove (int index ){

if(index==0){

removefirst();

}

else{

Node tmp1=searchnode(index-1);

Node delnode=tmp1.next;

Node tmp2=searchnode(index+1); // 여기가 그냥 널로 들어가는군 delnode가 마지막이어도 

tmp1.next=tmp2;

if(delnode==this.tail){

//들어오고 

this.tail=tmp1;

}

delnode=null;

size--;

}

}

// 링크드리스트 사이즈 구하기 

public int linksize(){

return this.size ;

}

// 인덱스의 데이터 가져오기 

public Object getelement(int index){

Node tmp=searchnode(index);

return tmp.data;

}

public static void main(String[] args) {

Linkpractice p= new Linkpractice();

p.addfirst(1);

p.addfirst(2);

p.addfirst(3);

p.addlast(4);

p.add(4, 7);

p.remove(4); //짜놓은게 넣 포인트 날거 같았는데 실제로 나는줄 알았는데 

p.see();

}

}