이 문제들을 다 풀면 stack, queue 정복!

Q. 다음 중 스택에 대한 설명으로 틀린 것은?

A

먼저 들어간게 나중에 나오는 First In Last Out 구조이다. 

B

먼저 들어간게 먼저 나오는 First In First Out 구조이다. 

C

top 메서드는 스택의 맨 위에 있는 값을 꺼내고, 해당 값을 반환한다. 

D

스택에 할당된 공간이 꽉 차면 더이상 push 할 수 없다. 

E

재귀 함수를 실행할 때 사용된다. 

 

answer : b c

 

A

먼저 들어간게 나중에 나오는 First In Last Out 구조이다. O

B

먼저 들어간게 먼저 나오는 First In First Out 구조이다. X

C

top 메서드는 스택의 맨 위에 있는 값을 꺼내고, 해당 값을 반환한다. X

=> top 메서드는 스택의 맨 위에 있는 값을 꺼내고, 해당 값을 반환한다. -> top은 속성이다!! 메서드가 아님.

D

스택에 할당된 공간이 꽉 차면 더이상 push 할 수 없다. O

E

재귀 함수를 실행할 때 사용된다. O

 

 

다음과 같은 코드의 실행 결과는?

function calc(expression) {
  // 1. 문자를 하나씩 검사한다.
  // 2. 숫자를 만나면 숫자를 스택에 푸시한다.
  // 3. 연산자를 만나면 스택에서 팝을 두 번 하고, 두 개의 숫자를 가지고 연산한다.
  // 4. 3의 연산 결과를 다시 스택에 푸시한다.
  // 5. 문자열이 끝날 때 까지 반복한다.
  // 6. 문자열이 끝나면 연산 결과 값을 리턴한다.
}

const result = calc("9 3 * 15 5 / + 2 -") 
console.log(result);

answer : 28

이것은 후의 표기법이다. 

우리가 보통 쓰는 것은 중의표기법인데

위의 식을 중의표기법으로 바꾸면

(9 * 3) + (15  / 5) - 2 와 같다.

 

 

Q. 다음과 같은 코드의 실행 결과는?

const stack = new Stack();
stack.push('A');
stack.push('E');
stack.push('C');
stack.push('F');
stack.push('D');
stack.pop();
stack.pop();

console.log(stack.peek(), stack.size());

answer C 3

 

peek()은 top을 읽는 메소드

size는 length를 반환한다.

 

 

Q. queue에 대한 설명 중 틀린 것을 모두 고르면?

A

먼저 들어간게 먼저 나오는 First In First Out 구조이다. 

B

먼저 들어간게 나중에 나오는 First In Last Out 구조이다. 

C

dequeue는 큐의 가장 앞에 있는 값을 꺼내서 반환한다. 

D

rear는 큐의 마지막 값의 인덱스를 가리킨다. 

E

큐의 검색 시간 복잡도는 O(n)이다. 

F

하노이의 탑의 구조는 큐와 유사하다. 

 

answer : b f

A

먼저 들어간게 먼저 나오는 First In First Out 구조이다. O

B

먼저 들어간게 나중에 나오는 First In Last Out 구조이다. X

C

dequeue는 큐의 가장 앞에 있는 값을 꺼내서 반환한다. O

D

rear는 큐의 마지막 값의 인덱스를 가리킨다. O

E

큐의 검색 시간 복잡도는 O(n)이다. O

F

하노이의 탑의 구조는 큐와 유사하다. X

 

 

Q. 다음과 같은 코드의 실행 결과로 적합한 것은?

const queue = new Queue();
queue.enqueue(10);
queue.enqueue(15);
queue.enqueue(30);
queue.enqueue(20);
queue.dequeue();
queue.enqueue(47);

console.log(queue.dequeue(), queue.size());

answer

15 3

 

 

Q. 다음 코드는 우선 순위가 높은 것이 먼저 나오는 우선순위 큐를 사용한 코드이다.

5번의 enqueue 이후 dequeue를 5번 호출할 때 나오는 값의 순서로 적절한 것은?

(단, priority 가 높을 수록 우선 순위가 높다.)

 

const queue = new PriorityQueue();
queue.enqueue({ value: 'A', priority: 5 })

queue.enqueue({ value: 'B', priority: 2 })

queue.enqueue({ value: 'C', priority: 1 })

queue.enqueue({ value: 'D', priority: 4 })

queue.enqueue({ value: 'E', priority: 3 })

// dequeue 5 times...

answer A - D - E - B - C

 

이것에 대해서는 힙트리 구조를 찾아보자.