[자료구조] 스택 (Stack)

1010

---

1. 스택(Stack) 이란?

최근에 저장한 데이터를 먼저 사용하는 구조

스택은 상자 안에 책을 쌓는 것과 같습니다.
순서대로 책을 상자 안에 넣었다가 뺄 때 맨 마지막에 넣었던 책이 먼저 상자 밖으로 나오게되는데, 이것을 선입선출, LIFO(Last In First Out)구조라고 말합니다.

---

2. 스택의 구성 요소

스택을 구성하는 것은 다양하지만 간단히 7개가 있습니다.

• push() : 스택에 데이터를 삽입하는 작업
  • 이 때, 값은 동시에 들어갈 수 없습니다.
• pop() : 스택의 top에서 데이터를 꺼내는 작업
• overflow : limit을 벗어나면 발생
• limit : push할 수 있는 한께로 배열의 끝
• top : 데이터 상단
• base : 스택의 시작 위치로 가장 아래쪽
  • 배열 인덱스 0
• underflow : base를 벗어나면 발생
  • 배열 인덱스 -1 이하

2.1. top

이 때 top은 특히나 중요한데 이유는 top이 -1에서 시작하기 때문입니다.
다시 말해 유여데이터의 유무를 알아낼 수 있는 것이 바로 top이라는 것이죠.

만약 top이 -1이 아니라 0에서 시작했다면 어떻게 될까요?

우리가 스택에 열심히 값들을 넣었습니다.
10, 20, 30, 40을 순서대로 넣고 이제 하나씩 꺼내봅니다.
40을 뺐을 때는 top이 3,
30을 뺐을 때는 top이 2
20을 뺐을 때는 top이 1이 되겠죠.

그리고 10도 마저 빼려고 하는데 이 10이 안 빼지고 동작을 멈춥니다.
10을 뺐을 때는 top이 0이 되어 유여데이터가 없다고 컴퓨터가 판단을 하게 된 것입니다.

따라서 데이터가 아예 없다는 것을 알려주기 위해 top은 -1에서 시작하는 것입니다. 기억하세요!

---

3. 스택의 기본 동작

스택에는 크게 값을 넣는 push()와 값을 빼내는 pop()이 존재합니다.

앞서 스택은 선입선출 구조라고 했었죠.

push()를 하게 되면 현재 top의 +1의 인덱스에 값이 들어가게 됩니다.
그 뒤로도 계속 위로 차근차근히 쌓이겠죠.

값을 빼내고 싶다면 pop()을 사용합니다.
이 때 pop을 하게 되면 top에 있는 데이터가 꺼내집니다.
즉, 맨 마지막에 push()했던 값이 꺼내지게 되는 것입니다.

---

4. 스택 vs 리스트 비교

• 연결 리스트는 아이템들의 사이에 뭔가 끼워 넣을 수 있습니다.
  물리적으로 흩어져 있는 자료들을 링크를 사용하여 연결한 것이기 때문에 얼마든지 주소값을 변경하고 자료와 자료 사이에 새로운 자료를 삽입할 수 있습니다.
• 하지만 그 index에는 접근할 수 없습니다.

• 스택은 아이템들의 사이에 뭔가 끼워넣기가 어렵습니다.
  선입선출 구조이기 때문에 무조건 맨 마지막에 추가한 데이터만 가져올 수 있기 때문입니다.
  즉 0인덱스의 데이터를 가져오려면 전부 다 뽑아내야 합니다.

---

5. 배열 활용문제 풀어보기

package org.example.Stack;

import java.util.Stack;

public class Q {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("지");
        stack.push("스");
        stack.push("에");
        stack.push("엠");
        stack.push("짱");
        stack.push("왕");

        System.out.println(stack.size());// Q1
        System.out.println(stack.capacity());// Q2

        int top = ; // Q3
        while( top !=  ) {// Q4
            System.out.println(stack.());// Q5
            --;// Q6
        }
    }
}

1. 위의 실행 결과는?
2. 위의 실행 결과는?
3. top에 들어가야 할 것은?
4. 빈칸에 들어가야 할 것은?
5. 어떤 메서드가 쓰였는가?
6. 빈칸에 들어가야 할 것은?
7. 위의 전체 코드의 실행결과는?

---