자료구조 스택

개념

정의

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

가장 먼저 입력된 자료가 가장 나중에 출력되는 관계를 표현

관계를 표현하기 귀해서 연산이 필요하며, 객체에 대한 정의와 연산이 모여서 순서가 기억되는 스택의 추상 자료형이 완성됨

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

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

 

추상 자료형

-스택의 추상자료형

 

응용

-스택의 다양한 응용

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

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

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

인터럽트의 처리와 되돌아갈 명령 수행 지점을 저장하기 위한 스택

컴파일러, 순환 호출 관리

 

연산

-스택의 삭제 연산

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

int a, b;

a = 5;

b = a--; => b = 5

------------------------

b = --a;  => b = 4

 

사칙연산의식의 전위, 후위, 중위 표현

수식의 계산

연산자의 계산 우선순위를 생각해야함

A + B * C + D = ( (A + (B * C)) + D )

 

수식의 표기 방법

-중위 표기법(infix notation)

연산자를 피연산자 사이에 표기 하는 방법

a+b

 

-전위 표기법(prefix notation)

연산자를 피연산자 앞에 표기하는 방법

+ab

 

-후위 표기법(postfix notation)

연산자를 피연산자 뒤에 표기하는 방법

ab+

 

-중위 표기식의 후위 표기식 변환 방법

먼저 중위 표기식을 연산자의 우선순위를 고려하여(피연산자, 연산자, 피연산자)의 형태로 괄호로 묶어줌

각 계산 뭉치를 묶고 있는 괄호 안에서 연ㅅ나자를 계산 뭉치의 가장 오른쪽으로 이동

각 계산 뭉치를 하나의 피연산자로 고려하여 위를 반복

괄호를 모두 제거

 

 

 

 

1. 스택을 생성하는 연산은 프로그래머가 지정한 크기의 새로운 스택을 생성하는 연산이며, 매개변수인 maxStack은 스택이 저장할 수 있는 최대 개수의 element를 의미합니다.
2. StackIsFull(stack, maxStackSize) 연산은 스택이 가득 찼는지를 확인하며, 저장된 원소의 수가 maxStackSize와 같으면 TRUE(‘스택이 가득 찼다’)를 반환하고 아니면 FALSE(‘스택에 여유 저장 공간이 있다’)를 반환합니다.
3. Stack Push(stack, item) 연산은 스택에 새로운 원소를 삽입합니다. 만일 스택이 가득 찼다(Full)면 더 이상의 원소를 스택에 삽입할 수 없으며, ‘stackFull‘ 메시지를 출력합니다.
4. Boolean StackIsEmpty(stack) 연산은 스택 상태가 빈 상태인지를 확인합니다. 만일 스택이 빈 상태이면 ‘TRUE’ 값을 반환하고, 스택에 하나 이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.
5. Element Pop(stack) 연산자는 스택이 빈 상태라면 삭제할 원소가 없으므로 ‘stackEmpty‘를 출력합니다. 하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 스택의 top이 가리키는 원소를 삭제하고 그 원소를 반환합니다.
6. 스택의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
7. 스택은 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형입니다.
8. 중위 표기법(infix notation)은 연산자를 피연산자의 사이에 표기하는 방법이며 일반적으로 가장 많이 사용되는 표기 방법(A+B)입니다.
9. 전위 표기법(prefix notation)은 연산자를 피연산자의 앞에 표기하는 방법 (+AB)입니다.
10. 후위 표기법(postfix notation)은 연산자를 피연산자의 뒤에 표기하는 방법 (AB+)입니다.