📚 Stack
대표적인 LIFO(Last In First Out) 자료구조.
한 쪽만 뚫린 상자를 생각하면 편한데, 그러면 먼저 넣은 것은 나중에 나올 수밖에 없기 때문이다.
Queue처럼 신경써야 할 게 따로 있지도 않고, 여기저기 요긴하게 쓰이는 녀석이다.
🎲 Functions
- push : 스택에 요소를 집어넣는다.
- pop : 스택 가장 위 요소를 반환하고 해당 요소를 스택에서 제거한다.
- isEmpty & isFull : 비었는지, 꽉 찼는지 판단한다.
- peek : pop과 비슷하지만 요소를 제거하지 않는다.
💻 Implementation
Array Implementation
배열에 top을 나타내는 index를 활용해서 구현할 수 있다.
class ArrayStack {
private int top;
private int size;
private int[] arr;
public ArrayStack(int n) {
size = n;
top = -1;
arr = new int[n];
}
public void push(int n) {
if (isFull()) return;
arr[++top] = n;
}
public int pop() {
if (isEmpty()) return -1;
return (arr[top--]);
}
public boolean isFull() {
return (top == size-1);
}
public boolean isEmpty() {
return (top == -1);
}
}
Linked List Implementation
역시 간단 !
class LLStack<T> {
private LinkedList<T> l;
public LLStack() {
l = new LinkedList<T>();
}
public void push(T x) {
l.insertAtFront(x);
}
public T pop() {
if (isEmpty()) return null;
return (l.deleteAtFront());
}
public T peek() {
return (l.getIter().getValue());
}
public boolean isEmpty() {
return (l.isEmpty());
}
}⌛️ Time Complexity
- push : O(1).
Array의 경우 인덱싱이고, Linked List는 insertAtFront이니 O(1) - pop : O(1)
역시 마찬가지. - peek : O(1).
순회가 필요없다. - isFull & isEmpty : O(1)
당연하다. Array의 경우 단순 비교, LinkedList의 경우에도 first == null 검사만 진행하기 때문.
😵💫 Famous Problems
Infix to Postfix
Infix는 우리가 흔히 알고 있는 수식 전개 방식이다.
반면 PostFix는 연산자를 항의 제일 뒤에 넣는 방식.
Postfix의 장점은 연산자 우선순위를 걱정할 필요 없이 항이 나오는 순서대로 계산을 하면 된다는 점인데, Stack을 이용한 문제 중 유명한 게 Infix에서 Postfix로 식을 바꾸는 방법이다.
간단하게 생각하면 우선 연산자가 항의 가장 뒤에 나와야 하므로 해당 부분에서 스택이 사용될 것이라 생각할 수 있다. 다만 infix에서는 연산자 우선순위가 존재하므로 이를 고려해서 진행해야 한다.
연산자 우선순위 해결 : A+B+C*D
위 식에서 연산자 우선순위를 해결해보자.
스택을 다음처럼 정의하자.
우선 알파벳을 만나게 된다면 그대로 출력한다.
A를 만났을 때
output : A
Stack : []
+ 를 만났을 때
이제부터 본격적으로 문제인데, 우선 연산자는 지금 나오면 안된다. 그러니 일단 스택에 넣어주자.
output : A
Stack : [+]
B를 만났을 때
output : AB
Stack : [+]
+를 만났을 때
이제 +가 하나 나와야 함은 자명한데, 지금 마주친 +를 바로 출력하는 건 아니다.
그래서 우선 +를 출력해주고, 지금 만난 +는 스택에 넣어보자.
output : AB+
Stack : [+]
C를 만났을 때
output : AB+C
Stack : [+]
*를 만났을 때
드디어 곱하기가 나왔는데, 곱하기는 D 바로 뒤에 넣어야 한다.
Stack에 이미 +가 하나 있지만, +가 지금 나오면 안 된다.
그러니 *를 일단 스택에 넣어준다.
output : AB+C
Stack : [+, *]
D를 만났을 때
output : AB+CD
Stack : [+,*]
이제 문자열이 끝났으니, Stack의 모든 것을 출력해주면 된다.
output : AB+CD*+
패턴
*가 나왔을 때 왜 아무것도 하지 않고 바로 스택에 넣어야 했을까?
Infix의 연산자 우선순위를 생각해보면 알 수 있다.
postfix에서는 연산자 우선순위가 높으면 앞에 나오게 된다. 그 말은 한 연산자가 있을 때, 그보다 우선순위가 높은 걸 먼저 출력해야 한다는 말이다. 낮은 걸 출력하면 AB+CD+* 식으로 되었을 테니 틀린 식이 된다.
그리고 우선순위가 같다면 바로 출력해줘야 한다. AB+를 생각해보면 알 수 있다.
결과적으로, "연산자를 만나면 해당 연산자보다 우선순위가 같거나 높은 연산자를 모두 출력 후 해당 연산자를 스택에 넣는다" 로 정리할 수 있다.
Implementation
class IntoPost {
public static void main(String[] args) {
LLStack<Character> s = new LLStack<Character>();
String str = "A+B+C*D";
char tmp;
// 문자열 전체 순회
for (int i=0;i<str.length();i++) {
tmp = str.charAt(i);
if (isOper(tmp)) { // 연산자라면
while (!s.isEmpty() && isPrimary(tmp, s.peek()) == true)
// 스택이 비지 않고, 현재 연산자보다 우선순위가 같거나 높은 요소 모두 pop
System.out.print(s.pop());
// 그 후 현재 연산자 push
s.push(tmp);
} else //연산자가 아니라면 바로 출력
System.out.print(tmp);
}
// 순회 이후 스택 비우기
while (!s.isEmpty())
System.out.print(s.pop());
System.out.println();
}
public static boolean isOper(char c) {
return (c=='+' || c=='-' || c=='*' || c=='/');
}
public static boolean isPrimary(char cur, char comp) {
if (cur == '*' || cur == '/')
if (comp == '*' || comp == '/')
return true;
if (cur == '+' || cur == '-')
if (comp == '+' || comp == '-')
return true;
return false;
}
}괄호까지 고려해야 한다면?
크게 달라지는 건 없고, 여는 괄호를 만나면 그냥 push, 닫는 괄호를 만나면 넣어둔 여는 괄호가 나올 때까지 모든 연산자를 Pop해주면 된다. 우선순위가 최우선이니까 가능한 것!
class IntoPost {
public static void main(String[] args) {
LLStack<Character> s = new LLStack<Character>();
String str = "(A+B+C)*D";
char tmp;
for (int i=0;i<str.length();i++) {
tmp = str.charAt(i);
if (isOper(tmp)) {
while (!s.isEmpty() && isPrimary(tmp, s.peek()) == true)
System.out.print(s.pop());
s.push(tmp);
} else if (tmp == '(')
s.push(tmp);
else if (tmp == ')') {
while (!s.isEmpty() && s.peek() != '(')
System.out.print(s.pop());
s.pop();
}
else
System.out.print(tmp);
}
while (!s.isEmpty())
System.out.print(s.pop());
System.out.println();
}
public static boolean isOper(char c) {
return (c=='+' || c=='-' || c=='*' || c=='/');
}
public static boolean isPrimary(char cur, char comp) {
if (cur == '*' || cur == '/')
if (comp == '*' || comp == '/')
return true;
if (cur == '+' || cur == '-')
if (comp == '+' || comp == '-')
return true;
return false;
}
}Postfix to Infix
이번에는 반대로 Postfix를 infix로 바꿔볼 수 있다.
훨씬 쉬운데, 이는 postfix가 그냥 순서대로 계산하면 되기 때문.
우선순위가 이미 지켜져 있는 상황이기 때문에 괄호만 감싸주면 Infix로 잘 바뀐다.
AB+가 있다면 AB 모두 스택에 넣고, 연산자를 만나는 순간 두 항을 pop해서 이어주고 스택에 다시 넣어주면 된다.
AB+C+
AB+C+로 예시를 들어보자.
A
Stack : [A]
B
Stack : [A, B]
+
B, A 순서대로 pop해서 괄호와 연산자를 이어붙이고 다시 Stack에 push한다.
Stack : [(A+B)]
C
Stack : [(A+B), C]
+
Stack : [((A+B)+C)]
Implementation
class PostToIn {
public static void main(String[] args) {
LLStack<String> s = new LLStack<String>();
String str = "AB+C+";
String s1, s2;
for (int i=0;i<str.length();i++) {
char tmp = str.charAt(i);
if (isOper(tmp)) {
s2 = s.pop();
s1 = s.pop();
s.push("(" + s1 + String.valueOf(tmp) + s2 + ")");
} else
s.push(String.valueOf(tmp));
}
System.out.println(s.pop());
}
public static boolean isOper(char c) {
return (c == '-' || c=='+' || c=='*' || c=='/');
}
}코드가 비교적 훨씬 간단하다.
아 그리고, 자바의 경우 String + String 연산의 복잡도가 언뜻 보면 O(n)일 것 같지만 실제로는 O(n^2)이다. 끝에 붙이는 개념이 아니라 아예 새로운 문자열을 만들기 때문.
따라서 시간이 널널하지 않은 경우에는 다른 방법을 고안해야 한다. char LinkedList를 구현하던가 Stringbuilder를 이용하던가.
