자바로 배우는 스택 (Stack)

개념

• 기본 자료 구조의 하나로 후입선출 / LIFO (Last In First Out) 형태로 데이터를 추가하고 반환한다.

• 

인터페이스

• push(value): 데이터를 리스트에 추가

• pop(): 가장 마지막에 입력된 혹은 스택에 가장 위에 위치하고 있는 항목을 반환

구현

• 스택은 배열(Array)와 연결리스트(Linkded list)를 통해 구현이 가능하다.
  Linked List로 구현하는 방법은 추후 Linked list에 대하여 알아 볼 때 같이 살펴보면 좋을 것으로 생각되며 지금은 스택의 개념을 먼저 짚고 넘어가야 하기 때문에 이해가 쉬운 배열로 간단한 스택을 구현해 보도록 하겠다.

• 스택은 후입선출(LIFO)의 형태를 가지므로 push()가 호출될 떄는 순차적으로 배열에 저장을 하고 pop()이 호출되었을 때는 저장된 배열의 가장 마지막 데이터를 반환하면 된다. 이를 구현하면 아래와 같이 된다.

• class Stack {
  
    private static final int MAX_N = 100;
  
    int mTop;
    int mStack[] = new int[MAX_N];
  
    public Stack() {
        mTop = 0;
    }
  
    public boolean isEmpty() {
        return (mTop == 0);
    }
  
    public boolean isFull() {
        return (mTop == MAX_N);
    }
  
    public boolean push(int value) {
        if (isFull()) {
            System.out.println("stack overflow!");
            return false;
        }
        mStack[mTop] = value;
        mTop++;
  
        return true;
    }
  
    public Integer pop() {
        if (mTop == 0) {
            System.out.println("stack is empty!");
            return null;
        }
  
        mTop--;
        Integer value = new Integer(mStack[mTop]);
  
        return value;
    }
  }

동작 확인

• 
    private static void testStack() {
        Stack stack = new Stack();
  
        for (int i = 0; i < 10; i++) {
            System.out.print("push value: " + i + "\n");
            stack.push(i);
        }
  
        System.out.print("\n");
  
        for (int i = 0; i < 10; i++) {
            System.out.print("pop value: " + stack.pop() + "\n");
        }
    }

• push value: 0
  push value: 1
  push value: 2
  push value: 3
  push value: 4
  push value: 5
  push value: 6
  push value: 7
  push value: 8
  push value: 9
  

• pop value: 9
  pop value: 8
  pop value: 7
  pop value: 6
  pop value: 5
  pop value: 4
  pop value: 3
  pop value: 2
  pop value: 1
  pop value: 0