[자료구조] Chapter 05. 스택 (Stack)

🚨 'C언어로 쉽게 풀어쓴 자료구조' 라는 책을 활용했던 과거 수업 필기를 정리한 것입니다.
💡 Chapter 순서는 책과 같지만 교수님의 과거 수업 내용에 따라 일부 책과 다른 내용이 있습니다.

1. Stack의 정의

2. Stack의 구현

1. 배열(Array)로 구현
   : 배열의 제한된 크기로 인한 stack overflow error(무한 루프로 쌓이다 보면 스택 꽉참 -> 계속 넣어야할 때 발생하는 오류) 고려
   
2. SLL(Singly-Linked List)로 구현
   : 크기의 제한 없이 무한 삽입 가능
   

3. Stack의 이용 사례

1. return address (함수 호출을 실행)
2. Back Tracking (미로찾기, 그래프 탐색)
   ex) 로봇이 길 찾을 때 끝까지 가보고 막히면 돌아와서 다른 길로 가보기 반복
3. 식(expression)의 처리
   

💡 참고 Polish notation (식의 표기법)

• a + b : infix notation (중위 표기법)
• +a b : prefix notation (전위 표기법)
• a b+ : postfix notation (후위 표기법)

💡 모든 식은 중위 표기식 (infix)에서 후위표기식 (postfix)으로 변환 후 계산

• b (c + d) -> bcd+
  a == b || x > y + z -> ab == xyz + > ||
• a b / (c + d) - e : infix
  -> -/a b + c d e : prefix
  -> a b * c d + / e - : postfix => 실제 계산은 stack 사용
  

4. LRU Stack (Least-Recently Used Stack)

운영체제(OS)

• Demend paging (요구 paging)
• Page Fault (Page 부재)
• Page Replacement (Page 교체)
• Victim Page 선정 (희생자 Page) => Hit-ratio (<-> Page Fault rate) / LRU policy