Stack 구현 (배열 resizing)

스택(Stack)

---

 스택(Stack)은 LIFO(Last In First Out)구조로 마지막에 저장한 데이터가 먼저 나온다. 예를 들면 1,2,3이라는 데이터를 넣으면 뺄 때는 반대로 3,2,1 역순으로 출력되는 것이다. 자바에서는 java.util에 Stack이 제공되지만 Stack의 구현 원리는 간단하기 때문에 알아둬서 나쁠게 없다. 특히, 배열을 resizing하는 부분은 java.util.Stack만 쓰던 나에게 아차 싶었던 부분...  예전에 배웠는데 까맣게 잊어버리고 있었다. 다시는 잊지 않도록 정리해본다..ㅠㅠ

MyStack.java

---

public class MyStack {
    
    private Object[] list;
    private int top;
    private int size;
    
    public MyStack(int size) {
        this.list = new Object[size];
        this.top = -1;
    }
    
    public void push(Object value) {
        if (size == list.length) {
            Object[] arr = new Object[list.length + (list.length >> 1)]; 
            
            for (int i = 0; i < list.length ; i++) {
                arr[i] = list[i];
            }
            
            list = arr;
        }
        
        list[++top] = value; // top의 초기값은 -1이니까 값을 먼저 증가시킨다.
        size++;
    }
    
    public Object pop() {
        if (top == -1) 
            return null;
        
        size--;
        return list[top--];
 
    }
    
    public boolean empty() {
        return size == 0; //size가 0이면 true 아니면 false
    }
    
    public int size() {
        return this.size;
    }
 
}

StackTest.java

---

public class StackTest {
 
    public static void main(String[] args) {
        
        MyStack s = new MyStack(5);
        
        s.push("하나");
        s.push("둘");
        s.push("셋");
        s.push("넷");
        s.push("다섯");
        s.push("여섯"); // resizing
        s.push("일곱");
        
        System.out.println("현재 스택의 크기 : " + s.size());
        
        System.out.println("pop : " + s.pop());
        System.out.println("pop : " + s.pop());
        
        System.out.println("현재 스택의 크기 : " + s.size());
        
        while(!s.empty()) {
            
        System.out.println("pop : " + s.pop());
        
        }
        
        System.out.println("현재 스택의 크기 : " + s.size());
        System.out.println("pop : " + s.pop());
        
 
        
            
        
    }
 
}

실행결과

---

배열의 크기 조정

---

 MyStack s = new MyStack(5);

 초기에 스택의 크기를 5로 초기화했다. 그런데 스택의 크기를 초과하는 push()가 들어왔다. 

이 때 스택의 크기가 늘어나야 한다. 그렇지 않으면 s.push("여섯")을 하는 순간 JVM은 ArrayIndexOutOfBoundException를 발생시킨다.

 그래서 push()에 size와 list.length가 같아질 때 스택의 크기를 자동으로 증가시키는 소스를 추가했다.

public void push(Object value) {

        if (size == list.length) {

            Object[] arr = new Object[list.length + (list.length >> 1)]; 

            

            for (int i = 0; i < list.length ; i++) {

                arr[i] = list[i];

            }

            

            list = arr;

        }

        

        list[++top] = value; // top의 초기값은 -1이니까 값을 먼저 증가시킨다.

        size++;

    }

 새로운 배열을 생성해 기존 길이의 절반만큼 크기를 늘려준다. 이 코드에서는 5에서 5의 절반인 2(소수점은 제외한다)만큼 증가시켜서 크기가 7인 배열이 생성되었다. 비트 연산자를 사용하면 일반 연산자보다 속도가 빠르다고 한다. (자세한 내용은 더 공부해서 정리하도록 하겠다(...))

 기존의 list 배열의 값을 arr에 담아준다. 그 다음 if문을 벗어나 "여섯"과 "일곱"을 저장한다.

 크기가 7인 배열(0x300)을 가리키는 참조변수 arr의 주소를 list에 넘겨준다.

 그 결과 list는 기존의 0x100 배열이 아닌 크기를 resizing한 0x300 배열을 참조하게 된다. 그리고 기존의 배열은 가비지가 된다.