스택

• 개념
  • 0개 이상의 원소를 갖는 유한 순서 리스트
  • 한 쪽에서 삽입과 삭제 연산이 수행됨
  • push와 pop연산이 한 곳에서 발생되는 자료구조
  • 선입 후출( First In Last Out ) : 가장 먼저 입력된 자료가 가장 나중에 출력
  • 후입 선출( Last In First Out ) : 가장 나중에 입력된 자료가 가장 먼저 출력
• 응용
  • 변수에 대한 메모리의 할당과 수집을 위한 시스템 스택
  • 서브루틴 호출 관리를 위한 스택
  • 연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산
  • 인터럽트의 처리와 이후 리턴 할 명령 수행 지점을 저장하기 위한 스택
  • 컴파일러, 순환 호출 관리

void push(int* top, element item) {
	if (*top >= STACK_SIZE - 1) {
		return stackFull();
	}
	return stack[++(*top)] = item;
}

element pop(int* top) {
	if (*top == -1) {
		return stackEmpty();
	}
	return stack[(*top)--];
}

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

• 전위표기법

  • 연산자를 피연산자 앞에 표기하는 방법
  • 예 ) + A B
  • 컴퓨터 구조

• 중위표기법

  • 연산자를 피연산자 가운데 표기하는 방법
  • 예 ) A + B
  • 사람

• 후위표기법

  • 연산자를 피연산자 뒤에 표기하는 방법
  • 예 ) A B +
  • 컴파일러

• 중위식 사용의 문제점

  • 연산자 우선순위 법칙을 사용해야 함
  • 2 + 3 * 4
    • ( 2 + 3 ) * 4
    • 2 + ( 3 * 4 )

중위 → 전위

중위 → 후위

큐

• 개념
  • 작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케줄
    • 택시를 타기 위해 서 있는 행렬, 병원의 접수대
  • 한쪽에서는 삽입연산만, 다른쪽에서는 삭제연산만 할 수 있는 구조
  • 선입선출 ( First In First Out ) : 가장 먼저 입력된 자료가 가장 먼저 출력
  • 선착순 서브 ( First Come First Server )