[자료구조] 스택 (Stack)

스택(stack)

 - 스택에 저장된 원소는 top으로 정한 곳만 접근이 가능하다.

    ㄴ 후입 선출 구조(LIFO, Last-In-First-Out) : 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제된다.

출처 : IT COOKBOOK

스택의 연산

 - 삽입(push)

① top의 위치를 하나 증가(∵ top은 스택에서 마지막 자료를 가리키기 때문)
    이때, 만약 top의 위치가 스택의 크기보다 커지면 오버플로우가 발생하므로 연산 수행하지 않고 종료.
② 스택의 top이 가리키는 위치에 삽입

		-①->			-②->
				←top		C	←top
B	←top		B			B
A			A			A

 - 삭제(pop)

① 스택이 공백이 아니라면 top이 가리키는 원소를 먼저 반환
② 스택의 top의 위치를 그 아래의 원소로 변경(top 위치 하나 감소)

		-①->			-②->
C	←top			←top
B			B			B	←top
A			A			A

---

순차 자료구조를 이용한 스택의 구현

 - 1차원 배열 이용

    ㄴ 스택의 크기 : 배열의 크기(n)

    ㄴ 스택에 저장된 원소의 순서 : 배열 원소의 인덱스 (0 ~ n-1)

 - 순차 자료구조로 구현한 스택의 장점

    ㄴ 1차원 배열을 사용하여 쉽게 구현

 - 순차 자료구조로 구현한 스택의 단점

    ㄴ 물리적으로 크기가 고정된 배열을 사용하므로 스택 크기 변경 불가

    ㄴ 순차 자료구조의 단점과 동일

---

연결 자료구조를 이용한 스택의 구현

 - 단순 연결 리스트 이용

    ㄴ 스택의 원소 : 단순 연결 리스트의 노드

    ㄴ 원소의 순서 : 노드 링크 포인터로 연결

top	●	→	n번째 원소 data	●
				↓
			. . .
				↓
			두 번째 원소 data	●
				↓
			첫 번째 원소 data	null

---

스택 사용 Version) 중위 표기식 ㅡ변환ㅡ> 후위 표기식

[자료 구조] 수식의 표기법 (Notation)

[자료 구조] 수식의 표기법 (Notation)