[자료구조] Stack

■ 개념

- Stack 자료구조는 데이터를 일시적으로 저장하기위한 자료구조

- 마지막에 추가된 데이터가 가장먼저 제거되는 LIFO(Last In First Out)

- Stack포인터라고 불리는 인덱스 변수를 사용하여 가장위에 존재하는 데이터를 추적한다

top이라는 index변수를 생성하여 포인터처럼 활용

■ 특징

Stack에 데이터를 추가하는 작업은 "push", 가장 위에 존재하는 데이터를 꺼내는 작업은 "pop"이라고 한다.
1. 제한된 접근

  Stack은 데이터를 꺼내거나 추가할 때 제일 위에 존재하는 데이터만 접근할 수 있다.
이는 데이터가 추가되고 제거될 때 다른데이터에 영향을 미치지 않게 하기 위함이다.

2. 속도

  Stack은 가장 위에 존재하는 데이터에대한 데이터 추가, 제거 및 접근에 최적화되어있다.
이러한 작업은 상수 시간(O(1))에 해당한다.

📌상수시간: 어떤 문제를 풀이하는데 필요한 연산 시간이 입력 자료에 관계없이 일정함을 의미한다

3. 메모리

  Stack은 선형메모리 구조를 가지며, 데이터를 구가할 때마다 메모리를 새로 할당하지 않아도 되어 효율적이다.

 

 

■ 직접 구현

public class Stack01 {

  /*
   * # 구현 목록
   * - int[] data: stack을 담을 배열
   * - top: stack의 포인터
   * - Stack: 생성자 필요
   * - pop
   * - push
   * - peek    : 현재 top이 보고있는 값
   * - isEmpty : stack이 비어있는지 확인
   * - isFull  : stack이 가득차있는지
   * - size    : stack의 현재 사이즈(몇개를 가지고있는가)
   */
    
    private int[] data;//stack의 값을 담을 배열
    private int top; //stack 포인터 top(index변수)

    public void Stack(int size){
      data = new int[size];
      top = -1;
      //>배열 = 0번부터, 따라서 -1이면 존재하지 않음
    } 

    public boolean isEmpty(){//stack이 비어있는지 검증
      return top == -1; //이 명제가 참 => 비어있다
    }
    
    public boolean isFull(){//stack이 가득찻는지 검증
      return top == data.length - 1;
    }
  
    public int peek(){
      return data[top];
    }

    public int push(int num){
      if(isFull()){//값을 넣기 전 검증
        throw new RuntimeException("stack이 가득차있습니다.");
      }
      return data[++top] = num; //++top해주고 num을 넣어주기
    }

    public int pop(){
      if(isEmpty()){//값을 빼기 전 검증
        throw new RuntimeException("stack이 비어있습니다.");
      }
      return data[top--];//꺼내주고 top-1
    }
    public int size(){
      if(isEmpty()){//비어있는지 검증
        throw new RuntimeException("stack이 비어있습니다.");
      }
      return top+1;//data.length를 해도되지만 이미 사용중인 top을 이용하자
    }

    public static void main(String[] args) {
      //테스트
      Stack st = new Stack(5);

      System.out.println(st.size());
      st.push(1);
      st.push(2);
      st.push(3);
      st.push(4);
      st.push(5);
      // st.push(6);
      System.out.println("size: " +st.size());
      System.out.println("peek: " +st.peek());
      System.out.println(st.pop()); 
    }
}​

■ 후기

이제야 스택을 스스로 작성할 수 있게되었다. 진짜 후련하다