LIFO, FIFO 동작 원리 이해
후입선출(LIFO : Last In First Out)
후입선출은 나중에 넣은 데이터가 먼저 빠져나가는 것을 말하며 스택이 후입선출을 사용하는 대표적인 자료구조이다.
선입선출(FIFO : First In First Out)
선입선출은 먼저 넣은 데이터가 먼저 빠져나가는 것을 말하며 큐가 선입선출을 사용하는 대표적인 자료구조이다.
Stack
스택은 후입선출을 사용하는 대표적인 자료구조로 가장 최근에 넣은 데이터가 가장 먼저 제거되는 구조를 말한다.
주요 연산
- Push : 스택의 맨 위에 데이터를 추가한다.
- Pop : 스택의 맨 위 데이터를 삭제한다.
- Peek : 스택 맨 위의 데이터를 조회한다.
- isEmpty : 스택이 비어있는지 확인한다. 비어있으면 true, 안비어있으면 false를 반환한다.
- size : 스택의 현재 개수를 반환한다.
예시 코드
Stack<String> stack = new Stack<>();
stack.push("A");
stack.push("B");
stack.push("C");
System.out.println("현재 스택 : " + stack);
System.out.println("맨 위 요소: " + stack.peek());
System.out.println("현재 크기 : " + stack.size());
String removed = stack.pop();
System.out.println("제거된 요소: " + removed);
System.out.println("현재 스택: " + stack);
System.out.println("스택이 비어있는가? " + stack.isEmpty());
// 현재 스택 : [A, B, C]
// 맨 위 요소: C
// 현재 크기 : 3
// 제거된 요소: C
// 현재 스택: [A, B]
// 스택이 비어있는가? false
Queue
큐는 선입선출을 사용하는 대표적인 자료구조로 가장 처음에에 넣은 데이터가 가장 먼저 제거되는 구조를 말한다. 자바에서는 Queue는 인터페이스로 구성되어 있기 때문에 Queue를 구현한 대표적인 클래스는 LinkedList이다.
주요연산
- offer : 큐에 데이터를 삽입한다.
- poll : 큐의 맨 첫 번째 데이터를 삭제한다.
- peek : 큐의 맨 첫 번째 데이터를 가져온다.
- isEmpty : 큐가 비어있는지 확인한다. 비어있으면 true, 안비어있으면 false를 반환한다.
- size : 큐의 현재 개수를 반환한다.
예시코드
Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");
System.out.println("현재 큐: " + queue);
System.out.println("맨 앞 요소: " + queue.peek());
System.out.println("현재 크기 : " + queue.size());
String removed = queue.poll();
System.out.println("제거된 요소: " + removed);
System.out.println("현재 큐: " + queue);
System.out.println("큐가 비어있는가? " + queue.isEmpty());
// 현재 큐: [A, B, C]
// 맨 앞 요소: A
// 현재 크기 : 3
// 제거된 요소: A
// 현재 큐: [B, C]
// 큐가 비어있는가? false
괄호 검사
괄호 검사는 백준 코딩테스트 문제를 풀어서 테스트 해보았다.
https://www.acmicpc.net/problem/9012
코드
public static String isBalanced(String s) {
String result = "NO";
Stack<Character> stack = new Stack<>();
int popCount = 0;
if (s.length() % 2 != 0) {
return result;
}
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty()) {
continue;
}
stack.pop();
popCount++;
}
}
if (stack.isEmpty() && s.length() / 2 == popCount) {
result = "YES";
}
return result;
}우선 String이 홀수일 경우 짝이 맞을 수 없기 때문에 바로 NO를 리턴해주었고, 값에 '(' 가 들어오면 push로 데이터를 추가하였고 값이 ')'이라면 Stack의 마지막 값을 불러와 쌍으로 맞는 괄호인지 확인하고 값이 맞다면 pop을 통해서 데이터를 삭제시키고, popCount를 1 증가 시킨다. 그 이후 stack이 비어있는지 확인하고, String 의 길이 / 2를 하여 popCount와 일치하는지 확인하고 맞다면 YES를 return 하게 하였다.
수식 계산
수식 계산은 프로그래머스의 문제를 가지고 테스트 하였다.
https://school.programmers.co.kr/learn/courses/30/lessons/120902
public int solution(String my_string) {
int answer = 0;
Queue<Integer> values = new LinkedList<>();
Queue<String> ops = new LinkedList<>();
String[] strList = my_string.split(" ");
for (String str : strList) {
if (isNumber(str)) {
values.offer(Integer.parseInt(str));
} else {
ops.offer(str);
}
}
answer = values.poll();
while (!values.isEmpty()) {
int num = values.poll();
String op = ops.poll();
switch (op) {
case "+":
answer += num;
break;
case "-":
answer -= num;
break;
}
}
return answer;
}
public static boolean isNumber(String s) {
try {
int num = Integer.parseInt(s);
return true;
} catch (Exception e) {
return false;
}
}우선 문자열을 공백 기준으로 배열로 만든 뒤 isNumber() 함수를 통해 숫자인지 아닌지 확인하고 그 이후 숫자라면 values에 데이터를 넣고, 연산자라면 ops에 데이터를 넣었다. 여기에서 맨 처음값들이 맨 처음으로 계산되어야 하기때문에 queue를 사용해서 연산을 진행하였다. 이후 answer에 맨 처음 값을 넣어주고 values에 데이터가 없을 때 까지 while 문을 사용하여 데이터가 없을 때 까지 연산을 진행하였다.