[자료구조] 스택이란?

• 스택

- 삽입과 삭제가 한쪽 끝에서만 수행되는 제한적 개념의 선형 구조

- 가장 마지막에 입력된 자료가 가장 먼저 출력되므로 후입 선출

   (LIFO, last in first out) 구조

- 중간에 자료를 삽입(push)하거나 삭제(pop)할 수 없으므로 자료의

  입출력이 비교적 제한적이며, 스택의 탑(top) 위치에서만 자료의 

   삽입과 삭제가 이루어짐.

 ‣ 탑(top)

  - 일반적으로 스택의 가장 위에 위치하는 자료

  - 삭제할 지점을 가리킴.

 

• 자료 삽입

- 탑의 초깃값은 -1이며, 자료가 삽입될 때마다 1씩 증가함

- 새롭게 입력할 자료를 스택의 가장 위에 추가

- 기존에 저장된 자료들은 추가한 자료의 아래에 위치

- 여유 공간이 있을 경우 얼마든지 자료 추가 가능

- 스택의 크기보다 많은 자료를 입력할 수는 없음

 

• 자료 삭제

- 탑은 자료가 삭제될 때마다 1씩 감소

- 스택의 가장 위에 입력된 자료를 먼저 제거하고

  제거된 자료의 아래에 있던 자료가 가장 위에 위치하게 됨

 

• 오류 발생 조건

- 스택 구조도 제한된 저장 공간을 사용하기 때문에 연산을

  수행할 때는 반드시 스택의 크기와 상태를 고려해야 함

 ‣ 오버플로(overflow)

  - 자료를 저장할 수 있는 스택 공간이 제한적이므로 자료가

     가득 차있는 상태에서 새로운 자료 추가 불가

  - 자료에 대한 추가적인 입력 요청으로 탑이 1 증가하여 스택의

     크기와 같아진 경우 오버플로 발생

  - 탑 포인터의 위치가 스택의 크기를 벗어나게 된 경우

 ‣ 언더플로(underflow)

  - 아무 자료도 저장되어 있지 않은 빈 스택 공간에서 자료의 삭제를

     요청할 경우 삭제할 자료가 없으므로 언더플로 발생

  - top이 -1인 상태에서 추가적인 자료의 삭제를 요청할 경우

 

---

문제) 접시를 쌓아올린다고 할 때 총 9개의 접시를 쌓는다고 할 때, 아래에서 3번째 접시를 꺼내기 위해서는 총 몇번의 push와 pop을 사용해야 하는가?

풀이

총 9개의 접시를 쌓아야 하므로 9번의 push가 필요함.

이후 아래에서 3번째 접시를 꺼내야하므로 7번의 pop이 필요함.