Knowledge/Data Structure

스택에 대해 알아보자

TakeKnowledge 2019. 9. 4. 22:25
반응형

- 스택이란?

 

한쪽 끝 ( 가장 위 - Top )에서만 자료를 넣고 뺄 수 있는 자료구조.

마지막으로 넣은 것이 가장 먼저 나오기 때문에 LIFO ( Last In First Out ) 라고도 한다.

 

- 주로 사용하는 메소드

 

push: 스택에 자료를 넣는 연산
pop : 스택에서 자료를 빼는 연산
peek: 스택의 가장 위에 있는 자료를 보는 연산
empty: 스택이 비어있는지 아닌지를 알아보는 연산
size: 스택에 저장되어있는 자료의 개수를 알아보는 연산

 

- 구현

 

정확한 구현이 아닌

백준 10828번 스택 문제 ( https://www.acmicpc.net/problem/10828 ) 의 조건

 

  • push X: 정수 X를 스택에 넣는 연산이다.
  • pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 스택에 들어있는 정수의 개수를 출력한다.
  • empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
  • top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

에 맞게 구현한 것임을 미리 알립니다

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Main {
 
    ArrayList<Integer> stack = new ArrayList<>();
 
    void push(int x) {
        stack.add(x);
    }
 
    void pop() {
        if (stack.size() == 0) {
            System.out.println(-1);
        } else {
            this.top();
            stack.remove(stack.size() - 1);
        }
    }
 
    void size() {
        System.out.println(stack.size());
    }
 
    void empty() {
        if (stack.size() == 0) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
 
    void top() {
 
        if (stack.size() == 0) {
            System.out.println(-1);
        } else {
            System.out.println(stack.get(stack.size() - 1));
        }
    }
 
    public static void main(String[] args) {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = "";
        Main stack = new Main();
 
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
 
        int count = Integer.parseInt(s);
 
        for (int i = 0; i < count; i++) {
            try {
                s = br.readLine();
 
                if (s.startsWith("push")) {
 
                    String[] push = s.split(" ");
                    stack.push(Integer.parseInt(push[1]));
 
                } else {
 
                    if (s.equals("top")) {
                        stack.top();
                    } else if (s.equals("size")) {
                        stack.size();
                    } else if (s.equals("pop")) {
                        stack.pop();
                    } else if (s.equals("empty")) {
                        stack.empty();
                    }
 
                }
 
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
 
    }
 
}

 

- 라이브러리 활용

 

굳이 이렇게 직접 구현하지 않아도 된다.

한두번은 이 자료구조를 이해하기 위해 구현해도 좋겠으나

java.util 패키지안에 이미 잘 구현된 Stack이 존재하니

실제로 알고리즘 문제를 풀때는 그걸 불러서 사용하자!

반응형