[자료구조] 스택

스택의 개념

스택의 정의

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

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

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

• 0개 이상의 원소를 갖는 유한 순서 리스트
• push(add) 와 pop(delete) 연산이 한곳에서 발생되는 자료구조

스택의 추상자료형

• 스택 객체 → 0개 이상의 원소를 갖는 유한 순서 리스트

push 연산

Stack Push(stack , item) ::= 
			if(StackIsFull(stack))
					then{'stackFull' 출력;}
					else{스택의 가장 위에 item 을 삽입하고, 스택을 반환한다;}

pop 연산

Element Pop(stack) ::= 
				if(StackIsEmpty(stack))
					then {'stackEmpty' 출력;}
					else { 스택의 가장 위에 있는 원소를 삭제 하고 반환한다; }

StackIsFull 연산

Boolean StackIsFull(stack, maxStackSize) ::=
	if((stack의 elements의 개수) == maxStackSize)
			then {true}
			else {false}

StackIsEmpty 연산

Boolean StackIsEmpty(stack):: =
		if(stack == CreateStack(maxStackSize))
			then {true}
			else {false}

스택의 응용

• 변수에 대한 메모리의 할당과 수집을 위한 시스템 스택
• 서브루틴 호출 관리를 위한 스택
• 연산자들간의 우선순위에 의해 계산 순서가 결정되는 수식 계산
• 인터럽트 의 처리와 되돌아갈 명령 수행 지점을 저장하기 위한 스택
• 컴파일러, 순환 호출 관리

스택의 연산

스택의 삭제 연산

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

int a, b;
a = 5;
b = a --;
// a = 4 , b = 5 | b =a 가 먼저 대입 이 되고  - 값이 적용

int a , b;
a = 5;
b = --a;
// a = 4 , b = 4 | a-1 이 먼저 적용이 되고 b에 대입

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

수식의 계산

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

A + B * C + D

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

수식의 표기 방법

• 중위 표기법(infix notation) (사람)

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

→ A + B

• 전위 표기법(prefix notation)

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

→ + AB

• 후위 표기법(postfix notation) (컴퓨터)

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

→ AB +

후위 표기법

• A + B → AB +

1. (A - ((B+K) / D))
2. (A - ((BK+) / D))
3. (A - ((BK+) D/))

→ A((BK +) D /) -

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

• 먼저 중위 표기식을 연산자의 우선순위를 고려하여 (피연산자, 연산자, 피연산자) 의 형태로 괄호로 묶어줌
• 각 계산뭉치를 묶고 있는 괄호 안에서 연산자를 계산 뭉치의 가장 오른쪽으로 이동 시킴
• 각 계산 뭉치를 하나의 피연산자로 고려하여 위를 반복
• 괄호를 모두 제거함