달력

72025  이전 다음

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31


==디자인 패턴이란?==============================================================================

컴퓨터 과학 연구자들이 디자인 패턴이라는 것을 연구하기 시작한 주요 이유는 간단하 고 또한 재활용성이 있는 프로그래밍 솔루션을 만들기 위해서 이다.
디자인 패턴은 프로젝트사이 또는 프로그래머 사이에서 객체 지향 코드를 재사용하게 하는 편리한 수단일 뿐이다.
디자인 패턴은 프로그래머들이 유용하다고 생각하는객체들간의 일반적인 상호작용(interaction) 방법들을 모은 목록(Catalog)이라고 할 수 있다.

다른 말로 디자인 패턴은 어떻게 하면 객체들이 다른 객체의 메소드, 데이터들과 뒤엉힘이 없이 통신이 이루어질 수 있는 가를 기술한 것이다.

위와 같이 객체를 분리함으로써 객체지향 프로그래밍의 목적을 항상 유지할 수 있다.


?? 디자인 패턴은 자주 발생되는 설계상의 문제를 해결하기 위한 반복적인 솔루션이다. [Smalltalk Companion]

?? 디자인 패턴은 소프트웨어 개발 영역상에서 어떠한 작업을 수행하기 위한 코딩 원칙의 집합으로 구성되어 있다. [Pree, 1994]

?? 디자인 패턴은 반복되는 구조를 설계할 때 설계를 재활용하는데 초점을 두고있다. 그에 비해 프레임워크는 세부 설계와 구현에 초점을 두고 있다. [Coplien& Schmidr, 1995]

?? 패턴은 특정 디자인 상황에서 발생되는 반복되는 설계상의 문제를 다룬다. 또한 그것의 해결 방법을 제시한다.

?? 패턴은 단일의 클래스와 인스턴스 또는 컴포넌트 들의 레벨 상위의 추상성을정의한다.[Gamma et al, 1993]


디자인 패턴은 객체를 설계하기 위한 것만은 아니다. 디자인 패턴은 객체간의 상호작용을 표현하기 위해서도 쓰인다. 이러한 관점을 가지고 쓰여진 패턴을 Communication 패턴이라고 한다.

?? Creational pattern(생성 패턴) : 프로그래머가 직접 객체를 생성하는 것보다 패턴을 이용하여 객체를 생성한다. 이 패턴을 적용하면 주어진 상황에 어떠한 적절한 객체가 생성되야 적합한지를 프로그램상으로 유용하게 표현할 수 있다.

?? Structural pattern(구조 패턴) : 객체의 그룹들을 좀더 큰 구조로 조합할 때 어떻게 하는 것이 좋은 가에 대하여 기술한 패턴들이다. 예를 들면 사용자 인터페이스나 계산 데이터에 쓰인다.

?? Behavioral pattern(기능 패턴) : 시스템상의 객체들의 통신과 통신의 흐름이 복잡한 프로그램상에서 어떻게 컨트롤되는지 정의한다.

========================================================================================================================

 

'Design Patterns' 카테고리의 다른 글

스트래티지 패턴 2 (Head First 파헤치기 ver.1)  (0) 2009.11.12
스트래티지 패턴(Strategy Pattern)  (0) 2009.11.12
Observer Pattern  (0) 2009.11.11
Singleton Pattern -  (0) 2009.11.11
생성 패턴-Factory  (0) 2009.11.11
Posted by 인천총각
|

자료구조(해싱)

자료구조 2009. 11. 6. 15:21


◎ 해싱에대해서?

○ 해싱이란?

해시 함수를 이용하여 키 값을 위치로 변환하고 이를 이용해
저장된 자료를 바로 찾아가는 계산 검색 방식이다.
값의 연산에 의해 직접 접근이 가능한 구조를 해시테이블(hash table)
해시테이블을 이요한 탐색을 해싱(hashing)

 

○ 해싱구조..

레코드 키들의 집합을 버켓주소의 집합에 대응시킨다는 의미에서 사상함수라 한다.
가장 이상적인 해싱 함수는 키 집합의 한 레코드와 버켓 주소 집합의 한 레코드가
1 : 1 대응하여 해시 테이블의 정해진 범위에 고르게 분포되어 있는것을 뜻함.

-저장 및 검색 과정-

키 값 –> 해싱 함수 –> 해시 주소(버킷 주소) –> 해시 테이블

 

해싱 함수 구현부분-
----------------------------------------------------------------------------------------
public static int hash(Object key) // hashing method >> private
{   
  int sum = 0;
  byte compare[] = null;
     compare=((String)key).getBytes(); // 문자열을 바이트로 환산해주는 메서드 >> 리턴값 : 배열
   
  for(int i=0;i<((String)key).length();i++)
  {
  sum+=(int)compare[i];
  }
    
  int h=(sum & 0x7FFFFFFF) % capacity;
  return h;
 }
------------------------------------------------------------------------------------------


○ 해시 테이블

해상함수로부터 계산된 함수값에 해당하는 위치에 각 레코드를 한 개 이상 보관할 수 있는
버켓들로 구성된 기억 공간이며, 주어진 key값을 가지고 해당 레코드를 빠르게 검색하기 위한
수단을 제공하며 레코드의 삽입과 삭제를 용이하게 한다.

해시 테이블은 크기가 파일보다 커야한다. n개의 레코드에 대해 n개의 해쉬 주소를 생성
하는 해쉬 함수를 찾는것은 불가능 하기 때문.
일반적으로 부하율(load factor) 75%이상이면 일정의 테이블 공간을 늘려주는 것이 좋다.
그이상의 급격하게 성능 저하가 발생!!

 

○ 버켓

일종의 자료구조로 해싱함수에 의해 계산된 주소인 홈 주소에 레코드를 저장하기 위해 마련된 기억공간.

 

○ 해싱함수란?

탐색 키를 간단화하는 함수를 해싱 함수(hashing function) 라 하며,
탐색 키를 받아서 해시 주소를 생성하는 기능을 한다.
이 해시 주소가 바로 간단화된 탐색 키라고 할 수 있고. 자리수가 몇 안 되는 정수이고 곧 배열의 번호이다.


※ 좋은 해시 함수 조건
- 주소 계산이 빠르게 구해져야 한다.
- 서로 다른 레코드의 계산된 값이 가급적 중복되지 안하야 한다(충돌이 적어야한다)

○ 해싱함수의 종류

-제산법(Division) : 나머지 연산자(%)를 사용하여 테이블 주소를 계산하는 방법!!
                    * 버켓주소 = 키 값 % 해쉬테이블 크기


-제곱법(Mid-Saure) : 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 있는 몇 비트를
                     선택하여 해시 테이블의 홈 주소로 사용, 심볼 테이블 응용에서 자주 사용
                    * k = 35270 제곱시 테이블의 크기가 10,000일때(중간 4비트선택)
         11243972900 -> 1243ㅣ9729ㅣ00 -> 9729가 주소값


-숫자 분석법(Digit-Analysis) : 레코드 모든키들 내에서 각 자리별로 어떤 분포인지 조사하여
          비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여 사용
                               * 정적 파일에 유효, In/out 빈번히 발생할경우 비효율적

 

-폴딩법(Folding) : 레코드 키의 마지막 부분을 제외한 모든 길이가 동일하게 여러부분으로 나누고
                   이를 모두 더하거나 배타적 노리합을 취하여 홈주소로 이용하는 방법

  탐색키 : 123ㅣ203ㅣ241ㅣ112ㅣ20
                  
  *이동폴딩 : 각부분의 값을 계산하기 위해 마지막을 제외한 모든 부분을 이동시
        최하위 비트가 마지막 부분의 자리와 일치하도록 우측끝을 맞추어 더한 값

        123+203+241+112+20 =699      


  *경계폴딩 : 나누어진 각 부분의 경계선을 종이 접듯이 접어 역으로 정렿한 다음 더한 값

        123+302+241+211+20=897

                    
- 기수변환법 , 무작위 방법 등이 있음

 


○ OverFlow 해결

- 선형조사법,이차조사법,이중해싱법,체이닝 의 방법 사용 (선형법과 체이닝 많이사용)

* 선형 조삽법(선형 개방 주소법) : 충돌이 일어난 키값을 다른 비어있는 버킷을 찾아 저장한다.
       이 때 비어있는 버킷은 순차적으로 찾는다

 

* 체이닝(Chaining) : 오버플로우 문제를 연결 리스트로 해결
        각 버켓에 고정된 슬롯을 할당하는 것이 아니라 각 버켓에, 삽입과 삭제가
        용이한 연결리스트를 할당
        버켓내에서는 원하는 항목을 찾을때는 연결리스트를 순차 탐색!

 


○ 동적 해싱법

 해시 테이블 대신에 트라이라는 자료구조 사용
 트라이 : 입력키의 각 비트값에 따라 2개의 가지로 분리되도록 만들어진 것
 
 키 값의 맨 오른쪽 비트부터 검사 하여 0일경우 첫번째 레벨의 위쪽 1일경우 아래쪽 으로 분기
 끝에서 두번째 비트를 검사하여 그값이 0이면 두번째 레벨의 위쪽 1이면 아래쪽으로 분기
 ......순차적으로 오른쪽에서 왼쪽으로 키값을 비교해 나가면서 분기한다.,

------------------------------------------------------------------------------------------------------------------------

구현

----Entry Class---------------------------------------------------------------------------------------------------------

public class Entry
{
 public Object key, value; //key,value 필드 분리
 public Entry next;  // Node 개념 적용 - 자기 참조

 public Entry(Object key, Object value) {
      this.key = key;
      this.value = value;
    }

 public Object getKey() {  //key 리턴
      return key;
    }
   
 public Object getValue() {  //value 리턴
       return value;
    }

 public void setValue(Object value) { //value 설정
      this.value = value;
    }
}


----HashTable Class----------------------------------------------------------------------------------------------------

public class HashTable
{
   private static final int CAPACITY = 10;  //기본테이블 크기
   private static int capacity;
   public Entry[] hTable;  // 해쉬테이블은 배열로 구성되어 있고 각각의 배열에는 엔트리가 들어감 

   public HashTable(int capacity) // 파라미터가 테이블 용량을 넘겨줄경우 생성자
   { 
     this.capacity = capacity;
     hTable = new Entry[capacity];  // 테이블 크기만큼 엔트리 생성 해서 해쉬 테이블 생성
   }

   public HashTable() // 파라미터가 없을경우
   {   
     this(CAPACITY);  // 기본값 크기로
   }

   public static int hash(Object key) // hashing method >> private
   {   
     int sum = 0;
     byte compare[] = null;
     compare=((String)key).getBytes(); // 문자열을 바이트로 환산해주는 메서드 >> 리턴값 : 배열
    
     for(int i=0;i<((String)key).length();i++)
     {
      sum+=(int)compare[i];
     }
    
     int h=(sum & 0x7FFFFFFF) % capacity;
     return h;
  }

  
   public void put(Object key, Object value) // 넣기
   { 
     int h = hash((String)key);   // key 값으로 해싱
     Entry cur = hTable[h];  // 해싱값에 해당하는 배열칸값
     Entry entry = new Entry(key, value); // 엔트리 형성
    
     if (hTable[h] == null) //
      { 
       hTable[h] = entry;    // 입력된 값 저장
      }
     else {  // 해시값 충돌시
         while (cur.next != null)// 노드 끝까지
          {      
            if(cur.getKey().equals(key)) // 혹시나 키값이 같은 자료 입력을 시도랬다면
            {  
            cur.setValue(value);   // 해당엔트리의 자료값만 변경
            break;  // 그다음 끝냄
            }
           cur = cur.next;    // 리스트가 끝날때까지 next 로 찾아감
          }
         cur.next = entry;   // 리스트의 끝에 입력된 엔트리 달기
        }
   }
   


  public void searchMap(Object word) // 검색 메서드
  {  
   int flag = 0; // 결과 상태
   Object result = null; // 결과값
   Entry cur = hTable[hash(word)];
  
   if (cur == null)
    flag = 0;
   else
   {
    while(cur != null)
    {
     if (cur.getKey().toString().equals((String)word))
      {
      flag = 1;
      result = cur.getValue(); break;
      }
     else
      cur = cur.next;
    }
   }
  
   //검색결과 출력
   if (flag == 0 ) System.out.println("검색결과가 없습니다.");
   else System.out.println("검색결과가 있으며 값은 " + (String)result + " 입니다.");
  }
 
 

   public void printMap() // 출력
   { 
     Entry cur;                   // 출력할 엔트리를 '포인팅' 하기 위해 정의한 변수
     for(int i=0; i<capacity; i++) // 테이블 크기 수 만큼
     { 
       System.out.print("|"+i+"|\t"); 
       cur = hTable[i];     // i번 배열에 있는 엔트리를 받아오기
      
       if((cur == null))        // 비어있을경우
        System.out.print("null");  // null 출력
       else
       { 
         while(cur != null)
         {      // 엔트리 끝이 더이상 없을 때까지
           System.out.print("Key : "+ cur.getKey() +"  Value : "+ cur.getValue()+"  ");  // 현재 엔트리의 키값과 자료값을 불러와 출력
           cur = cur.next;        // 다음번 엔트리로 넘어가기
         }
       }
       System.out.println("");   // 줄바꾸기 
     }      
   }
  
  
 }

----Testinput Class-----------------------------------------------------------------------------------------------------

public class Testinput
{

 public static void clearScreen() // 화면 초기화
 {
      for (int i = 0; i < 80; i++)
        System.out.println("");
 }
 
 
 public static void main(String[] args) throws IOException
 {
     HashTable map2 = new HashTable();
  int msel;
        String con;  // 계속 여부
        do
        {
          //clearScreen();
    System.out.println("메뉴를 선택하세요");
    System.out.println("1. 입력");
    System.out.println("2. 출력");
    System.out.println("3. 검색");
    System.out.println("4. 종료");
    
    BufferedReader ar = new BufferedReader(new InputStreamReader(System.in));
    msel =Integer.parseInt(ar.readLine());
    
    switch (msel)
    {
     case 1: // 입력
     {
      System.out.println("key : ");
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      String b=br.readLine().toString();
      System.out.println("value : ");
      BufferedReader cr = new BufferedReader(new InputStreamReader(System.in));
      String c=cr.readLine().toString();
      map2.put(b,c);
      break;
     }
     case 2: // 출력
     {
      map2.printMap();
      break;
     }
     case 3: // 검색
     {
      System.out.println("search : ");
      BufferedReader dr = new BufferedReader(new InputStreamReader(System.in));

      String d=dr.readLine().toString();
      map2.searchMap(d);
      break;
     }
     case 4: // 종료
     {
      return;
     }
    }     
  
  } while (true);
  
  
  
 }

}

----TestChaining Class--------------------------------------------------------------------------------------------------

public static void main(String[] args)
{
     HashTable map1 = new HashTable();  // 첫번째 맵 형성
     map1.put("태희","011-234-5348");  // 자료입력
     map1.put("미","011-214-7678");
     map1.put("동훈","015-434-8378");
     map1.put("종훈","011-2674-5878");
     map1.put("Hut","016-214-2678");
     map1.put("Ohr","013-134-1678");
     System.out.println("map1 is  ");
     map1.printMap();  // 자료출력
    
     map1.searchMap("Ohr");
     map1.searchMap("종훈");
    


     //System.out.println(map1.hash("Tor"));
     //System.out.println(map1.hash("Rad"));
    
    
    

     HashTable map55 = new HashTable();
     map55.put("a","1234");
     map55.put("b","3456");
     map55.put("c","9874");
     map55.put("d","5478");
     map55.searchMap("c");
    
    
   }
 }


------------------------------------------------------------------------------------------------------------------------LRU 기법? 주기억장치에 저장된 시점과 관계없이, 사용률이 가장 저조한 페이지를 교체하는것!

'자료구조' 카테고리의 다른 글

자료구조(Stack 과 Queue)  (0) 2009.11.06
자료구조 ( Array와 Linked List)-  (0) 2009.11.06
Posted by 인천총각
|

◆◆ Stack 과 Queue


◆ 1. Stack

  ㉠ 정의

      여러 개의 데이타 항목들이 일정한 순서로 나열된 자료 구조로, 한쪽 끝에서만 새로운 항목을 삽입하거나 기존 항목을 삭제할 수
      있는 선형 구조.


  ㉡ 특징

      Last- In-First-Out List (후입 선출) : 먼저 삽입된 것은 나중에 삭제되고, 나중에 삽입된 것이 먼저 삭제.

      push : Data 를 넣는 것.

      pop : 넣어둔 Data 를 꺼내는 것.

      top : Data 를 저장하는 위치


  ㉢ 연산

       S를 스택, x를 데이터 요소(element)라고 하자. 그러면 스택에서는 아래와 같은 중요한 연산이 존재하는 것을 알 수 있다.

       S.top(): 스택의 가장 윗 데이터를 넘겨준다.만약에 비었다면 이 연산은 정의불가 상태다.

       S.pop(): 스택의 가장 윗 데이터를 지우고 그 값을 넘겨준다.스택이 비었다면 연산 정의불가 상태.

       S.push(): 스택의 가장 윗 데이터로 x를 넣는다.

       S.empty(): 스택이 비었다면 참을 주고,그렇지 않다면 거짓이 된다.

       또한, 스택연산을 목록(list) 연산으로 표현할 수도 있다.

       S.top(): S.retrieve(S.first())

       S.pop(): S.top(),S.delete(S.first())

       S.push():S.insert(x,pNull)

       S.empty():S.first()==pNull

 

◆ 2. Queue

  ㉠ 정의

      여러 개의 데이타 항목들이 일정한 순서로 나열된 자료 구조로 한쪽 끝에서는 삽입만 할 수 있고, 삭제는 반대쪽 끝에서만 할 수 있
      도록 되어 있는 선형 구조.


  ㉡ 특징

       First In First Out (선입선출) : 큐에 저장된 데이터 항목들 중에 먼저 삽입된 것은 먼저 삭제되고, 나중에 삽입된 것은 나중에 삭제.

       put : Data 를 넣는 것.

       get : Data 를 꺼내는 것.

       front(head) : Data 를 put 할 수 있는 위치.

       rear(tail) : Data 가 있어 get 할 수 있는 위치.

       Overflow : Queue 가 꽉 차서 더 이상 Data 를 넣을 수 없는 경우 (put 할 수 없는 경우)

       Underflow : Queue 가 비어 있어 Data 를 꺼낼 수 없는 경우 (get 할 수 없는 경우)


  ㉢ 종류

       가. 선형 Queue : 막대 모양으로 된 Queue 이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 Data 를 꺼내거나 Data 를 한
                               칸씩 옮겨야 한다는 단점이 있다.

       나. 환형 Queue  : 선형 Queue 의 문제점을 보완한 것이 환형 Queue 이다. front가 Queue 의 끝에 닿으면 Queue 의 맨 앞으로 Data 를 보내어 원형으로 연결 하는 방식.

       다. Linked Queue  : Linkedlist 를 사용한 것으로써, Queue  의 길이를 쉽게 늘릴 수 있어 Overflow 가 발생하지 않는다.

                                  필요에 따라 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리하다.

 

◆◆ 3. Simulation (Java)


1. node 클레스 설계
------------------------------------------------------------------------------------------------------------------
public class Node {
 
 public Node(int v){
  value = v;
 }
 
 public int value;
 public Node next;   // 자기 참조!!
}
------------------------------------------------------------------------------------------------------------------

 

2. LinkedList 클레스 설계
------------------------------------------------------------------------------------------------------------------
public class LinkedList {
 Node header;

 public LinkedList(Node h) {
  header = h;
 }

 public void append(Node node) {
  Node last = header;
  while (last.next != null) {
   last = last.next;
  }
  last.next = node;
 }
 
 public Node getHeader(){
  return header;
 }

 public void remove_back() //링크드 리스트에 뒤에 있는걸 삭제
 {
  Node last = header;

  if (last.next == null)  // elements 가 하나만 있는 상황이므로 끊을필요 없다
  {
  }
  else
  {
   while (last.next.next != null) { // 두번째 연결된 elements 의 next 값이 없을때 까지 루프
    last = last.next;
   }
   last.next = null; //  마지막 에 연결된 elements 의 next 를 null 값을 넣어 끊기
  }
 }
 
 public void remove_front() //링크드 리스트에 앞에 있는걸 삭제
 {
  header = header.next; // 헤더 를 다음 값으로 바꾸기
  
 }
  
}
------------------------------------------------------------------------------------------------------------------

 

3. Array 로 Stack 구현
------------------------------------------------------------------------------------------------------------------
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class IntStack_A {
 
    private int[] data;

    private int top;   // stack 맨위

    private int many_items; // 현재 Stack 에 몇 개의 원소가 있는지를 저장해 놓은 변수

    private int stack_size; // Stack 의 전체 크기
   
    private BufferedReader br ;

public IntStack_A(int size) // size : 스텍의 크기
    {
        data = new int[size];

        stack_size = size;      

        top = -1; // stack 이 비어 있을 때

        many_items = 0;

     System.out.println("값을 입력하세요 :");
     try {
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));

   printf1();   
   System.out.println("");
   System.out.println("1.삭제(POP)  2.삽입(PUSH)");
   br = new BufferedReader(new InputStreamReader(System.in));
   String sd=br.readLine();
   if (sd.equals("1"))
   {
   pop();
   printf1();
   }
   
   else if (sd.equals("2"))
   {
   push(99);
   printf1();
   } 
   
  } catch (NumberFormatException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  } catch (IOException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
       
    }
   
   
    public void push(int number) // push()는 Stack 의 맨 위에 쌓아놓을 수 있다  >> data 배열에 숫자를 넣음
    {
        data[++top] = number; //++top 연산을 통해서 top 은 push 함수를 호출할 때마다 하나씩 위로 올라가서 Stack 의 맨 위를 언제나 가리키게 됨
                                         // 배열 이므로 제일 나중에 집어넣은 원소의 Index 를 보유

        many_items++; // Stack 에 저장된 원소의 갯수 1 증가
    }

   
    public int pop() // 맨 위에서만 빼낼 수 있다
 {
  many_items--; // Stack 에 저장된 원소의 갯수 1 감소
  return data[top--]; // 배열에서 맨위의 값을 반환하고 인덱스 를 1 감소시킴
 }
   
   

    public void printf1() // 배열 출력
    {
     for(int i=0;i<many_items;i++){
     System.out.print(data[i]+",");
  }
    }

     public static void main(String[] args)
     {
 new IntStack_A(5);
      }
}

------------------------------------------------------------------------------------------------------------------

 

4. Array 로 Queue 구현
------------------------------------------------------------------------------------------------------------------
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class IntQueue_A {
 
    private int[] data;

    private int rear;   // Queue 맨위

    private int many_items; // 현재 Queue 에 몇 개의 원소가 있는지를 저장해 놓은 변수

    private int Queue_size; // Queue 의 전체 크기
   
    private BufferedReader br ;

public IntQueue_A(int size) // size : Queue 크기
    {
        data = new int[size];

        Queue_size = size;      

        rear = -1; // Queue 가 비어 있을 때

        many_items = 0;

     System.out.println("값을 입력하세요 :");
     try {
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));

   printf1();   
   System.out.println("");
   System.out.println("1.삭제(POP)  2.삽입(PUSH)");
   br = new BufferedReader(new InputStreamReader(System.in));
   String sd=br.readLine();
   if (sd.equals("1"))
   {
   pop();
   printf1();
   }
   
   else if (sd.equals("2"))
   {
   push(99);
   printf1();
   }  
   
  } catch (NumberFormatException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  } catch (IOException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }       
    }
       
    public void push(int number) //  data 배열에 숫자를 넣음
    {
        data[++rear] = number; //

        many_items++; // Queue 에 저장된 원소의 갯수 1 증가
    }
   
    public void pop() // 맨 위에서만 빼낼 수 있다
 {

  for (int i=0;i<many_items;i++)
  {
   data[i] = data[i+1];
  }

  many_items--; // Queue 에 저장된 원소의 갯수 1 감소
 }

    public void printf1() // 배열 출력
    {
     for(int i=0;i<many_items;i++){
     System.out.print(data[i]+",");
  }
    }

 public static void main(String[] args) {
  new IntQueue_A(5);
 }
}
------------------------------------------------------------------------------------------------------------------

 

5. LinkedList 로 Stack 구현
------------------------------------------------------------------------------------------------------------------
public class LinkedListStack {
 public static void main(String[] args) {
  LinkedList list = new LinkedList(new Node(50));
  list.append(new Node(20));
  list.append(new Node(30));
  print(list.getHeader());
  list.remove_back();
  print(list.getHeader());
  list.append(new Node(10));
  print(list.getHeader());
  list.append(new Node(60));
  print(list.getHeader());
  list.remove_back();
  print(list.getHeader());
  list.remove_back();
 }

 private static void print(Node header) {
  Node list = header;
  while (list != null) {
   System.out.print(list.value + " -> ");
   list = list.next;
  }
  System.out.println();
 }
}
------------------------------------------------------------------------------------------------------------------

 

6. LinkedList 로 Queue 구현
------------------------------------------------------------------------------------------------------------------
public class LinkedListQueue {
 public static void main(String[] args) {
  LinkedList list = new LinkedList(new Node(50));
  list.append(new Node(20));
  list.append(new Node(30));
  print(list.getHeader());
  list.append(new Node(10));
  print(list.getHeader());
  list.append(new Node(60));
  print(list.getHeader());
  list.remove_front();
  print(list.getHeader());
 }

 private static void print(Node header) {
  Node list = header;
  while (list != null) {
   System.out.print(list.value + " -> ");
   list = list.next;
  }
  System.out.println();
 }
}

'자료구조' 카테고리의 다른 글

자료구조(해싱)  (0) 2009.11.06
자료구조 ( Array와 Linked List)-  (0) 2009.11.06
Posted by 인천총각
|