[Structure] Stack (Last In First Out)

Stack

• LIFO (Last In First Out)의 성질을 가진 자료구조
  • 나중에 들어간 데이터가 먼저나오는 구조
• 데이터의 추가/삭제는 O(1)의 시간복잡도를 갖는다 하지만, 탐색은 O(n)의 시간복잡도를 가짐
• 연결리스트로 구현이 가능하다.
• stack underflow : 비어있는 스택에서 원소를 추출하려 할때
• stack overflow : 스택이 넘치는 경우
• 사용예
  
  • 웹 브라우저 방문기록
  • 역순 문자열 만들기
  • 실행취소
• 주로 DFS(깊이 우선탐색) 에 사용된다.
• 자주사용되는 함수
  • push : 자료를 넣는것
  • pop : 자료를꺼냄 (최상단 자료를 지우고 반환한다.)
  • peek : 자료를꺼냄 (최상단 자료를 지우지않고 반환한다.)

1. Stack의 구조
2. Stack의 선언
3. Stack의 사용(연습문제)

---

1. Stack의 구조

• 위 그림과 같이 스택은 땅굴을 파놓은 모양(?)과 같다고 봐도될것같다.
• 먼저 들어간 데이터가 제일 안쪽에 있어서 제일 마지막에 나오게 되는구조이다.
• 왼쪽 코드를 보면 red, white, black, blue의 순서로 값을 담았고,
• 우측의 코드에선 pop()을 통해서 최상단 값을 꺼내는데 꺼내게 되는값은 제일 마지막에 넣은 데이터인 blue인것을 확인할 수 있다.

---

2. Stack의 선언

public class Main {
    public static void main(String[] args) {
        Stack<String> st = new Stack<>();

        st.push("red");
        st.push("blue");

        System.out.println(st.pop());
        System.out.println(st.pop());
    }
}

• 위 코드를 실행하면 실행결과는 blue red 이다.
• 먼저 들어간 red가 나중에 나오고 나중에 들어간 blue 가 먼저 출력되어지는것이다.
• 그럼 지금 위 코드에서 Stack엔 어떤 데이터가 남아있을까?
• 두 데이터를 모두 pop해줬기때문에 Stack은 비어있는 상태이다.

public class Main {
    public static void main(String[] args) {
        Stack<String> st = new Stack<>();

        st.push("red");
        st.push("blue");

        System.out.println(st.peek());
        System.out.println(st.peek());
    }
}

• 위 코드의 실행결과는 blue blue이다.
• 이유는 값은 red blue 순서로 넣었지만 나중에 넣은 blue가 먼저 출력되는것이고, pop이 아닌 peek를 해줬기에 값을 꺼내서 출력은 하였지만 지우진 않은것이다.
• 위와같은 성질을 이용하여 알고리즘 문제를 해결할수도 서비스에 적용할수도 있는것이다.

---

3. Stack의 사용 (연습문제)

아래의 두 문제를 보고 사용하는법을 익혀보자.

1. https://do-hyeon.tistory.com/216?category=943920 

[LeetCode] 20. Valid Parentheses

2. https://do-hyeon.tistory.com/217?category=943920 

[LeetCode] 71. Simplify Path