[자료구조] 스택(Stack)

스택

• 0개 이상의 원소를 갖는 유한 순서 리스트
• push(add)와 pop(delete)연산이 한곳에서 발생되는 자료구조
• 가장 먼저 입력된 자료가 가장 나중에 출력
  

연산

스택의 삭제 연산

int pop() {
	if (top == -1) {
    	return StackIsEmpty();
    else return stack[pop--];}

스택의 삽입 연산

void push(int item) {
	if (top >= STACK_SIZE = -1)
    	return StackIsFull();
    else stack[++top]=item;}

수식의 표기 방법

• 수식의 계산
  • 연산자의 계산 우선순위를 생각해야 함
  • A+BC+D ⇒ ((A+(BC))+D)
• 수식의 표기 방법
  • 중의 표기법(infix notation) - 사람
    • 연산자를 피연산자 사이에 표기하는 방법
    • A+B
  • 전위 표기법(prefix notation)
    • 연산자를 피연산자 앞에 표기하는 방법
    • +AB
  • 후위 표기법(postfix notation) → 컴퓨터 + 스택을 쓰면 매우 효율적이다.
    • 연산자를 피연산자의 뒤에 표기하는 방법
    • AB+
• 중위표기식의 후위 표기식 변환 방법
  • 먼저 중위 표기식을 연산자의 우선순위를 고려하여 (피연산자, 연산자, 피연산자)의 형태로 괄호로 묶어줌
  • 각 계산뭉치를 묶고 있는 괄호 안에서 연산자를 계산 뭉치의 가장 오른쪽으로 이동시킴
  • 각 계산뭉치를 하나의 피연산자로 고려하여 위를 반복함
  • 괄호를 모두 제거함