[자료구조] 4강 3장 스택과 큐 - 1절 스택

3장 스택과 큐 - 1절 스택

 

* 스택의 정의

스택 : 선형 자료 구조의 한 종류

비선형 구조 : 트리, 그래프

선형 구조 : 스택, 리스트, 배열 (각각의 원소들이 순서를 가지고 있다)

선형 자료 구조의 한 종류

원소의 삽입과 삭제가 리스트의 한쪽 끝에서만 이루어지는 구조

가장 마지막에 삽입된 원소가 가장 마지막에 삭제되는 구조로서 후입선출(LIFO: Last In First Out)구조

삽입(push) : 스택에 원소를 삽입하는 과정

삭제(pop) : 스택에서 원소를 꺼내오는 과정

top pointer :주로를 가리키는 포인터 값

 

* 시스템 스택

프로그램에서 호출과 복귀에 따른 수행 순서를 관리하기 위한 스택

함수 호출이 발생하면 스택 프레임에 여러 정보들을 저장하여 시스템 스택에 삽입

호출한 함수 수행에 필요한 지역 변수, 매개변수 및 수행 후 복귀할 주소 정보를 저장

함수 실행이 끝나면 복귀 주소 확인 (복귀주소가 없으면 프로그램 순서가 모호해지므로 필수적이다.)

 

* 스택의 추상화 자료 구조

특정한 자료들이 가지고 있는 요소들, 그 요소들이 할수 있는 기능들을 나열

* 스택의 삽입 연산

void push(data, stack, n, top) [n = stack_size , top = 0]

 

* 스택의 적용 분야들

부프로그램 호출시 복귀 주소를 저장

함수 호출의 순서 제어

인터럽트가 발생하여 복귀 주소를 저장

후위 표기법으로 표현된 산술식을 연산 (AB+)

0- 주소지정방식 명령어의 자료 저장

재귀 프로그램의 순서 제어 (factorial 등)

컴파일러를 이용한 언어 번역

문자열 역순 생성 – push

 

* 정리

스택은 LIFO구조

프로그램 호출/복귀에 필요한 시스템 스택

스택의 삽입/삭제 과정(오버플로우, 언더플로우)

스택의 적용 분야들