[JAVA] Stack 구현

학습 내용

스택의 대표적인 3가지 기능을 구현 할 수 있습니다.

시간 복잡도 분류를 할 수 있습니다.

 

• 추가
  • 요소 추가
• 삭제
  
  • 요소 삭제

• 조회
  • 최상단 요소 반환

---

필드

private E[] array;
private int top;
private int capacity;

public MyStack(int size) {
    array = (E[]) new Object[size];
    capacity = size;
    top = -1;
}

 

---

추가

1. 요소 추가

public void push(E element) {
    if (isFull()) {
        E[] bigger = (E[]) new Object[array.length * 2];
        System.arraycopy(array, 0, bigger, 0, array.length);
        array = bigger;
    }
    array[++top] = element;
}

배열이 가득 차면 2배로 길이를 늘려주고 그렇지 않다면 배열에 요소를 넣어 줍니다.

 

시간 복잡도는 O(1)로 보여집니다.

 

---

삭제

1. 요소 삭제

public E pop() {
    if (isEmpty()) {
        throw new NullPointerException("배열이 비어있습니다.");
    }
    return array[top--];
}

배열이 비어 있으면 예외를 던지고 그렇지 않다면 배열의 값을 반환합니다.

 

이 기능도 역시 O(1) 의 시간 복잡도를 가집니다.

 

---

조회

1. 최상단 요소 반환

public Object peek() {
    if (!isEmpty()) {
        E element = array[top];
        return element;
    } else
        System.exit(-1);
    return -1;
}

배열이 비어 있지 않다면 배열의 요소를 반환 하고 그렇지 않다면 시스템을 종료합니다.

 

이 기능도 역시 O(1) 의 시간 복잡도를 가집니다.

 

---

테스트

MyStack stack;

@BeforeEach
public void beforeEach() {
    stack = new MyStack(10);
}


@Test
@DisplayName("스택 최상단에 요소 추가")
void push() throws NoSuchFieldException {
    // given
    String input1 = "첫번째";
    String input2 = "두번째";
    String input3 = "세번째";

    // when
    stack.push(input1);
    stack.push(input2);
    stack.push(input3);

    int result = stack.size();
    // then
    Assert.assertEquals(3,result);
    Assertions.assertEquals(false, stack.isEmpty());
    Assert.assertEquals(input3, stack.pop());
    Assert.assertEquals(input2, stack.pop());
    Assert.assertEquals(input1, stack.pop());

}


@Test
@DisplayName("요소 꺼내오기")
void pop() {
    // given
    String input1 = "첫번째";
    String input2 = "두번째";
    String input3 = "세번째";

    stack.push(input1);
    stack.push(input2);
    stack.push(input3);

    // when
    Object result1 = stack.pop();
    Object result2 = stack.pop();
    Object result3 = stack.pop();

    // then
    Assertions.assertEquals(input3, result1);
    Assertions.assertEquals(input2, result2);
    Assertions.assertEquals(input1, result3);
    Assertions.assertEquals(0, stack.size());
}

@Test
@DisplayName("최상단의 요소를 반환")
void peek() {
    // given
    String input1 = "첫번째";
    String input2 = "두번째";
    String input3 = "세번째";

    stack.push(input1);
    stack.push(input2);
    stack.push(input3);

    // when
    Object result1 = stack.peek();

    // then
    Assertions.assertEquals(input3, result1);
}

 

테스트 통과

 

---

정리

스택의 구조를 이해하고 직접 구현 해보았습니다.

ArrayList 와 LinkedList 보다 구현 하는 기능들이 적어 오류의 발생 횟수는 적을 것이라 판단합니다.

 

 

 

참조 : https://www.techiedelight.com/stack-implementation-in-java/