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이 존재하니
실제로 알고리즘 문제를 풀때는 그걸 불러서 사용하자!
반응형