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

자료구조(Data Structure)란?

• 프로그램에서 사용할 많은 데이터(data)를
  메모리 상에서 관리하는 여러 방법들

• 자료구조의 종류중에서 구현하고자 하는 프로그램에 맞는
  최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요하다.

자료구조의 장점

• 효율적인 자료구조는 성능좋은 알고리즘의 기반이 된다.

• 효율적인 자료의 관리는 프로그램의 수행속도와 밀접한 관련이 있다.

스택(Stack)

• 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조 (Last In First Out ( 후입선출 ) 구조

  • 블럭, 택배 상자 등등...

• 맨 마지막 위치(top)에서만 자료를 추가, 삭제, 꺼낼 수 있음

  • 중간의 자료를 꺼낼 수 없다.

• 가장 최근의 자료를 찾아오거나 게임에서 히스토리를 유지하고
  이를 무를때 사용할 수 있다.

  • 오목, 장기에서 한수 무르는 행위

• 함수의 메모리는 호출 순서에 따른 stack구조

• jdk 클래스 : Stack

스택(Stack) 구현

• 배열(MyArray.java) 활용하여 스택 구현하기

MyArrayStack.java

import java_basic.data_structure.array.MyArray;

public class MyArrayStack {
  int top; // Stack의 현재 크기
  
  MyArray arrayStack;

  public MyArrayStack(){
    top = 0;
    arrayStack = new MyArray();
  }

  public MyArrayStack(int size){ // siza = 배열 최대 크기
    arrayStack = new MyArray(size);
  }

  public void push(int data){
    if (isFull()) {
      System.out.println("stack is full");
      return;
    }

    arrayStack.addElement(data);
    top++; // push를 진행할 때마다 top 1증가
  }

  // pop : return과 동시에 return한 값을 삭제한다.
  public int pop(){
    if(top==0){
      System.out.println("stack is empty");
      return MyArray.ERROR_NUM;
    }
    // --top : top자체의 값을 1 감소시키고 반영한다.
    return arrayStack.removeElement(--top);
  }

  // peek : return만 한다.(삭제 없음)
  public int peek(){
    if(top == 0){
      System.out.println("stack is empty");
      return MyArray.ERROR_NUM;
    }
    // top -1 : top자체의 값에서 1을 뺀 값을 뜻한다.
    return arrayStack.getElement(top-1);
  }

  public int getSize(){
    return top;
  }

  public boolean isFull(){
    return top == arrayStack.ARRAY_SIZE;
  }
  public boolean isEmpty(){
    return top==0;
  }

  public void printAll(){
    arrayStack.printAll();
  }
}

MyArrayStackTest.java

public class MyArrayStackTest {
  public static void main(String[] args) {
    MyArrayStack stack = new MyArrayStack(3); // size = 3;

    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.push(40);

    stack.printAll();

    // System.out.println("top element is " + stack.pop());
    System.out.println("top element is " + stack.peek());
    stack.printAll();
    System.out.println("stack size is " + stack.getSize());
  }
}

// result
stack is full
10
20
30
top element is 30
10
20
30
stack size is 3