[Java] 배열로 Stack 구현하기

✨ 자료 구조를 공부하면서 stack을 배열로 구현하는 것은 많이 보았지만 삽입할 때 요소의 type까지 체크해주는 경우가 없어서 직접 구현해봤습니다.

🎱 Stack

LIFO(Last In First Out)의 구조를 가진 자료 구조
가장 마지막에 넣은 데이터가 가장 먼저 나간다.

---

🎨 구현할 메서드

push(element) : 데이터를 삽입한다.
pop() : 데이터를 뺀다. 이때 빠지는 데이터는 가장 마지막에 넣은 데이터다.
isEmpty() : 배열이 비었는지 여부를 판단한다. 데이터가 없으면 true, 하나라도 있으면 false를 리턴한다.
peek() : 가장 마지막에 넣은 데이터를 리턴한다.
clear() : 배열을 초기화 시킨다.
isFull() : 배열이 가득찼는지 여부를 판단한다. 데이터가 꽉 찼으면 true, 아니면 false를 리턴한다.
printStack() : 배열에 있는 모든 요소를 출력한다.
size() : 배열의 크기를 리턴한다.

stack 세팅

class ArrayStack{
	private String type;
    private int capacity;
    private int top = -1;
    private Object stackArray[];
    
    ArrayStack(String type){
    	this.type = type;
        this.capacity = 100;
        stackArray = new Object[capacity];
    }
    ArrayStack(String type, int capacity){
    	this.type = type;
        this.capacity = capacity;
        stackArray = new Object[capacity];
    }
    
    public void push(Object element){}
    
    public Object pop(){}
    
    public boolean isEmpty(){}
    
    public boolean isFull(){}
    
    public Object peek(){}
    
    public void clear(){}
    
    public void printStack(){}
    
    public int size(){}
}

stack을 구현할 때 필요한 멤버 변수는 데이터 타입인 type, stack의 최대 용량인 capacity, 마지막 데이터의 위치 top, 데이터를 저장할 stackArray이다. 데이터의 타입은 기존 stack과 같이 원하는 타입을 넣을 수 있도록 Object로 지정하였다.

stack을 생성할 때는 타입을 지정해준다. 이번에 구현할 때는 최대 용량을 지정해주기 위해 두개의 생성자를 구현한다.

ArrayStack stack = new ArrayStack("String");
ArrayStack stack = new ArrayStack("Integer",100);

isEmpty()

가장 먼저 구현해볼 메서드는 isEmpty이다. 다른 메서드에서도 사용하기 때문에 먼저 구현한다.

public boolean isEmpty(){
	return (top == -1);
}

배열이 비었는지 확인할 때는 현재 데이터의 위치를 찾으면 된다. 아무 값도 들어있지 않으면 -1을 가리키므로 top == -1 인지 체크한다.

isFull()

isFull은 isEmpty와 마찬가지로 다른 메서드에서 사용한다.

public boolean isFull(){
	return (top >= this.capacity-1);
}

배열이 가득 찼는지 확인할 땐느 현재 데이터의 위치와 최대 용량을 비교하면 된다. 이때 top은 -1부터 시작한 데이터의 인덱스번호이지만 capacity는 말 그대로 용량이기 때문에 1을 빼야 크기가 맞다. 만약 데이터의 위치가 용량보다 크거나 같다면 가득찼다는 뜻이다.

push(Object element)

push 할 때는 들어갈 요소의 타입이 선언한 타입과 같은지, 용량이 가득찬 상태인지 체크해준다.

public void push(Object element){
    if(!this.type.equals(element.getClass().getSimpleName()){
    	throw new IllegalStateException("타입 에러");
    }
    if(isFull()){
    	throw new IllegalStateException("배열이 가득 참");
    }
    
    stackArray[++top] = element;
}

타입을 비교할 때는 선언한 타입과 들어온 요소의 타입을 비교한다. 요소의 타입은 getClass().getSimpleName() 통해 얻을 수 있다. 보통 타입을 구할 때는 getClass().getName()을 많이 사용한다. 이 경우에는 단순히 String이 아닌 java.lang.String과 같이 풀네임으로 구해지기 때문에 getSimpleName()을 사용하였다.

push할 때 배열이 가득차면 더 이상 넣지 못하게 하기 위해 isFull 메서드를 사용한다.

위의 두 경우가 아니라면 top을 증가시키고 해당되는 위치에 element를 넣어준다. top은 -1로 시작했기 때문에 먼저 증가시킨 후 element를 넣어줘야 한다.

pop()

pop 할 때는 배열이 비었는지 아닌지 체크한다. 또한 해당되는 데이터를 null로 바꾸어준다.

public Object pop(){
	if(isEmpty()){
    	throw new IllegalStateException("배열이 비었음.");
    }
    Object element = arr[top];
    stackArray[top] = null;
    top--;
    return element;
}

배열이 비었는지 확인하기 위해 isEmpty를 활용한다. 배열이 비었다면 에러를 발생시킨다.
element는 제거될 요소이다. 미리 저장해둔다. 그후 제거될 데이터를 null로 바꿔준다. 데이터가 제거되었기 때문에 마지막에 저장된 데이터는 top에서 1을 감소시킨 위치이다.

peek()

peek은 배열이 비었는지 여부를 판단한 후 top 위치에 있는 데이터를 반환해준다.

public Object peek(){
	if(isEmpty()){
    	throw new IllegalStateException("배열이 비었음.");
    }
    
    return stackArray[top];
}

clear()

clear는 이미 배열이 비었다면 초기화해줄 필요가 없기 때문에 배열이 비었는지 여부만 판단하면 된다.

public void clear(){
	if(isEmpty()){
    	throw new IllegalStateException("배열이 비었음.");
    }
    this.top = -1;
    stackArray = new Object[this.capacity];
}

배열을 초기화 했기 때문에 top을 원래 값인 -1로 바꾼다. 지정해둔 용량에 맞게 새로 배열을 생성한다.

printStack()

배열에 있는 모든 요소를 출력한다. 이때 배열의 용량이 가득차지 않았다면 남은 공간은 null이기 때문에 null이 아닐 경우에만 출력한다.

public void printStack(){
	for(Object ele : stackArray){
    	if(ele != null){
        	System.out.print(ele+" ");
        }
    }
}

size()

public int size(){
	return (this.top + 1);
}

size는 현재 데이터의 위치에 1을 더한 값이다. top은 현재 위치로 인덱스 번호를 나타내기 때문에 1을 더해준다.

---

전체 코드

class ArrayStack{
    private int top;
    private int capacity;
    private Object stackArray[];
    private String type;

    ArrayStack(String type){
        this.type = type;
        this.top = -1;
        this.capacity = 100;
        stackArray = new Object[capacity];
    }
    ArrayStack(String type, int capacity){
        this.type = type;
        this.top = -1;
        this.capacity = capacity;
        stackArray = new Object[capacity];
    }

    public boolean isEmpty(){
        return (top == -1);
    }

    public boolean isFull(){
        return (top >= this.capacity-1);
    }

    public int size(){
        return this.top+1;
    }
    public void push(Object element){
        checkType(element);
        checkIsFull();

        stackArray[++top]  = element;
    }

    public Object pop(){
        checkIsEmpty();
        Object ele = stackArray[top];
        stackArray[top] = null;
        --top;
        return ele;
    }

    public Object peek(){
        checkIsEmpty();
        return stackArray[top];
    }

    public void clear(){
        checkIsEmpty();

        this.top = -1;
        stackArray = new Object[this.capacity];
    }

    public void printStack(){
        for(Object ele : stackArray){
            if(ele!=null)
                System.out.print(ele+" ");
        }
    }

    private void checkType(Object obj){
        if(!Objects.equals(this.type, obj.getClass().getSimpleName())){
            throw new IllegalStateException("타입 에러");
        }
    }
    private void checkIsFull(){
        if(isFull()){
            throw new IllegalStateException("스텍이 가득참");
        }
    }
    private void checkIsEmpty(){
        if(isEmpty()){
            throw new IllegalStateException("스텍이 비었음");
        }
    }
}

여러 가지 체크할 사항들은 여러 번 사용되기 때문에 따로 메서드를 만들었습니다.

---

참고 링크 : Java 배열로 스택(Stack) 구현하기