20180324 Stack : Data Structure

개요

스택은 기본적인 자료구조. 자바 내 API 로 제공한다. 간단한게 스택을 살펴보고 직접 구현해보는 시간을 가진다. 스택은 기본적인 LIFO (Last In First Out) 구조를 가진다. (후입선출) 쓰이는 메소드는 다양하게 있지만 몇개만 알면 사용이 가능하고 직접 구현도 할 수 있다.

• push

• pop

• peek

• setSize

• size

• isEmpty (extends Vector Class)

• empty (Stack Class)

• contains 

• iterator

대략 쓰일 수 있는 것들은 위와 같을 것이다. 이제 알아보자.

- Wrapper Class 인 Integer 타입으로 스택 변수를 초기화.

Stack<Integer> stack = new Stack<Integer>();

- Stack은 클래스이며, 벡터 클래스를 상속

public class Stack<E> extends Vector<E>

- Stack 초기화시, 기본 사이즈 설정은 10이다.

public Vector() {
    this(10);
}

- size() : 스택이 가진 요소 개수

- capacity() : 스택의 현재 전체 용량

Stack<Integer> stack = new Stack<Integer>();
stack.size();
stack.capacity();

- Stack의 setSize() 메소드

파라미터로 받는 newSize 값에 대해서 기존의 값보다 크면 Stack 의 용량을 늘린다. 하지만 파라미터로 newSize 의 값이 작다면 newSize 부터 Stack 이 가지고 있는 요소의 값까지 모두 null 값으로 만들어 GC의 처리를 받게 한다.

public synchronized void setSize(int newSize) {
    modCount++;
    if (newSize > elementCount) {
        ensureCapacityHelper(newSize);
    } else {
        for (int i = newSize ; i < elementCount ; i++) {
            elementData[i] = null;
        }
    }
    elementCount = newSize;
}

- Stack Implement in Java ( 직접 구현 )

클래스 내부에 따로 int 형 배열을 선언하였다. 하지만 실제 자바 API 안에는 Object 타입으로 배열을 선언해서 데이터 형에 맞게 변환할 수 있도록 설정해주었다. 

Object [] objectArray = new Object[10];

스택의 기본적인 연산인 push 와 pop 이외에도 다른 부분들도 구현해보았다.

class Stack{
    private int[]array = new int[10];
    private int elementCount;
    private int top;
    
    public Stack(){
        this.elementCount = 0;
        this.top = 0;
    }
    
    public void push(int value){
        if(top >= array.length){
            reSize(top << 1);
        }
        
        elementCount++;
        array[top++] = value;
    }
    
    public Integer pop(){
        if(!(top <= 0)){
            elementCount--;
            return array[--top];
        }
        
        return -1;
    }
    
    public Integer size(){
        return elementCount;
    }
    
    // 비었는지 여부 출력, 
    public Integer empty(){
        if(elementCount == 0)
            return 1;
        
        return 0;
    }
    
    // 스택의 가장 맨 위의 값 출력, 없으면 -1
    public Integer top(){
        if(elementCount == 0)
            return -1;
        
        return array[(top-1)];
    }
    
    public void reSize(int newSize){
        array = Arrays.copyOf(array, newSize);
    }
}

[ 백준문제 ]

[ 2504번 : 괄호의 값 ]

들어오는 문자열에 대해서 해당 문자열이 올바른 괄호인지를 판단하는 것부터 시작해서 주어진 조건과 수식을 확인하여 계산하는 문제이다. 스택을 두 개 쓴다라고 생각했지만 스택을 두 개 쓰는 것보단 하나의 String 타입의 스택을 쓰면서 열린괄호는 넣고 닫힌 괄호는 스택 내부의 값이 숫자인지 혹은 괄호인지 판단해서 순차적으로 계산하면 면 된다.

약간 유의할 것은 숫자가 여러번 연속해서 나타나는 값들에 대해서는 무조건 덧셈연산을 수행하도록 나는 코드 구성을 그렇게 하였다. 

코드링크