[Algorithm] 자바로 스택(Stack) 구현

스택이란?

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다.

스택의 최상단에 데이터를 추가(push) 하고 최상단의 데이터만 꺼낼(pop) 수 있다.

스택의 활용 예시

• 웹 브라우저의 방문 기록: 가장 최근에 열린 페이지 부터 보여줌
• 실행취소(ctrl+z): 가장 최근에 실행된 것부터 취소됨
• 역순 문자열 만들기

 

스택 구현

 

1. 클래스 선언 및 매개변수, 생성자 생성

public class Stack<T> { //제너레이트 하여 데이터 타입 설정
	
	private T[] stk; //데이터를 저장할 배열
	private int len; //스택의 현재 크기
	private int max; //스택의 최대 크기(사용안할시 -1 로 초기화)
	
	public Stack(int max) { //최대 크기를 설정
		this.len = 0;
		this.stk = (T[])new Object[max]; //배열의 길이를 max 로 설정
		if(max < 1) // 할당된 매개변수가 1보다 작을 시 최대크기를 1 로 변경
			max = 1;
		this.max = max;
	}
	
	public Stack() { // 최대 크기 설정x
		this.len = 0;
		this.stk = (T[])new Object[len];//배열의 길이를 현재길이(len)으로 설정
		this.max = -1;
	}

1) 먼저 클래스를 생성하고 제너레이트 하여 데이터 타입 설정

2) 스택 구현에 필요한 멤버변수 생성

   stk: 데이터를 저장할 배열

   len: 스택의 현재 크기

   max: 스택의 최대 크기

3) 생성자를 생성하며 각각의 멤버변수 초기화(최대 크기를 설정할 시 max값 매개변수로 받음)

 

 

2. 스택에 데이터를 추가

	public boolean push(T el) { // 데이터를 추가
        if(max == len && max > -1) {
			System.out.println("데이터 범위 초과");
			return false;
		}
		
		len += 1;//길이 추가
		
		if(max == -1) { // 최대 길이를 설정하지 않은 경우
			T [] temp = stk;//스택 정보를 저장할 임시 배열 생성 
			stk = (T[])new Object[len];//배열의 길이를 추가하여 초기화
			for(int i=0; i<temp.length; i++) //이전의 데이터를 현재 배열로 이동 
				stk[i] = (T)temp[i];
		}
		stk[len-1] = el;//추가할 데이터 최상단에 추가
		return true;
	}

스택의 데이터가 저장된 배열의 크기를 늘리고 추가할 데이터 최상단에 추가

 

3. 스택의 데이터를 제거

	public boolean pop() { // 맨 위의 데이터를 제거
		if(len == 0) {
			System.out.println("제거할 데이터가 없습니다.");
			return false;
		}
		len -= 1;
		T [] temp = stk;
		stk = (T[])new Object[len]; 
		
		for(int i=0; i<stk.length; i++)
			stk[i] = (T)temp[i]; 
		
		return true;
        
        
        if(len == 0) { //데이터가 존재하지 않는 경우
			System.out.println("제거할 데이터가 없습니다.");
			return false;
		}
		len -= 1; // 데이터 길이를 1만큼 감소
		if(max == -1) { //최대 길이를 설정하지 않았을 경우
			T [] temp = stk; // 이전 데이터를 임시 배열에 이동
			stk = (T[])new Object[len];//배열을 감소된 길이로 초기화
			for(int i=0; i<stk.length; i++)//데이터를 초기화한 배열에 추가.  
				stk[i] = (T)temp[i];//감소된 길이만큼 반복하므로 최상단의 데이터는 제거됨
		}else {
			stk[len] = null; //최대 길이를 설정했을 경우 추출할 위치의 데이터를 null로 설정
		}
		return true;
	}

스텍의 데이터가 저장된 배열의 크기를 줄이고 최상단의 데이터를 제거

 

 

4. 최상단의 데이터를 반환

	public Object get() { // 맨위의 데이터를 반환
		if(len == 0) {
			System.out.println("반환할 데이터가 없습니다.");
			return false;
		}
		return stk[len-1];
	}

데이터가 저장된 배열의 최상단의 데이터를 반환

 

 

5. 스택의 크기를 반환

	public int getLen() { // 스택의 크기를 반환
		return len;
	}

 

 

6. 현재 스택이 비어있는 상태인지 확인

	public boolean isEmpty() { // stack이 비어있을 시 false 아닐시 true 반환
		if(len == 0)
			return false;
		
		return true;
	}

 

 

7. 현재 스택에 저장되어 있는 데이터들을 모두 출력

	public void printAllData() { //stack의 모든 데이터를 상단에서부터 출력
		for(int i = len-1; i>=0; i--) {
			System.out.println("================");
			System.out.println((i+1) + ": " + stk[i]);
		}
	}

현재 저장되어 있는 데이터들을 상단에서부터 출력

 

 

8. 스택 초기화

	public void clear() { //stack 초기화
		this.len = 0;
		if(this.max == -1) //최대 길이를 설정하지 않았을 경우에만
			this.stk = (T[])new Object[len];//배열의 길이를 0으로 설정
		else
        		this.stk = (T[])new Object[max];
	}

 

 

전체 코드

public class Stack<T> { //제너레이트 하여 데이터 타입 설정
	
	private T[] stk; //데이터를 저장할 배열
	private int len; //스택의 현재 크기
	private int max; //스택의 최대 크기(사용안할시 -1 로 초기화)
	
	public Stack(int max) { //최대 크기를 설정
		this.len = 0;
		this.stk = (T[])new Object[max];
		if(max < 1) // 할당된 매개변수가 1보다 작을 시 최대크기를 1 로 변경
			max = 1;
		this.max = max;
	}
	
	public Stack() { // 최대 크기 설정x
		this.len = 0;
		this.stk = (T[])new Object[len];
		this.max = -1;
	}
	
	public boolean push(T el) { // 데이터를 추가
		if(max == len && max > -1) {
			System.out.println("데이터 범위 초과");
			return false;
		}
		
		len += 1;
		
		if(max == -1) {
			T [] temp = stk;
			stk = (T[])new Object[len];
			for(int i=0; i<temp.length; i++) 
				stk[i] = (T)temp[i];
		}
		stk[len-1] = el;
		return true;
	}
	
	public boolean pop() { // 맨 위의 데이터를 제거
		if(len == 0) {
			System.out.println("제거할 데이터가 없습니다.");
			return false;
		}
		len -= 1;
		if(max == -1) {
			T [] temp = stk;
			stk = (T[])new Object[len];
			for(int i=0; i<stk.length; i++)
				stk[i] = (T)temp[i];
		}else {
			stk[len] = null;
		}
		return true;
	}
	public Object get() { // 맨위의 데이터를 반환
		if(len == 0) {
			System.out.println("반환할 데이터가 없습니다.");
			return false;
		}
		return stk[len-1];
	}
	
	public int getLen() { // 스택의 크기를 반환
		return len;
	}
	
	public boolean isEmpty() { // stack이 비어있을 시 false 아닐시 true 반환
		if(len == 0)
			return false;
		
		return true;
	}
	
	public void printAllData() { //stack의 모든 데이터를 상단에서부터 출력
		for(int i = len-1; i>=0; i--) {
			System.out.println("================");
			System.out.println((i+1) + ": " + stk[i]);
		}
	}
	
	public void clear() { //stack 초기화
		this.len = 0;
		if(this.max == -1) 
			this.stk = (T[])new Object[len];
        	else
        	this.stk = (T[])new Object[max];
		
	}
	
}