[자료구조] 스택 (2차정리)

스택

스택의 정의

• 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 자료구조
  
• 가장 먼저 입력된 자료가 가장 나중에 출력되는 관계를 표현함
  
• 관계를 표현하기 위해서 연산이 필요하며, 객체에 대한 정의와 연산이 모여서 순서가 기억되는 스택의 추상 자료형이 완성됨
  
• 스택 객체 : 0개 이상의 원소를 갖는 유한 순서 리스트
  
  

스택의 응용

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

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

• 수식의 계산 : 연산자의 계산 우선순위를 생각해야 함
  
• A+BC+D → ((A+(BC))+D)
  
  

수식의 표기 방법

1. 중위 표기법 (사람, 입력)
   
   • 연산자를 피연산자 사이에 표기하는 방법
     
   • A+B
     
     
2. 전위 표기법
   
   • 연산자를 피연산자 앞에 표기하는 방법
     
   • +AB
     
     
3. 후위 표기법 (컴퓨터, 출력(중간단계))
   
   • 연산자를 피연산자의 뒤에 표기하는 방법
     
   • AB+
     
   • 애매모호한 상황이 벌어지지 않기에 효율적
     
     

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

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