Stack

Stack & StackInterface 구현

st-lab 님의 블로그를 참고해서 구현한 StackInterface & Stack이다.

StackInterface

package Interface_form;
 
/**
 * 
 * 자바 stack Interface입니다. <br>
 * StackInterface는 Stack에 의해 구현됩니다.
 * 
 * @author st_lab
 * @param <E> the type of elements in this Stack
 *
 * @version 1.0
 * 
 */
 
 
public interface StackInterface<E> {
	
	/**
	 * 스택의 맨 위에 요소를 추가합니다. 
	 * 
	 * @param item 스택에 추가할 요소 
	 * @return 스택에 추가된 요소 
	 */
	E push(E item);
	
	/**
	 * 스택의 맨 위에 있는 요소를 제거하고 제거 된 요소를 반환합니다.
	 * 
	 * @return 제거 된 요소 
	 */
	E pop();
	
	/**
	 * 스택의 맨 위에 있는 요소를 제거하지 않고 반환합니다.
	 * 
	 * @return 스택의 맨 위에 있는 요소 
	 */
	E peek();
	
	/**
	 * 스택의 상반 부터 특정 요소가 몇 번째 위치에 있는지를 반환합니다.
	 * 중복되는 원소가 있을경우 가장 위에 있는 요소의 위치가 반환됩니다.
	 *
	 * @param value 스택에서 위치를 찾을 요소
	 * @return 스택의 상단부터 처음으로 요소와 일치하는 위치를 반환.
	 *         만약 일치하는 요소가 없을 경우 -1 을 반환 
	 */
	/* 
	 *         ________
	 *         | a    |
	 * idx 3   |______|   search("w")
	 *         | e    |   --> 상단(idx 3)으로 부터 3번 째에 위치 
	 * idx 2   |______|       == return 되는 값 : 3
	 *         | w    |
	 * idx 1   |______| 
	 *         | k    |
	 * idx 0   |______|
	 * 
	 */ 
	int search(Object value);
	
	/**
	 * 스택의 요소 개수를 반환합니다.
	 * 
	 * @return 스택에 있는 요소 개수를 반환 
	 */
	int size();
	
	/**
	 * 스택에 있는 모든 요소를 삭제합니다.
	 */
	void clear();
	
	/**
	 * 스택에 요소가 비어있는지를 반환합니다.
	 * 
	 * @return 스택에 요소가 없을 경우 {@code true}, 그 외의 경우 {@code false}를 반환
	 */
	boolean empty();
}

Stack

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.EmptyStackException;

import Interface_form.StackInterface;

public class Stack<E> implements StackInterface<E> {
  private static final int DEFAULT_CAPACITY = 10;
  private static final Object[] EMPTY_ARRAY = {};

  private Object[] array;
  private int size = 0;

  public Stack() { // 초기 공간 할당 x
    this.array = EMPTY_ARRAY;
    this.size = 0;
  }

  public Stack(int capacity) { // 초기 공간 할당 o
    this.array = new Object[capacity];
    this.size = 0;
  }

  private void resize() {
    // 빈 배열일 경우
    if (Arrays.equals(array, EMPTY_ARRAY)) {
      array = new Object[DEFAULT_CAPACITY];
      return;
    }
    // 요소가 용적 / 2 보다 작을경우
    if (size < array.length / 2) {
      array = Arrays.copyOf(array, Math.max(DEFAULT_CAPACITY, (array.length / 2)));
      // Math.max는 크기가 DEFAULT_CAPACIYT보다 작아지는 상황을 방지하기 위해 사용
      return;
    }
    // 요소가 용적의 크기와 같을 경우
    if (size == array.length) {
      array = Arrays.copyOf(array, (array.length / 2));
      return;
    }
  }

  @Override
  public E push(E item) {
    if (array.length == size) {
      resize();
    }
    array[size] = (E) item;
    size++;

    return item;
  }

  @Override
  public E pop() {
    if (size == 0) {
      throw new EmptyStackException();
    }
    @SuppressWarnings("unchecked")
    E element = (E) array[size - 1];
    array[size - 1] = null;
    size--;
    resize();
    return element;
  }

  @SuppressWarnings("unchecked")
  @Override
  public E peek() {
    if (size == 0) {
      throw new EmptyStackException();
    }

    return (E) array[size - 1];
  }

  @Override
  public int search(Object value) {
    // value가 null일 때는 eqauls(null)이되어 null pointer exception이 발생할 수 있으니,
    // == 로 null값을 비교해준다.
    // 왜 null 조회가 필요한지는 나중에 알아보자
    if (value == null) {
      for (int i = size - 1; i >= 0; i--) {
        if (arr[i] == value) {
          return size - i;
        }
      }
    } else {
      for (int i = size - 1; i >= 0; i--) {
        if (arr[i] == value) {
          return size - i;
        }
      }
    }
    return -1;
  }

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

  @Override
  public void clear() {
    for (int i = 0; i < size; i++) {
      array[i] = null;
    }
    size = 0;
    resize(); 
    // resize 시 배열의 값이 아무것도 없어도 Arrays.equals(array, DEFAULT_ARRAY) 조건에 충족되지 않아 사이즈가 절반으로 줄임
  }

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

  @Override
  public Object clone() throws CloneNotSupportedException {
    Stack<E> clone = (Stack<E>) super.clone();

    // clone.DEFAULT_CAPACITY = 10;
    // clone.EMPTY_ARRAY = {};
    // clone.array;
    // clone.size = 0;

    clone.array = new Object[size];

    // for (int i = 0; i < size; i++) {
    //   clone.array[i] = array[i];
    //   clone.size++;
    // }
    System.arraycopy(clone, 0, array, 0, size);
    return clone();
  }

  public Object toArray() {
    // return  array;
    // array의 용적이 size보다 크므로 size 만큼의 크기를 가지는 새로운 배열을 리턴해주자
    return Arrays.copyOf(array, size);
  }

  @SuppressWarnings("unchecked")
  public <T> T[] toArray(T[] a) {
    if (a.length < size) {
      //a = (T[]) Array.newInstance(getClass().getComponentType(), size);
      return Arrays.copyOf(array, size, getClass());
    }
    System.arraycopy(array, 0, a, 0, size);
    return a;
  }

  public void sort() {
    sort(null);
  }

  public void sort(Comparator<? super E> c) {
    // Arrays.sort(array, (Comparator) c);
    Arrays.sort((E[]) array, 0, size, c);
    // size 까지만 정려하면 되기 때문에 위  Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) 를 사용
  }
}

ArrayList를 상속받는 Stack

Stack은 기본적으로 Vector를 상속받는다. 그리고 Vector는 ArrayList와 구조가 유사하다. (차이점은 동기화를 지원하느냐 안 하느냐)

그래서 앞서 구현한 ArrayList를 상속 받아 Stack을 구현해보자

import Interface_form.StackInterface;

public class StackExtendArrayLIst<E> extends ArrayList<E> implements StackInterface<E> {

  public StackExtendArrayLIst() {
    super();
  }

  public StackExtendArrayLIst(int capacity) {
    super(capacity);
  }

  @Override
  public E push(E item) {
    super.addLast(item);
    return item;
  }

  @Override
  public E pop() {
    int length = super.size();
    return (E) super.remove(length - 1);
  }

  @Override
  public E peek() {
    int length = super.size();
    return (E) super.get(length - 1);
  }

  @Override
  public int search(Object value) {
    int idx = super.lastindexOf(value);
    if (idx >= 0) {
      int size = size();
      return size - idx;
    }
    return -1;
  }

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

매우 간편하게 구현할 수 있다.

소스 코드 링크

StackInterface

Stack

출처)

Stack

StackInterface