[자료구조] Java Stack 구현 / 자바 스택 구현

[자료구조] Java ArrayList 구현

[자료구조] Java ArrayList 구현

모든 데이터 및 알고리즘을 List  구조만 이용해서 최적화된 프로그래밍을 할 수 있으면 얼마나좋을까?

안타깝게도 그렇지 않기 때문에 세상에는 List를 제외한 많은 자료구조가 존재한다.

이번에는 Stack과 관련된 구현을 할 예정이다

Stack은 Last In First Out 구조를 갖는다. 이 LIFO 구조를 갖는 가장 흔한 예를 들어보면 많이 원기둥으로 된 초콜릿 통을 얘기한다. 하지만 우리 프로그래밍 세계에는 초콜릿 통만 만들지 않으니, 다른 예를 알아볼 필요도 있다.

이런 예는 어떨까?

구조선에 총 500kg의 인원을 태울 수 있다. 구조를 기다리는 사람들은 차례로 줄 서서 탑승을 기다리고 있다. 구조선이 도착지에 도착하면, 탑승구에 있는 사람부터 내린다. 구조선은 총 탑승 중량이 500kg을 넘어가면, 출발한지 조금 지나 침몰한다. 탑승할 때, 중량을 나타내는 전자저울이 있다.

무인도 예

해당 문제는 도착지에 도착하건, 중량초과를 하건, 제일 마지막에 탑승한 사람부터 내려야 한다. 이러한 경우 Stack을 이용해 구현할 수 있겠다.

---

Stack은 Last In First Out

Stack에 대해 이미지를 연상해보면 다음과 같이 생각하면 편하다.

stack 이미지

즉, 제일 위에서(top) 데이터를 삽입하거나, 데이터를 반환한다.

stack은 리스트처럼 1. 크기가 고정(배열) 2. 크기가 동적(ArrayList)의 성격을 가질 수 있고, 구현 방법은 그 성격과 같다.

크기를 고정시키고 싶다면 배열로 구현하고, 크기를 동적으로 변경하고 싶다면 ArrayList로 구현하면 된다. 오늘 게시글에서는 크기가 고정된 Stack을 구현해 보겠다.

---

Stack에는 어떤게 필요할까?

Stack은 어떤 기능이 필요할까? 기본적인 목적은 제일 위에서 데이터를 삽입, 반환할 수 있어야 한다. 부가적으로, 현재 Stack의 사이즈와 크기, 초기화, 그리고 비어있거나 꽉찼는지를 구할 수 있으면 된다.

따라서 제일 위를 구하는 top, 크기를 담는 capacity를 가지면 된다.

Stack에서는 ArrayList와 달리 add, remove라는 함수 이름을 사용하지 않고 각각 push, pop이라는 이름의 함수를 사용한다.

---

Stack 구현

따라서 Stack의 기본은 다음과 같다.

public class Stack<T> {
	int top;
	int capacity = -1;
	T[] stack;
	Stack(int capacity){
		this.capacity = capacity;
		stack = (T[]) (new Object[capacity]);
		top = -1;
	}
}

top을 -1로 초기화 하는 이유는 개발의 간편함을 위함이다. 따라서 스택이 비어있을때 top은 -1이 된다.

고정된 크기를 갖는 Stack을 구현하기 생성자는 capacity값을 전달해야 한다.

데이터를 삽입할 때는 Stack이 가득찼는지 확인해야 한다. 그리고 공간이 남아있다면 데이터를 삽입하면 된다.

public class Stack<T> {
	...
	public void push(T element) {
		if(isFull()) {
			System.out.println("Stack이 가득 찼습니다.");
			return;
		}
		
		stack[++top] = element;
	}
	
	public boolean isFull() {	return (this.top == this.capacity-1);	}
   	...
}

isFull(): 스택이 가득찼는지 확인한다.

데이터를 반환할 때는 삽입할 때와 반대로 Stack이 비어있는지 확인해야 한다. 그리고 비어있지 않다면 데이터를 반환하면 된다.

public class Stack<T> {
	...
	public T pop() {
		if(isEmpty()) {
			System.out.println("Stack이 비어있습니다.");
			return null;
		}
        
		return stack[top--];
	}
	
	public boolean isEmpty() {	return (this.top == -1);	}
   	...
}

isEmpty(): 스택이 비어있는지 확인한다.

그런데 우리는 반환하지 않고 데이터를 확인만 하고 싶을수도 있다. 이럴 때를 위해 peek()라는 함수가 존재한다. 이는 stack에서 데이터를 삭제하지 않고, top에 어떤 data가 존재하는지 확인을 가능하게 한다.

public class Stack<T> {
	...
	public T peek() {
		if(isEmpty()) {
			System.out.println("Stack이 비어있습니다.");
			return null;
		}
		
		return stack[top];
	}
	
	public boolean isEmpty() {	return (this.top == -1);	}
   	...
}

pop과의 차이점은 return (T) stack[top--]; 과 return (T) stack[top]; 이다.

pop의 경우 top을 하나 감소시켜 다음 데이터가 삽입될때, 반환한 데이터 위치에 새로운 데이터가 덮어씌워지지만, peek의 경우 top의 데이터 조작을 일체 하지 않음으로써 다음 pop 혹은 push를 수행할 때 기존과 같은 역활을 하게 하는 것이다.

이제 나머지 부가기능인 stack의 크기와 초기화 하는 함수를 만들어주면 된다.

public class Stack<T> {
	...
    public void clear(){
        if(isEmpty()){
        	System.out.println("Stack은 이미 비어있습니다.");
            return;
        }
        top = -1;
        stack = (T[]) (new Object[capacity]);
        System.out.println("Stack 초기화 완료!");
    }
    
    public int size(){
    	return (top+1);
    }
}

 

---

전체코드와 실행 결과

public class mainStack {
	public static void main(String[] args) {
		System.out.println("=====짧은머리 개발자=====");
		Stack<Integer> stack = new Stack<>(5);
		for(int i = 0; i < 5; i++) {
			stack.push((i+1));
			System.out.println(i + " 번째 peek: " + stack.peek());
		}
		System.out.println("===Pop===");
		for(int i = stack.size(); i > 0; i--) {
			System.out.print(i + " 번째 : " + stack.pop() + " | " );
		}
	}
}

public class Stack<T> {
	int top;
	int capacity = -1;
	T[] stack;
	public Stack(int capacity){
		this.capacity = capacity;
		stack = (T[]) (new Object[capacity]);
		System.out.println("size : " + capacity);
		top = -1;
	}
	
	public void push(T element) {
		if(isFull()) {
			System.out.println("Stack이 가득 찼습니다.");
			return;
		}
		
		stack[++top] = element;
	}
	
	public T pop() {
		if(isEmpty()) {
			System.out.println("Stack이 비어있습니다.");
			return null;
		}
		return stack[top--];
	}
	
	public T peek() {
		if(isEmpty()) {
			System.out.println("Stack이 비어있습니다.");
			return null;
		}
		
		return stack[top];
	}
	
	public void clear(){
        if(isEmpty()){
        	System.out.println("Stack은 이미 비어있습니다.");
            return;
        }
        top = 0;
        stack = (T[]) (new Object[capacity]);
        System.out.println("Stack 초기화 완료!");
    }
	public int size(){
    	return (top+1);
    }
	
	public boolean isEmpty() {	return (this.top == -1);	}
	public boolean isFull() {	return (this.top == this.capacity-1);	}
}