[자료구조] 스택(Stack) / 이론

 

---

 

목차

 

스택 정의

스택 구조

삽입과정

삭제과정

스택 응용 산술표기법

 

---

 

---

[스택 정리]

스택 : 쌓아 올린다는 의미로 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있는 것을 말한다.

• 순서리스트
• 리스트를 구성하는 각각의 원소에 대한 조작에 일정한 제한을 가한 데이터구조
• LIFO구조 (Last In First Out) : 마지막에 들어간게 먼저 나온다.
• Bottom : 한쪽 끝은 막혀있다.
• Top : 뚫려있는 한쪽 끝. 모든 원소의 삽입과 삭제가 행해진다.
• Push : Top에 새로운 원소를 넣는 것
• Pop : 스택의 Top으로부터 한 원소를 삭제

 

---

[스택 구조]

스택은 데이터를 쌓아 올리는 구조이다.

그러므로 비커와 같은 모양으로 한쪽 방향으로만 데이터를 넣을 수 있는 구조이다.

 

 

스택을 생성하면 데이터가 없기 때문에 top의 위치는 bottom위치와 같다.

즉, Top이 0이라면 스택은 비어있는 상태이다.

 

스택의 최상위 부분은 stack size로 스택의 크기를 나타낸다.

만약 Top의 위치가 Stack size와 같다면 스택은 꽉 찬 상태이다.

 

 

---

[삽입과정]

스택에 새로운 요소를 추가할 때는 항상 Top에서 행해진다.

스택 크기 =n, Top 초기값 = 0

Top값을 1 증가시킨다.

 

 

증가된 Top포인터가 스택의 크기를벗어나지 않았는가를 확인한다.

 

 

만약 증가된 Top 포인터가 스택의 크기를 벗어났다면 OverFlow가 발생한다.

만약 증가된 Top 포인터가 스택의 크기를 벗어나지 않았다면 데이터를 삽입한다.

 

< 삽입 알고리즘 >

Top ←Top + 1

if Top > n then StackOverFlow or Exit

STACK[Top] ←item

END_PUSH

 

Top ←Top+1

if Top> n then StackOverFlow or Exit

STACK[Top] ←item

END_PUSH

 

 

---

[삭제과정]

스택에서 하나의 요소를 삭제하고자 할 때 Top이 가리키는 요소를 제거한다.

Top에 요소가 있다면 Top 요소를 삭제한 후

 

Top의 값을 1 감소

 

Top=0일 때는 현재 스택은 공백상태이므로 스택이 empty를 나타낸다.

스택이 비어있을 때 삭제를 시도하면 UnderFlow가 발생한다.

 

< 삭제 알고리즘 >

if Top ≤ 0 then UnderFlow or Exit

item ← STACK[Top]

Top ← Top-1

END_POP

if Top <= 0 then UnderFlow or Exit

item ← STACK[Top]

Top ← Top-1

END_POP

 

---

[스택 응용 산술표기법]

1. 중위 표기법(Infix)
2. 후위 표기법(Postfix)
3. 전위 표기법(Prefix)

< 중위 표기법 (Infix) >

연산자를 두 개의 피 연산자 사이에 표기하는 방법 

A+B

< 후위 표기법 (Postfix) >

연산자를 두 개의 피연산자 뒤에 표기하는 방법

AB+

< 전위 표기법  (Prefix) >

연산자를 두 개의 피연산자 앞에 표기

+AB

 

<예시>

A*B+C/D

1. 중위 표기법 : A*B+C/D
2. 후위 표기법 : AB*CD/+
3. 전위 표기법 : +*AB/CD

 

 

---

잘못된 정보는 댓글에 남겨주시면 감사하겠습니다!😊

댓글과 좋아요는 큰 힘이 됩니다!

 

[ 참고자료 ]