3.스택 4. 큐

 

중위표기법 A+B

전위 표기법 +AB

후위표기법 AB+

 

Q2

스택의 응용 분야가 아닌 것은 ?

1

시스템 스택

2

서브루틴 호출

3

작업 스케쥴링

4

후위 수식의 계산

 

스택의 응용

 

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

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

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

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

컴파일러, 순환호출  

스택의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.

 

 

중위표기법을 후위표기법으로 바꿀때 스택의 상태

ex)A+B*C  => ABC*+

 

왼쪽부터 읽어가는데, 알파벳의 경우에는 그냥 출력.  연산자의경우에는 아래 규칙에 따라 행동한다

 

현재 읽은 연산자(+ - )의 우선순위가 스택 상단의 연산자(* / )보다 낮거나 같을 때는 다음과 같이 합니다:

1. 스택에서 우선순위가 높거나 같은 연산자를 모두 팝하여 출력 목록에 추가합니다.
2. 현재 연산자를 스택에 푸시합니다.

현재 읽은 연산자(* / )의 우선순위가 스택 상단의 연산자(+ -)보다 높거나 스택이 빈경우에는 현재 읽은 연산자 push

 

 

 

큐

 

 

큐의 프론트에서는 삭제가 발생한다

FIFO 

FCFS스케줄링 : 작업이 준비큐에 도착한 순서대로 cpu를 할당받고 작업이 완료될 때까지 cpu를 사용하는 기법

 

RoundRobin 스케줄링 : 대화형 시스템에 적합하며 일정시간만 cpu 를 사용하는 스케줄링 방식

 

front , rear의 초기값은 큐의 공백상태를 나타내는 -1로 한다

삽입일떄는 rear변수가 증가

삭제는 front변수가 증가

rear==front면 큐가 빈상태임

 

 

큐에서 노드를 삽입할 경우의 설명으로 맞는 것은 ?

1

rear의 위치를 감소시킨 후 원소를 삽입

2

 front의 위치를 증가시킨 후 원소를 삽입

3

 rear의 위치를 증가시킨 후 원소를 삽입

4

front의 위치를 감소시킨 후 원소를 삽입

 

 

원형큐

mod메서드 사용

 

1. void Add_q(element item) {

2. if ( (가) )

3.   {   printf(“Queue is full !!”) ;

4.       return ;       }

5.  queue[ (나) ] = item ; 

6.  return ;   }

Q3

지문은 큐에 원소를 삽입하는 알고리즘이다. (가) 와 (나) 에 알맞은 내용은?

1

(가) rear == QUEUE_SIZE

(나 ) rear++

2

(가) rear == QUEUE_SIZE

(나 ) ++rear

3

(가) rear == QUEUE_SIZE-1

(나 ) ++rear

 

 

 

코드도 알고있어야함