참고
Stack
NOTE
Stack ⇒ LIFO (Last In, First Out) 원칙에 기반한 선형 자료구조!
push, pop을 통해 데이터를 넣고 뺀다.
Stack의 사용 사례
NOTE
•
Undo / Redo
// 사용자가 A, B, C 순으로 작업을 수행했다고 가정해봅시다.
Undo 스택: [A, B, C], Redo 스택: []
// 사용자가 Undo를 클릭하면 C 작업이 Undo 스택에서 제거되고
// Redo 스택에 추가됩니다.
Undo 스택: [A, B], Redo 스택: [C]
// 이제 사용자가 Redo를 클릭하면 C 작업이 Redo 스택에서 제거되고
// Undo 스택에 다시 추가됩니다.
Undo 스택: [A, B, C], Redo 스택: []
Java
복사
2개의 스택을 활용한 Undo, Redo
•
백스페이스
◦
키보드 입력을 하다가 백스페이스(←) 키를 누르면 최근에 입력한 글자를 지운다.
•
최근 작업 순서로 되돌아가기
◦
한글, 워드, 파워포인트 등 편집기는 최근에 한 작업 순서로 취소하는 기능이 있다.
◦
ctrl + z
•
프로그램의 함수 호출을 관리
◦
컴퓨터의 운영체제는 함수 호출을 관리하기 위해 스택을 사용한다.
◦
이를 호출 스택(Call Stack)이라 하며, 함수 호출과 반환을 효율적으로 관리한다.
Stack Overflow / Underflow
NOTE
스택 자료구조에서 일반적으로 발생할 수 있는 2가지 오류상황!
•
스택 오버플로우(Stack Overflow)
◦
스택이 꽉차 있을 때, push 연산을 수행하려고 시도하면 발생
•
스택 언더플로우(Stack Underflow)
◦
스택이 비어 있을 때, pop 연산을 수행하려고 시도하면 발생
Stack Overflow / Underflow가 시스템에 끼치는 영향
NOTE
•
스프링부트 애플리케이션
◦
내부적으로 여러 스레드를 사용해서 작업을 처리한다.
◦
웹 어플리케이션의 경우 HTTP 요청을 처리하기 위한 쓰레드, DB연결을 관리하는 쓰레드, 스케쥴링된 작업을 실행하는 쓰레드 등 많은 쓰레드가 존재한다.
◦
이때 Stack OVerflow는 Thread 별로 할당된 스택 메모리 영역에서 발생하는데, 주로 재귀함수 호출이 너무 깊게 들어가거나, 스택 프레임의 크키가 너무 커져서 스택 메모리 한계를 초과할때 발생한다.
•
스프링 부트 애플리케이션에서 메인 스레드에서 Stack Overflow가 발생
◦
메인 스레드에서 에러가 발생하면, 전체가 시작되지 않거나 중단될 수 있다.
◦
하지만 이러한 경우는 흔하지 않으며, 대부분 웹 요청 처리나 비즈니스 로직 수행중에 발생한다.
◦
웹 요청 처리나 비즈니스 로직 수행 중에 발생하는 경우, 해당 쓰레드만 종료되고, 다른 쓰레드는 영향을 받지 않는다.
Stack Overflow / Underflow 방지하는 방법
NOTE
•
재귀 함수 제한
◦
재귀 함수는 스택 오버플로우의 주요 원인 중 하나이다.
◦
재귀 함수의 깊이를 제한하거나, 필요한 경우 반복문을 사용하여 재귀 대신 반복작업을 수행하도록 한다.
•
예외 처리
◦
예외가 발생할 수 있는 경우에 적절한 대응을 하도록 한다.
◦
ex) pop 연산을 수행하기전 isEmpty 수행
Stack 구현 (Array / Linked List)
Array를 활용한 Stack 구현
NOTE
시간 복잡도
•
Push : , 리사이징이 필요한 경우
•
Pop :
•
Peek :
•
Size :
Linked List를 통한 Stack 구현
NOTE
시간 복잡도
•
Push : , 리사이징이 필요한 경우
•
Pop :
•
Peek :
•
Size : (구현에 따라서 이 될 수도 있습니다.)
참고
중위 표현식 (Infix Notation)을 후위 표현식 (Reverse Polish Notation, RPN)으로 변환하는 알고리즘
NOTE
a + b
c - d
e * f
g / h
(a + b) * c
Java
복사
중위 표현식 예제
a b +
c d -
e f *
g h /
a b + c *
Java
복사
후위 표현식 예제
•
초기 상태
연산자를 저장할 스택(operatorStack)과 변환된 후위 표현식을 저장할 배열(postfixResult)을 준비
중위 표현식: (a + b - c) * d
operatorStack: (초기 상태: 비어 있음)
postfixResult: (초기 상태: 비어 있음)
Java
복사
•
“(”를 만남
여는 괄호 '('를 만나면, operatorStack에 추가합니다.
중위 표현식: (a + b - c) * d
operatorStack: (
postfixResult: []
Java
복사
•
“a”를 만남
숫자를 만나면, 결과 리스트 (postfixResult)에 바로 추가합니다.
중위 표현식: (a + b - c) * d
operatorStack: (
postfixResult: a
Java
복사
•
“+” 연산자를 만남
+ 연산자를 만나면, operatorStack의 맨 위에 있는 연산자(”(”)의 우선순위와 비교합니다. 현재 스택에는 (가 있으므로, +를 operatorStack에 푸시합니다.
중위 표현식: (a + b - c) * d
operatorStack: ( +
postfixResult: a
Java
복사
•
“b”를 만남
숫자를 만나면, 결과 리스트 (postfixResult)에 바로 추가합니다.
중위 표현식: (a + b - c) * d
operatorStack: ( +
postfixResult: ab
Java
복사
•
“-” 연산자를 만남
- 연산자를 만나면, operatorStack의 맨 위에 있는 연산자와의 우선순위를 비교합니다. 현재 스택의 맨 위에 있는 연산자는 +이며, -와 +는 동일한 우선순위를 갖습니다.
operatorStack의 맨 위에 있는 연산자(+)의 우선순위가 현재 연산자(-)와 같거나 높으면, 해당 연산자를 팝(pop)하여 postfixResult에 추가한 다음 -를 operatorStack에 푸시합니다.
이 작업을 operatorStack의 맨 위 연산자의 우선순위가 현재 연산자의 우선순위 보다 낮을 때까지 계속 반복합니다.
중위 표현식: (a + b - c) * d
operatorStack: ( -
postfixResult: ab+ (- =< +)
Java
복사
•
“c”를 만남
중위 표현식: (a + b - c) * d
operatorStack: ( -
postfixResult: ab+c
Java
복사
•
“)”를 만남
닫는 괄호 ')'를 만나면, operatorStack에서 여는 괄호 '('가 나올 때까지 스택의 상단에 있는 연산자를 postfixResult에 추가하고, 스택에서 제거합니다. 여는 괄호 '('도 스택에서 제거합니다.
중위 표현식: (a + b - c) * d
operatorStack:
postfixResult: ab+c-
Java
복사
•
“*”를 만남
* 연산자를 만나면, operatorStack의 맨 위에 있는 연산자의 우선순위와 비교합니다. 현재 operatorStack은 비어 있으므로, *를 operatorStack에 푸시합니다.
중위 표현식: (a + b - c) * d
operatorStack: *
postfixResult: ab+c-
Java
복사
•
“d”를 만남
숫자를 만나면, 결과 리스트 (postfixResult)에 바로 추가합니다.
중위 표현식: (a + b - c) * d
operatorStack: *
postfixResult: ab+c-d
Java
복사
•
중위 표현식의 모든 요소 순회 완료
중위 표현식을 모두 순회했으므로, operatorStack에 남아있는 연산자들을 모두 팝하여 postfixResult에 추가합니다. 여기서 *를 팝하고 postfixResult에 추가합니다.
중위 표현식: (a + b - c) * d
operatorStack:
postfixResult: ab+c-d*
Java
복사
이렇게 중위 표현식 (a + b - c) * d가 후위 표현식 a b + c - d *로 변환되었습니다.