프로그래밍/TIL(Today I Learned)

3강 스택

가라멜 2018. 9. 6. 19:10
반응형

1. 스택의 개념과 추상 자료형

- 0개 이상의 원소를 갖는 유한 순서 리스트

- push 와 pop  연산이 한곳에서 발생되는 자료 구조

- 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형


- CreateS 연산

Stack CreateS(maxSize) ::= 스택의 크기가 maxSize 인 빈 스택을 생성하고 반환한다;

- Push 연산

Stack Push(stack, item) ::= if(isFull(stack))

then { 'stackFull' 출력;}

else { 스택의 가장 위에 item을 삽입하고, 스택을 반환;}

- Pop연산

 Element Pop(stack) :: = if(isEmpty(stack))

then { 'stackEmpty' 출력;}

else { 스택의 가장 위에 있는 원소(element)를 삭제하고 반환;}



2. 스택의 응용과 연산(중요)

- 변수에 대한 메모리의 할당과 수집을 위한 시스템 스택

- 서브루틴 호출 관리를 위한 스택

- 연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산

- 인터럽트의 처리와, 이후 리턴할 명령 수행 지점을 저장하기 위한 스택

- 컴파일러, 순환 호출 관리


<스택의 연산>

- 스택의 삭제 연산

- (*top)-- 에서 사용된'--' 연산자의 위치에 따라 연산의 적용순서가 달라질 수 있음

- 스택의 삽입 연산

-++(*top)에서 사용된 '++' 연산자의 위치에 따라 연산의 적용순서가 달라질 수 있음


3. 배열을 이용한 스택의 구현



4. 사칙 연산식의 전위/후위/중위 표현

수식의 계산

- 연산자의 계산 순서를 생각해야 함


중위 표기법 : 연산자를 피연산자 사이에 표기하는 방법 > A+B

전위 표기법 : 연산자를 피연산자 앞에 표기하는 방법 > +AB

후위 표기법 : 연산자를 피연산자 뒤에 표기하는 방법 > AB+





'프로그래밍 > TIL(Today I Learned)' 카테고리의 다른 글

2강 C++ 언어의 기초(1)  (0) 2018.09.09
3강 유한 오토마타  (0) 2018.09.06
4강 JSP 동작원리  (0) 2018.09.03
3강 JSP 개요  (0) 2018.08.30
3강 처리장치(1)  (0) 2018.08.28