자료구조 스택 이론 조금(LIFO, push, pop, top, 스택 응용 등)

리스트 작업은 시간과 무관

스택(큐도 마찬가지) 시간을 기준 (시간에 대한 정보가 포함)

 

배열, 리스트 중간 삽입 가능 -> 시간 기준이라 볼 수 없음

 

스택 예시

1. 식판 닦기 2. 음료수 진열 3. 연탄 아궁이 4. 책 쌓기 등등

 

LIFO (Last In First Out) / 후입선출

 

탑 : 마지막 스택 위치, 항상 마지막을 가리킴 / 마지막 원소의 위치 

푸쉬 : 넣기

팝 : 빼기 

 

개념 -> 추상 자료형 -> 알고리즘 -> 구현 

--> 구체화됨 -->

 

 

 

스택 push 알고리즘

top이 마지막 자료를 가리키므로 그 위 자료를 삽입하려면 top의 위치를 하나 증가

이 때 top의 위치가 스택의 총 크기보다 크면 오버플로우

오버플로우가 아니면 top이 가리키는 위치에 새로운 원소 삽입

 

스택의 pop 알고리즘

스택이 공백 스택이 아니면 top이 가리키는 원소를 먼저 반환

그 후 top의 위치는 그 아래의 원소로 변경하기 위해 위치 하나 감소 

 

 

 

순차자료구조 이용

- 스택의 크기 : 배열의 크기

- 스택에 저장된 원소의 순서 : 배열 원소의 인덱스

0번 스택의 첫 번째 원소 / n-1번 스택의 n번째 원소

 

변수 top : 스택에 저장된 마지막 원소에 대한 인덱스 저장

- 공백상태 : top = -1 

- 포화상태 : top = n-1

 

장점 : 구현 쉬움

단점 : 스택 크기를 변경하기 어려움, 메모리 공간의 낭비나 오버플로우의 발생가능성 

 

(배열 포인터는 차원을 넘어 ~) 포인터 다차원 배열 

 

 

연결자료구조 이용

단순연결리스트 이용

스택의 원소 : 노드

순서 : 노드의 링크 포인터로 연결(시간적 특성 함유해야 함)

push : 마지막 노드 삽입 (char Item 인자로 받고)

pop : 마지막 노드 삭제

연결 리스트와 차이

: 방향이 반대

스택은 늘 마지막 노드를 가져감

Top 관리 편함 -> 사라지기 전에 노드의 링크 값을 넣어주기

Top을 이용한 구현 방식 가능

 

스택 응용 방법

1. 역순 문자열

2. 시스템 스택 

3. 괄호 검사

4. 후위표기법 변환

5. 후위표기 수식의 연산

 

 

깊이 우선 탐색

- 백 트래킹 : 되돌아오는 행위

- 재방문 회피 : 갔던 곳 다시 안감

백트랙으로 인한 스택이 비어짐 -> 하고자하는 경로가 없음 의미

 

 

 

실습과 코드 이론은 시험기간 때 복습하기

과제나 해야지;;