[선형 자료구조] 스택 (Stack)

제로베이스의 자료구조 과제 중 스택과 관련된 문제가 나와 공부하면서 내용을 정리해본다.

---

💡 스택 (Stack)

• 후입선출 (Last In First Out ; LIFO) 자료구조 : 마지막에 들어온 데이터가 먼저 나가는 구조
  실무에서 후입선출 자료구조라는 단어를 사용하지는 않고, 그냥 스택이라고 말한다.
• 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용한다.
  ex. 함수 콜 스택, 수식 계산, 수식 괄호 검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로, 인터럽트 처리 등

👉 스택 기본 구조

• 후입 선출 구조
• 기본적으로 데이터를 추가, 꺼내기, 스택 공간 확인 동작으로 이루어져있다.
  

👉 스택 기본 연산

• 데이터 저장 (Push) : 스택의 가장 마지막 위치에 데이터 저장
• 데이터 추출 (Pop) : 스택의 가장 마지막 위치에서 데이터 추출

👉 스택의 메서드

📖 처음 보는 메서드를 공부할 때는 꼭 공식 문서를 먼저 살펴보자.

메서드	설 명
boolean empty()	Stack이 비어있는지 참 or 거짓으로 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환한다. (비어있는 경우 EmptyStackException이 발생한다.)
Object pop()	Stack의 맨 위에 저장된 객체를 추출한다. (비어있는 경우 EmptyStackException이 발생한다.)
Object push(Object item)	Stack에 객체(item)을 저장한다.
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환한다. 못찾으면 -1을 반환한다. (배열과 달리 1부터 시작)

👉 스택의 구현

• 순차적으로 추가하고 삭제할 수 있는 배열로 구현하는 것이 일반적이다.

📖 수식 괄호 검사 예제

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Stack st = new Stack();
        String expression = "((3+5)*8-2)";	   // "괄호가 일치합니다."
//        String expression = "((3+5*8-2)";    // case 1 : "괄호가 일치하지 않습니다."
//        String expression = "(3+5)*8-2)";    // case 2 : "[예외 발생] 괄호가 일치하지 않습니다."

        try{
            for (int i = 0; i < expression.length(); i++) {
                char ch = expression.charAt(i);

                if(ch == '('){              // 여는 괄호는 스택에 저장
                    st.push(ch + "");
                } else if(ch == ')'){       // 닫는 괄호는 pop으로 스택에서 삭제
                    st.pop();
                }
            }

            if (st.isEmpty()) {     // 스택이 비어있으면 괄호가 맞다.
                System.out.println("괄호가 일치합니다.");
            } else {
                System.out.println("괄호가 일치하지 않습니다.");
            }
        } catch (EmptyStackException e){
            System.out.println("[예외발생] 괄호가 일치하지 않습니다.");
        }
    }
}