[자료구조] Stack

❓ Stack 이란?

---

• 후입 선출(LIFO) 프로토콜을 구현하는 자료 구조
• 접근 가능한 유일한 객체는 최근에 삽입된 객체

== 한쪽 끝에서한 항목을 삭제하거나 새로운 항목을 저장하는 자료구조

 

 

❓ Stack 연산

---

1) Peek: 스택이 공백이 아니면, Top의 원소를 return

2) Pop: 스택이 공백이 아니면, Top의 원소를 삭제해서 return

3) Push: 주어진 원소를 스택의 Top에 추가

4) Size: 스택에 있는 원소의 수 return

 

 

❓ Stack 구현

---

• array를 기반 구현
  -> 스택의 원소를 저장하기 위해 배열 사용
  -> Size, Peek, Pop, Push 외에 isEmpty, resize 메소드 포함 
  => ArrayStack은 스택이 꽉 찼을 때 배열을 재구축해야 하므로 다소 비효율적
  
  
• linkedlist 기반 구현

 

 

 

❓ Stack 응용

---

- 후위식

- 수식 괄호 검사

- 미로 연구