Stack

Stack

• 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO(후입선출), Last In First Out)을 가진 자료 구조이다.

• [JVM 함수 호출 스택, Stack Overflow 에러] 에서의 스택

JVM

public class JvmStack {

    public static void main(String[] args) {
        JvmStack jvmStack = new JvmStack();
        jvmStack.add();
    }

    public void add(){
        minus();
        mul();
    }

    public void minus(){
        System.out.println("minus");
    }
    public void mul(){
        System.out.println("mul");
    }
}

특징

• 배열과 달리 index 같은 위치 값으로 접근할 수가 없다.
  검색시. 제일 상위 값부터 검색해야 하므로 O(1)~O(n) 의 시간이 걸린다.
• 데이터 추가 및 삭제는 O(1)
  배열처럼 원소들을 하나씩 밀어줄 필요가 없다.
• 한 쪽 끝에서만 자료를 넣고 뺄 수 있다.
• Stack이 List도 상속받고 있어 List의 메소드도 사용가능하다.

기본연산

• pop() : 스택에서 가장 위에 있는 항목을 제거한다.
• push(item) : item 하나를 스택의 가장 윗 부분에 추가한다.
• peek() : 스택의 가장 위에 있는 항목을 반환(조회)한다. pop 메소드와는 달리 스택에서 제거하지는 않는다.
• isEmpty() : 스택이 비어 있을 때에 true를 반환한다.
• clear() : 스택에 존재하는 모든 자료들을 삭제한다.

push와 pop할 때는 해당 위치를 알고 있어야 하므로 기억하고 있는 ‘스택 포인터(SP)’가 필요하다.

스택 포인터는 다음 값이 들어갈 위치를 가리키고 있다. (처음 기본값은 -1)

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

push()

item 하나를 스택의 가장 윗 부분에 추가

pop()

스택에서 가장 위에 있는 항목을 제거

peek()

스택의 가장 위에 있는 항목을 반환

isEmpty()

스택이 비어 있을 때에 true를 반환

isFull()

스택이 꽉차 있을 때 true를 반환

코드

class Stack{
	private int sp;
	private int stackSize;
	private char stackArr[];

	// 스택이 비어있는 상태인지 확인
	// 스택 포인터가 -1인 경우 데이터가 없는 상태이므로 true 아닌 경우 false를 return
	public boolean isEmpty(){
		return sp == -1;
	}

	// 스택이 가득찬 상태인지 확인
	// 스택 포인터가 스택의 마지막 인덱스와 동일한 경우 true 아닌 경우 false를 return
	public boolean isFull(){
		return sp == this.stackSize -1;
	}

	// 스택에 데이터를 추가
	public void push (char item){
		if(isFull()){
			System.out.println("Stack is full!");
		}
		else{
			stackArr[++sp] = item; // sp 값이 먼저 증가된 후에 해당 코드 실행
			System.out.println("입력된 문자 : " + item);
		}
	}

	// 스택의 최상위(마지막) 데이터 추출 후 삭제
	public char pop(){
		if (isEmpty()) {
			System.out.println("Deleting fail! Stack is empty!");
			return 0;
		} else {
			System.out.println("삭제된 문자 : " + stackArr[sp]);
			return stackArr[sp--]; // 해당 코드가 실행 된 후 sp 값 감소
		}
	}

	// 스택의 최상위(마지막) 데이터 추출
	public char peek(){
		if (isEmpty()){
			System.out.println("Peeking fail! Stack is empty!");
			return 0;
		}
		else {
			System.out.println("최상위 문자 조회 : " + stackArr[sp]);
			return stackArr[sp];
		}
	}

	// 스택 초기화
	public void clear(){
		if (isEmpty()){
			System.out.println("Stack is already empty!");
		} else {
			sp = -1; // 스택 포인터 초기화
			stackArr = new char[this.stackSize]; // 새로운 스택 배열 생성
			System.out.println("Stack is clear!");
		}
	}

	// 스택을 생성하는 생성자
	public Stack(int stackSize){
		sp = -1; // 스택 포인터 초기화
		this.stackSize = stackSize; // 스택 사이즈 설정
		stackArr = new char[this.stackSize]; // 스택 배열 생성
	}

	// 스택에 저장된 모든 데이터를 출력
	public void printStack(){
		if (isEmpty()) {
			System.out.println("Stack is empty!");
		} else {
			System.out.print("Stack elements : ");
			for (int i =0; i<=sp; i++) {
				System.out.print(stackArr[i] + " ");
			}
			System.out.println();
		}
	}

}

public class StackTest {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in); // 사용자로부터 키 입력을 받기 위해서는 System.in을 사용한다.
		System.out.print("스택 사이즈를 입력하세요. :  ");
		int stackSize = scanner.nextInt(); // int nextInt() : 입력받은 값을 int 타입으로 반환

		Stack stack = new Stack(stackSize);

		stack.push('A');
		stack.printStack();

		stack.push('B');
		stack.printStack();

		stack.push('C');
		stack.printStack();

		stack.pop();
		stack.printStack();

		stack.peek();
		stack.printStack();

		stack.clear();
		stack.printStack();
	}
}

// https://velog.io/@kungsboy/%EC%88%99%EC%A0%9C-Stack-%EA%B5%AC%ED%98%84

동작 배열 스택

스택에는 MAX_SIZE라는 최대 크기가 존재해야 한다.

→ 스택 포인터와 MAX_SIZE를 비교해서 isFull 메소드로 비교해야되기 때문이다.

최대 크기가 없는 스택을 만드려면?

arraycopy를 활용한 동적배열 사용한다.(스택이 최대가 되면 스택 크기를 2배로 늘리는 방법이다.)

활용

• 재귀 알고리즘
  • 재귀적으로 함수를 호출해야하는 경우 임시 데이터를 스택에 넣어준다.
  • 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
  • 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
  • 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
• 웹 브라우저 방문기록(뒤로가기)
• 실행 취소
• 역순 문자열 만들기
• 수식의 괄호 검사
• 후위 표기법 계산