[이코테 with Java] 자료구조와 스택

■ 탐색

---

탐색(search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 

대표적인 탐색 알고리즘으로는 DFS와 BFS를 꼽을 수 있다.

DFS, BFS를 이해하기 위해서는 "스택"과 "큐"를 이해해야 한다.

 

■ 자료구조

---

자료구조(Data Structure)란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 

그중 스택과 큐는 자료 구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다.

• 삽입(Push): 데이터를 삽입한다.
• 삭제(Pop): 데이터를 삭제한다. 

실제로 스택과 큐를 사용할 때는 "오버플로"와 "언더플로"를 고민해야 한다.

• 오버플로: 데이터의 크기가 가득 찬 상태에서 삽입 연산을 수행할 때 발생(저장 공간을 벗어나 데이터가 넘쳐흐를 때)
• 언더플로: 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산 수행할 때 발생

 

■ 스택

---

스택(Stack)은 박스 쌓기에 비유할 수 있다.  우리가 박스를 쌓을 때는 "아래에서부터 위로" 쌓는다.

아래에 있는 박스를 빼고 싶으면 어떻게 해야 할까?

위에 있는 박스를 뺀 다음, 아래에 있는 박스를 빼야 한다.

이런 구조를 "선입후출(First In Last Out)" 구조 또는 "후입선출(Last In First Out)" 구조라고 한다. 

 

 

■ 코드

 

import java.util.*;

public class Main {
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>();
        Stack<Integer> reverseStack = new Stack<>();
        // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
        s.push(5);
        s.push(2);
        s.push(3);
        s.push(7);
        s.pop();
        s.push(1);
        s.push(4);
        s.pop();
        // 스택의 최상단 원소부터 출력
        while(!s.empty()){
            System.out.println(s.peek());
            reverseStack.push(s.peek());
            s.pop();
        }
        while(!reverseStack.empty()){
            System.out.println(reverseStack.pop());
        }
        
    }
}

 

원래 이코테에는 최상단 원소부터 출력하는 함수만 구현되어 있지만,

나중에 역순으로 출력하는 경우도 필요할 것 같아 reverseStack이라는 Stack도 선언해주었다.

 

※ 기본 Stack

1. 초기 단계 - 박스가 없음

2. 삽입(5)  - (5)

3. 삽입(2) - (5, 2)

4. 삽입(3) - (5, 2, 3)

5. 삽입(7) - (5, 2, 3, 7)

6. 삭제() - (5, 2, 3) => 가장 최근에 들어온 수(7)부터 빼야 한다.

7. 삽입(1) - (5, 2, 3, 1) 

8. 삽입(4) - (5, 2, 3, 1, 4)

9. 삭제() - (5, 2, 3, 1) => 가장 최근에 들어온 수(4)부터 빼야 한다. 

--> 출력은 1, 3, 2, 5

 

※ 역순 Stack

1. 초기 단계 - 박스가 없음

2. 삽입(1) - (1) => 가장 최근에 들어온 함수 먼저 빠지므로, (5, 2, 3, 1)의 1부터 저장된다.

3. 삽입(3) - (1, 3)

4. 삽입(2) - (1, 3, 2)

5. 삽입(5) - (1, 3, 2, 5)

--> 출력은 5, 2, 3, 1