IntStack 클래스

스택이란?

• 동일한 자료형의 집합을 의미
• 스택은 맨 위에 데이터를 추가하고 제거 가능한 자료구조이다. (LIFO, last in first out)

코드 설명

/******************************************************************************/
// IntStack 클래스는 정수형 스택 구조를 제공합니다.
public class IntStack implements Cloneable
{
   // IntStack 클래스의 불변 조건:
   //   1. 스택에 들어 있는 항목의 수는 manyItems 변수에 저장됩니다.
   //   2. 스택이 비어 있으면 data 배열에 어떤 값이 들어 있는지는 중요하지 않습니다.
   //      스택이 비어 있지 않다면, data 배열에 항목이 저장되며,
   //      스택의 바닥은 data[0], 그 다음 항목은 data[1], ... 맨 위 항목은 data[manyItems-1]입니다.
   private int[ ] data;
   private int manyItems; 


   /**
   * 초기 용량이 10인 비어 있는 스택을 생성합니다.
   * @param 없음
   * @postcondition
   *   이 스택은 비어 있으며 초기 용량은 10입니다.
   * @exception OutOfMemoryError
   *   <CODE>new int[10]</CODE> 생성 시 메모리가 부족한 경우 발생합니다.
   **/   
   public IntStack( )
   {
      final int INITIAL_CAPACITY = 10;
      manyItems = 0;
      data = new int[INITIAL_CAPACITY];
   }

   
   /**
   * 지정된 초기 용량을 가진 비어 있는 스택을 생성합니다.
   * @param initialCapacity
   *   스택의 초기 용량
   * @precondition
   *   initialCapacity는 0 이상이어야 합니다.
   * @postcondition
   *   이 스택은 비어 있으며 주어진 용량을 가집니다.
   * @exception IllegalArgumentException
   *   initialCapacity가 음수일 경우 발생합니다.
   * @exception OutOfMemoryError
   *   <CODE>new int[initialCapacity]</CODE> 생성 시 메모리가 부족한 경우 발생합니다.
   **/   
   public IntStack(int initialCapacity)
   {
      if (initialCapacity < 0)
         throw new IllegalArgumentException("초기 용량이 너무 작습니다: " + initialCapacity);
      manyItems = 0;
      data = new int[initialCapacity];
   }

   
   /**
   * 이 스택의 복사본을 생성합니다.
   * @return
   *   이 스택의 복사본을 반환합니다. 원본과 복사본은 서로 영향을 주지 않습니다.
   * @exception OutOfMemoryError
   *   복사본 생성 중 메모리 부족 시 발생합니다.
   **/ 
   public Object clone( )       
   {
      IntStack answer;
      
      try
      {
         answer = (IntStack) super.clone( );
      }
      catch (CloneNotSupportedException e)
      {
         throw new RuntimeException("이 클래스는 Cloneable을 구현하지 않았습니다.");
     }
      
      answer.data = (int [ ]) data.clone( );
      return answer;
   }        
 

   /**
   * 이 스택의 현재 용량을 지정된 값 이상으로 늘립니다.
   * @param minimumCapacity
   *   최소 확보해야 하는 용량
   * @postcondition
   *   이 스택의 용량은 최소한 minimumCapacity 이상이 됩니다.
   * @exception OutOfMemoryError
   *   용량을 늘리기 위한 메모리 부족 시 발생합니다.
   **/
   public void ensureCapacity(int minimumCapacity)
   {
      int biggerArray[ ];
      
      if (data.length < minimumCapacity)
      {
         biggerArray = new int[minimumCapacity];
         System.arraycopy(data, 0, biggerArray, 0, manyItems);
         data = biggerArray;
      }
   }


   /**
   * 이 스택의 현재 용량을 반환합니다.
   * @return
   *   스택의 현재 용량
   **/
   public int getCapacity( )   
   {
      return data.length;
   }

   
   /**
   * 이 스택이 비어 있는지 확인합니다.
   * @return
   *   스택이 비어 있으면 true, 아니면 false
   **/
   public boolean isEmpty( )
   {
      return (manyItems == 0);
   }
   

   /**
   * 스택의 맨 위 항목을 제거하지 않고 확인합니다.
   * @precondition
   *   스택이 비어 있지 않아야 합니다.
   * @return
   *   스택의 맨 위 항목
   * @exception EmptyStackException
   *   스택이 비어 있을 경우 발생합니다.
   **/   
   public int peek( )   
   {
      if (manyItems == 0)
         throw new EmptyStackException( );
      return data[manyItems-1];
   }

   
   /**
   * 스택의 맨 위 항목을 꺼내어 제거합니다.
   * @precondition
   *   스택이 비어 있지 않아야 합니다.
   * @postcondition
   *   맨 위 항목이 제거되며 반환됩니다.
   * @exception EmptyStackException
   *   스택이 비어 있을 경우 발생합니다.
   **/    
   public int pop( )
   {
      if (manyItems == 0)
         throw new EmptyStackException( );
      return data[--manyItems];
   }
   
 
   /**
   * 새 항목을 스택에 추가합니다.
   * 용량을 초과하면 자동으로 용량이 늘어납니다.
   * @param item
   *   추가할 항목
   * @postcondition
   *   항목이 스택에 추가됩니다.
   * @exception OutOfMemoryError
   *   용량 증가를 위한 메모리 부족 시 발생합니다.
   * @note
   *   용량이 Integer.MAX_VALUE를 초과하면 스택이 실패할 수 있습니다.
   **/    
   public void push(int item)
   {
      if (manyItems == data.length)
         ensureCapacity(manyItems*2 + 1);
      data[manyItems++] = item;
   }
              

   /**
   * 이 스택에 들어 있는 항목 수를 반환합니다.
   * @return
   *   항목 수
   **/ 
   public int size( )   
   {
      return manyItems;
   }


   /**
   * 이 스택의 용량을 현재 크기만큼으로 줄입니다.
   * @postcondition
   *   스택의 용량이 현재 항목 수에 맞게 조정됩니다.
   * @exception OutOfMemoryError
   *   용량 변경을 위한 메모리 부족 시 발생합니다.
   **/   
   public void trimToSize( )
   {
      int trimmedArray[ ];
      
      if (data.length != manyItems)
      {
         trimmedArray = new int[manyItems];
         System.arraycopy(data, 0, trimmedArray, 0, manyItems);
         data = trimmedArray;
      }
   } 
}

• LIFO의 구조를 나타낸 Int형의 stack구조이다.

필드 변수

private int[] data;
private int manyItems;

• data에는 int자료형의 데이터를 저장해 준다.
• manyItems는 데이터의 개수를 저장해 준다.

생성자

public IntStack() {
   final int INITIAL_CAPACITY = 10;
   manyItems = 0;
   data = new int[INITIAL_CAPACITY];
}

• 기본 생성자는 초기 용량을 10으로 고정하여서 비어있는 스택을 생성한다.
• data 배열을 new int [10]으로 선언해 준다.

public IntStack(int initialCapacity)

• 이번 생성자는 초기 용량을 initialCapacity로 선언해 준다.
• 음수 용량을 받은 경우에는 IllegalArgumentException을 발생시킨다.

메서드

public Object clone( )       
   {
      IntStack answer;
      
      try
      {
         answer = (IntStack) super.clone( );
      }
      catch (CloneNotSupportedException e)
      {
         throw new RuntimeException("이 클래스는 Cloneable을 구현하지 않았습니다.");
     }
      
      answer.data = (int [ ]) data.clone( );
      return answer;
   }

• answer에 super.clone() 활용하여서 얕은 복사를 해준다.
• 그런 다음 (int [ ])data.clone()으로 깊은 복사를 진행해 준다.

public void trimToSize( )
   {
      int trimmedArray[ ];
      
      if (data.length != manyItems)
      {
         trimmedArray = new int[manyItems];
         System.arraycopy(data, 0, trimmedArray, 0, manyItems);
         data = trimmedArray;
      }
   }

• 배열의 용량을 데이터의 개수에 맞춰서 줄여주는 메서드.
• arraycopy를 활용하여서 용량에 알맞게 저장해 준다.

 public int getCapacity( )   
   {
      return data.length;
   }

• 배열의 크기를 return 해준다. (data.length)

public boolean isEmpty( )
   {
      return (manyItems == 0);
   }

• 데이터의 개수가 0이라면 true, 아니라면 false를 리턴해준다.

 public int size( )   
   {
      return manyItems;
   }

• 데이터의 개수를 리턴해준다. (manyItems)

 public void push(int item)
   {
      if (manyItems == data.length)
         ensureCapacity(manyItems*2 + 1);
      data[manyItems++] = item;
   }

• 만약 현제 데이터의 개수가 데이터의 용량과 동일하여서 데이터를 넣을 수 없다면 현제 데이터 개수의 2배만큼 용량을 늘려준다.
• manyItems의 위치에 item을 저장해 주고 manyItems를 1 증가시켜준다.

  public int pop( )
   {
      if (manyItems == 0)
         throw new EmptyStackException( );
      return data[--manyItems];
   }

• 만약 데이터의 개수가 0이라면 EmptyStackException을 발생시킨다.
• --manyItems위치의 데이터를 리턴해준다.

public void ensureCapacity(int minimumCapacity)
   {
      int biggerArray[ ];
      
      if (data.length < minimumCapacity)
      {
         biggerArray = new int[minimumCapacity];
         System.arraycopy(data, 0, biggerArray, 0, manyItems);
         data = biggerArray;
      }
   }

• 만약 minmumCapacity가 data의 용량보다 작은 경우에 배열의 용량을 늘려준다.
• arraycopy를 활용하여서 데이터의 용량을 늘려준다.