[Java] - 자바로 Stack 구현하기

 

 

 

Stack이란?

https://ttl-blog.tistory.com/628

[자료구조] - 스택(Stack)

 

 

 

 

 

 

 

 

 

Stack 인터페이스

우선 Stack의 인터페이스를 다음과 같이 정의하겠습니다.

public interface Stack<E> {

   /**
    * 스택이 비어있는지 확인합니다
    */
   boolean isEmpty();

   /**
    * 스택이 가득 찼는지 확인합니다
    */
   boolean isFull();

   /**
    * 스택에 저장된 현재 원소의 수를 반환합니다.
    */
   int size();


   /**
    * push를 수행합니다.
    * 스택에 요소를 삽입합니다.
    */
   boolean push(E item);

   /**
    * pop을 수행합니다.
    * 스택에 가장 마지막에 들어간 원소를 스택에서 제거한 뒤 반환합니다.
    * 원소가 없다면 null을 반환합니다.
    */
   E pop();

   /**
    * peek를 수행합니다.
    * 스택에 가장 마지막에 들어간 원소를 스택에서 제거하지 않고 반환합니다.
    * 원소가 없다면 null을 반환합니다.
    */
   E peek();

   /**
    * 스택을 비웁니다.
    */
   void clear();

}

 

 

 

 

 

 

 

 

 

 

Stack 전체 구현 코드

import java.util.Arrays;

public class ArrayStack<E> implements Stack<E>{


   private static final int DEFAULT_CAPACITY = 50;

   private int capacity;           // 현재 스택의 용량
   private int size;              // 스택에 들어온 원소의 개수, (top 원소의 배열에서의 인덱스 = size - 1)
   private E[] elements;           // 원소를 저장하는 배열


   //== Constructor ==//
   public ArrayStack() {
      this(DEFAULT_CAPACITY);
   }


   @SuppressWarnings("unchecked")
   public ArrayStack(int capacity) {
      setCapacity(capacity);
      setElements( (E[]) new Object[capacity]);
      setSize(0);
   }






   //== Getter / Setter ==//
   private int capacity() {
      return capacity;
   }

   private void setCapacity(int capacity) {
      this.capacity = capacity;
   }

   private void setSize(int size) {
      this.size = size;
   }

   private E[] elements() {
      return this.elements;
   }

   private void setElements(E[] elements) {
      this.elements = elements;
   }
   //== [Finish] - Getter / Setter ==//







   @Override
   public boolean isEmpty() {
      return (size() <= 0);
   }

   @Override
   public boolean isFull() {
      return (size() == capacity());
   }

   @Override
   public int size() {
      return this.size;
   }



   @Override
   public boolean push(E item) {
      if (isFull()) {grow();}

      this.elements[size++] = item;
      return true;
   }

   @Override
   public E pop() {
      if (isEmpty()) {return null;}

      E remove = this.elements[size - 1];//pop 할 원소는 (size -1)
      this.elements[--size] = null;
      return remove;
   }


   @Override
   public E peek() {
      if (isEmpty()) {return null;}
      return this.elements[size-1];
   }


   @Override
   @SuppressWarnings("unchecked")
   public void clear() {
      setElements( (E[]) new Object[this.capacity()]);
      setSize(0);
   }


   /**
    * 배열의 크기를 2배로 늘려준다.
    */
   @SuppressWarnings("unchecked")
   private void grow() {
      setCapacity( capacity() * 2 );
      setElements( Arrays.copyOf( elements(), capacity()) );
   }



}

 

 

 

 

 

 

 

 

 

 

 

세부 구현

 

ArrayStack<E>의 필드

public class ArrayStack<E> implements Stack<E>{

	private static final int DEFAULT_CAPACITY = 50;
	
	private int capacity; 				// 현재 스택의 용량 
	private int size; 					// 스택에 들어온 원소의 개수, (top 원소의 배열에서의 인덱스 = size - 1)
	private E[] elements;				// 원소를 저장하는 배열

 

설명

• DEFAULT_CAPACITY : Stack의 기본 용량입니다. 이는 다 차면 grow 메서드를 통하여 용량을 2배 증가시켜줍니다.
• capacity : Stack의 현재 용량입니다.
• size : Stack에 삽입된 원소의 개수입니다.
• elements : 원소를 저장하는 배열입니다. 이를 통해 Stack이 배열로 구현되었다는 것을 알 수 있습니다.

 

 

 

 

 

 

 

 

ArrayStack<E>의 생성자

//== Constructor ==//
public ArrayStack() {
   this(DEFAULT_CAPACITY);
}


@SuppressWarnings("unchecked")
public ArrayStack(int capacity) {
   setCapacity(capacity);
   setElements( (E[]) new Object[capacity]);
   setSize(0);
}

 

설명

• ArrayStack(int capacity) : 초기 용량을 주입받아 Stack을 생성하는 생성자입니다.
• ArrayStack() : 초기 용량을 지정하지 않은 생성자로, DEFAULT_CAPACITY를 사용합니다. 이미 구현한 다른 생성자를 사용하여 생성합니다.
•  @SuppressWarnings("unchecked") : 

 

 

 

 

 

 

 

 

내부적으로 사용할 Getter, Setter

//== Getter / Setter ==//
private int capacity() {
   return capacity;
}

private void setCapacity(int capacity) {
   this.capacity = capacity;
}

private void setSize(int size) {
   this.size = size;
}

private E[] elements() {
   return this.elements;
}

private void setElements(E[] elements) {
   this.elements = elements;
}

 

 

 

 

 

 

 

 

 

 

ArrayStack<E>의 내부 상태 확인하기

@Override
public boolean isEmpty() {
   return (size() <= 0);
}

@Override
public boolean isFull() {
   return (size() == capacity());
}

@Override
public int size() {
   return this.size;
}

설명

• isEmpty() : 스택이 비어있는지 확인합니다. size가 0이면 스택이 비어있는 상태이므로 사실 size() == 0으로 해주어도 상관없습니다.
• isFull() : 스택의 용량이 가득 찼는지 확인합니다. 가득 찼다면 grow 메서드를 사용해서 용량을 2배 늘려줍니다.
• size() : 현재 저장된 원소의 개수를 반환합니다.

 

 

 

 

 

 

 

 

 

ArrayStack<E>의 배열 크기 증가시키기

/**
 * 배열의 크기를 2배로 늘려준다.
 */
@SuppressWarnings("unchecked")
private void grow() {
   setCapacity( capacity() * 2 );
   setElements( Arrays.copyOf( elements(), capacity()) );
}

 

 

설명

• 현재 스택의 용량을, 기존 용량의 2배로 지정합니다.
• Arrays.copyOf 메서드를 사용하여, 기존 원소를 저장하던 배열을, 2배로 늘린 용량만큼의 새로운 길이를 갖는 배열에 복사 후, 이를 스택의 배열로 다시 Set 합니다.

 

 

 

 

 

 

 

 

 

ArrayStack<E> 초기화하기

@Override
@SuppressWarnings("unchecked")
public void clear() {
   setElements( (E[]) new Object[this.capacity()]);
   setSize(0);
}

 

 

설명

• Setter를 통해 기존의 배열을 비어있는 새로운 배열로 대체합니다. 기존의 배열은 참조를 잃어 GC(Garbage Collectior)에 의해 수거됩니다.

 

 

 

 

 

 

 

 

 

ArrayStack<E>의 삽입과 삭제

@Override
public boolean push(E item) {
   if (isFull()) {grow();}

   this.elements[size++] = item;
   return true;
}

@Override
public E pop() {
   if (isEmpty()) {return null;}

   E remove = this.elements[size - 1];//pop 할 원소는 (size -1)
   this.elements[--size] = null;
   return remove;
}


@Override
public E peek() {
   if (isEmpty()) {return null;}
   return this.elements[size-1];
}

 

 

설명

• push(E item) : 스택에 원소를 추가합니다.
  • 추가 전에 스택이 가득 찼는지 확인 후, 가득 찼다면 grow()를 통해 용량을 늘려줍니다.
• pop() : 가장 최근에 삽입된 원소를 제거 후 반환합니다.
  • 비어있다면 null을 반환합니다.
• peek () : 가장 최근에 삽입된 원소를 제거하지 않고 반환합니다.

 

 

 

 

 

 

 

 

 

테스트코드

import java.util.stream.IntStream;


public class Test {
   public static void main(String[] args) {

      Stack<Integer> stack = new ArrayStack<>();
      IntStream.rangeClosed(0, 100).forEach(stack::push);

      StringBuilder sb = new StringBuilder();
      while (!stack.isEmpty()){
         sb.append(stack.pop());
         sb.append("\n");
      }
      System.out.println(sb.toString());

   }
}