5.5 연습 문제¶

5.5.1 개념 확인¶

빈 스택 S와 빈 큐 Q를 준비하고, 각각에 같은 연산을 수행한다.

1단계: A를 넣는다. 2단계: B를 넣는다. 3단계: 원소 하나를 꺼내 기록한다. 4단계: C를 넣는다. 5단계: 비어 있을 때까지 원소를 계속 꺼내 기록한다.

S와 Q에서 원소가 나오는 순서를 각각 적고, ‘후입선출’ 또는 ‘선입선출’로 차이를 설명하라.

참고 답안

스택 S에서 나오는 순서는 B, C, A다. A, B를 넣은 뒤 가장 최근에 넣은 B를 먼저 꺼내고 C를 넣는다. 이후 C, A를 차례대로 꺼내므로 ‘후입선출’의 특성을 보인다.

큐 Q에서 나오는 순서는 A, B, C다. A, B를 넣은 뒤 가장 먼저 넣은 A를 꺼내고, C를 넣는다. 이후 B, C를 차례대로 꺼내므로 ‘선입선출’의 특성을 보인다.

길이가 5인 원형 배열로 큐를 구현하며, 배열의 인덱스는 0～4다. 현재 front = 3, size = 2이고 큐의 A, B는 각각 인덱스 3과 4에 있다.

참고 답안

새 원소의 위치는 (front + size) % 5 = (3 + 2) % 5 = 0이므로, C는 인덱스 0에 저장된다. 삽입 후 size = 3이다.
현재 큐의 맨 앞 원소인 A가 나온다. 새로운 맨 앞 인덱스는 (3 + 1) % 5 = 4이므로 front = 4, size = 2다.
유효한 원소의 논리적 순서는 B, C이며, B는 인덱스 4에, C는 인덱스 0에 있다. 원소를 꺼낼 때는 front를 이동하고 size만 수정하면 된다. 원형 배열에서는 나머지 연산으로 인덱스가 처음으로 돌아가므로, 다른 원소를 모두 앞으로 옮길 필요가 없다.

여기서는 push_first를 앞에 넣기, push_last를 뒤에 넣기, pop_first를 앞에서 꺼내기, pop_last를 뒤에서 꺼내기로 정의한다.

빈 덱 deq에 다음 연산을 차례대로 수행한다.

두 번 꺼낸 원소는 각각 무엇인가?
모든 연산을 마친 뒤 앞에서 뒤까지 어떤 원소가 남는가?
뒤에서만 넣고 앞에서만 삭제할 수 있는 큐로 이 6단계를 모두 수행할 수 있는가? 불가능하다면 수행할 수 없는 연산을 찾아라. 이어서 덱은 모두 수행할 수 있는지와 그 이유를 설명하라.

참고 답안

처음 세 단계를 마치면 덱의 앞에서 뒤까지는 [C, A, B]다.

pop_last()로 B를 꺼낸다. D를 넣으면 [C, A, D]가 되고, pop_first()로 C를 꺼낸다.
마지막에는 [A, D]가 남는다.
뒤에서만 넣고 앞에서만 삭제하는 큐로는 모든 연산을 수행할 수 없다. 3단계의 push_first(C)는 앞에 넣어야 하고, 4단계의 pop_last()는 뒤에서 삭제해야 하므로 이 큐가 지원하는 연산 범위를 벗어난다. 덱은 양 끝에서 모두 삽입과 삭제가 가능하므로 6단계를 전부 수행할 수 있다.

세 종류의 괄호 (), [], {}만 포함하는 문자열 s가 주어진다. 스택을 사용하여 올바른 괄호 문자열인지 판단하라.

올바른 문자열은 다음 두 조건을 모두 만족해야 한다. 닫는 괄호는 가장 최근에 등장한, 아직 짝이 없는 여는 괄호와 종류가 같아야 하며, 순회를 마친 뒤 짝이 없는 여는 괄호가 남아 있어서는 안 된다. 판단 결과를 불리언 값으로 반환하라.

풀이 힌트