자료구조 다시보기- stack

오늘의 TIL 힘차게 나와주세요 ~~~~~~!!!

참고 1 - javatpoint What is a Stack?
참고 2 - [자료구조 알고리즘] Stack 구현하기 in Java

1. stack

스택은 LIFO (Last In First Out)을 따르는 자료구조이다.
한 방향으로만 흘러가가기에 queue 와는 다르게 가장 위에 있는 element 만 가르키는 포인터 하나만 있다.
현실세계에서 책상에 책을 쌓아두면 가장 위에 쌓은 책부터 치울 수 있는 것과 같다.

2. stack 자료구조를 사용하는 예시

• Balancing of symbols : 클래스 선언의 시작과 끝에는 {} 가 들어가야한다.
  이렇게 선언의 시작과 끝을 알때도 스택을 사용한다. { 로 시작했다면 탑에 }가 들어올때까지가 한 클래스다.
• 메모리 관리 : 스택 메모리 블럭에 함수가 생성될 때 차곡차곡 데이터 저장했다가 함수 종료되면 메모리 정리한다.
• string 을 거꾸로 만들고 싶을때: stack 에 문자를 하나씩 넣고 pop 하면 뒤에서부터 뺄 수 있기에 거꾸로 배열할 수 있다.

3. java 로 구현

import java.util.EmptyStackException;

public class StackTest<T> {
    class Node<T>{
        private  T data;
        private  Node<T> next;
        public Node(T data){
            this.data = data;
        }
    }

    private Node<T> top;

    public T pop(){
        if(isEmpty(){
            throw new EmptyStackException();
        }
        T value = top.data; //top 의 데이터 저장
        top = top.next; //top을 없애고 그 다음 노드가 탑이 됨
        return value; // 값 반환
    }

    public T peek(){
        if(top == null){
            throw new EmptyStackException();
        }
        return top.data;
    }

    public void push(T input){
        Node<T> newNode =new Node<>(input);
        if(!isEmpty()){
            newNode.next = top; // 다음 값에 현재 탑 저장
        }
        top = newNode; //탑 바꾸기 
    }

    public boolean isEmpty(){
        return top == null ? true : false;
    }
}

유닛 테스트

  @Test
    void stackTest(){
        StackTest<Integer> stack = new StackTest<Integer>();
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.pop();
        assertThat(4).isEqualTo(stack.peek());
    }

    @Test
    void isEmptyTest(){
        StackTest<Integer> stack = new StackTest<Integer>();
        assertThat(true).isEqualTo(stack.isEmpty());
        stack.push(2);
        stack.push(3);
        assertThat(false).isEqualTo(stack.isEmpty());
        stack.pop();
        stack.pop();
        assertThat(true).isEqualTo(stack.isEmpty());
    }