[자료구조] 스택의 개념과 스택 추상 자료형

스택(Stack)

  일반적인 의미 : 물건이 쌓여있는 더미

자료구조에서의 의미 : 자료가 저장된 자료의 더미

 

LIFO(Last in first out) 후입선출 방식으로

나중에 삽입된 자료가 가장 먼저 나간다.

 

사용예

1. 시스템 모델링

먼저들어온 자료가 가장 나중에 나가는 방식

2. 알고리즘

수식, 미로찾기 등의 알고리즘에서 사용

 

 

자료의 삽입과 삭제

자료가 A, B, C 순서대로 삽입되었다고 한다면 

C,B,A 순서로 꺼내게 된다

 

top, 가장 최근에 조회된 자료의 위치에서

자료가 추가되고 삭제되는 것이다!

 

---

스택의 3가지 연산

 

1. 푸시(Push)

값을 Top 위치에 삽입하고, top의 위치가 삽입 된 값의 위치로 변경된다

 

- overflow(넘침) 현상의 발생

: 지정된 stack의 개수보다 더 많은 양의 정보를

저장하고자 할 경우 더이상 추가할 수 없는 오버플로우 현상이 발생된다

 

 

 

2. 팝(Pop)

 top 위치에 있는 값을 제거하기 위하여 사용하는 연산으로

그 아래의 값이 top으로 변경된다

 

- underflow(부족) 현상의 발생

: stack에 저장된 데이터를 모두 제거되어 공백 현상일때

더이상 제거할 수 있는 값이 없을 경우 언더플로우 현상이 발생된다

 

 

 

3. 피크(Peek)

: 반환 값은 그대로 두고 Top 에 있는 값을 보여주는 것을 의미한다.

엿보기 라고 하기도 한다.

---

스택 추상자료형

 

스택 생성

스택의 크기 n이 필요한 경우

배열을 이용하여 생성하는 경우에 필요하고,

연결리스트를 이용하여 생성하는 경우에는 필요하지 않다

 

스택 삭제

생성된 스택을 삭제할 수 있어야하기 때문에

메모리의 크기를 알고자 필요한 경우가 있다

 

스택의 연산

push

원소 추가 가능 여부 판단

오버플로우가 발생하는 것을 방지하기위해 

원소를 추가할수 없는 경우를 판단할 수 있어야한다.

 

pop

공백 스택인지 여부 판단

언더 플로우가 발생하는 것을 방지하기 위해

현재 저장 되어 있는 값이 있는지 확인하여 

공백 스택인지 판단할 수 있어야한다

 

=> 해당 경우는 배열리스트인 경우에 의미가 있으며

연결리스트로 구현된 경우는 크게 고려하지 않아도 된다

 

peek