이롭게 현명하게
[자료구조] 스택(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
[스택 응용 산술표기법]
- 중위 표기법(Infix)
- 후위 표기법(Postfix)
- 전위 표기법(Prefix)
< 중위 표기법 (Infix) >
연산자를 두 개의 피 연산자 사이에 표기하는 방법
A+B
< 후위 표기법 (Postfix) >
연산자를 두 개의 피연산자 뒤에 표기하는 방법
AB+
< 전위 표기법 (Prefix) >
연산자를 두 개의 피연산자 앞에 표기
+AB
<예시>
A*B+C/D
- 중위 표기법 : A*B+C/D
- 후위 표기법 : AB*CD/+
- 전위 표기법 : +*AB/CD
잘못된 정보는 댓글에 남겨주시면 감사하겠습니다!😊
댓글과 좋아요는 큰 힘이 됩니다!
[ 참고자료 ]