[기초 자료구조] Stack

1. Stack 이란?

• LIFO 방식으로 데이터를 저장하는 자료구조 입니다.

 

LIFO

• Last-In, First Out
• 가장 나중에 들어온 데이터가 가장 먼저 나가는 방식을 의미합니다.

 

2. 연산

push	맨 위에 항목을 추가합니다.	O(1)
pop	맨 위에 항목을 반환하고 제거합니다.	O(1)
peek	맨 위에 항목을 반환합니다.	O(1)

 

 

3. 사용 사례

Undo / Redo	애플리케이션 사용중, 최근 수행한 명령을 취소 / 취소한 명령을 다시 실행 하는 기능으로 사용합니다.
call stack	운영체제에서 프로그램의 함수 호출을 관리하기 위해 사용합니다.
괄호 짝 맞추기	수식의 괄호가 문법에 맞게 작성되었는지 확인하는데 사용합니다.
문자열 역순으로 변환하기	문자열을 역순으로 바꾸는데 사용합니다.
후위 표기법으로 변환하기	수식을 후위 표기법으로 변환하는데 사용합니다.

 

4. Exception

Stack Overflow

• Stack에 할당된 메모리 용량이 초과된 상황에서 요소를 추가하려 할 때 발생하는 오류

 

사례

• 재귀함수 : 스레드가 재귀함수를 호출할 때, 깊이가 너무 깊어져 스택 메모리의 용량을 초과합니다.

 

Stack Underflow

• Stack에 할당된 요소가 없는 상황에서 요소를 제거하려 할 때 발생하는 예외

 

5. 구현

기본

public class MyStack<T> {
    final T[] arr;
    final int size;
    int top;

    public MyStack(int size) {
        this.arr = (T[]) new Object[size];
        this.size = size;
        this.top = -1;
    }

    public void push(T item) {
        fullCheck();

        arr[++top] = item;
    }

    public T pop() {
        emptyCheck();

        return arr[top--];
    }

    public T peek() {
        return arr[top];
    }

    private void emptyCheck() {
        if (top == -1) throw new IllegalStateException("empty");
    }

    private void fullCheck() {
        if (top == size-1) throw new IllegalStateException("full");
    }
}

 

후위표현식

• 연산자가 피연산자 뒤에 오는 표기 방식
• 괄호 X

 

계산 순서

• 왼쪽에서 오른쪽으로 읽기
• 연산자를 만나면 바로 앞의 두 피연산자에 대해 연산 수행

 

연산자 우선순위

• 후위 표현식에서는 연산자의 위치로 우선순위를 표현함
• 우선순위가 높은 연산자일 수록 더 안쪽에 위치함 (더 먼저 수행되어야 하기 때문)

 

 

StringBuilder sb = new StringBuilder();
Map<Character, Integer> precedence = new HashMap<>();
precedence.put('+', 1);
precedence.put('-', 1);
precedence.put('*', 2);
precedence.put('/', 2);

for (char ch : expArr) {
    if (Character.isLetter(ch)) {
    	sb.append(ch);
    } else if (ch == '(') {
    	stack.push(ch);
    } else if (ch == ')') {
    	while (!stack.isEmpty() && stack.peek() != '(') sb.append(stack.pop());
    
    	stack.pop();
    } else {
    	while (!stack.isEmpty() && stack.peek() != '(' && precedence.get(ch) <= precedence.get(stack.peek())) sb.append(stack.pop());
        
        stack.push(ch);
    }
}

while (!stack.isEmpty()) sb.append(stack.pop());

System.out.print(sb);

 

연산자는 우선순위, 먼저온 순서 순으로 안쪽으로 배치되어야 함

 

현재 연산자 우선순위가 스택 top의 연산자 우선순위보다 높으면

• 스택에 현재 연산자를 push함

 

현재 연산자 우선순위가 스택 top의 연산자 우선순위보다 낮거나 같으면

• 정답 문자열에 스택 연산자를 push함 (반복)
• 우선순위가 높은 연산자가 먼저 배치되어야 하기 때문

 

 

출처

• Wiki - Stack
• Wiki - Stack (eng)