스택, 큐, 후위표기식

3장 1절에서는 자료구조의 기본 개념과 배열을 배웠습니다.

자료구조 = 데이터를 저장하는 방법
알고리즘 = 문제를 해결하는 절차
배열 = 인덱스로 빠르게 접근하는 연속 저장 구조

이번 절에서는 배열을 이용해서 만들 수 있는 대표 자료구조인 스택과 큐를 배웁니다.

이번 절의 핵심은 다음과 같습니다.

스택 = 나중에 들어온 것이 먼저 나갑니다
큐 = 먼저 들어온 것이 먼저 나갑니다
후위표기식 = 연산자를 피연산자 뒤에 쓰는 수식 표기법

이 내용은 자료구조 출제범위의 스택, 큐, 원형 큐, 데크, 스택을 이용한 수식 계산과 표기식 변환, 후위표기식의 연산, 중위표기를 후위표기로 변환, 미로 찾기, 서브루틴 주소 복귀, 다중 스택, 다중 큐에 해당합니다. 또 후위표기식 변환에서는 C프로그래밍에서 배운 연산자 우선순위, 조건문, 반복문 개념도 같이 쓰입니다.

이번 절의 큰 그림

이번 절에서 배울 흐름은 다음과 같습니다.

스택의 개념
→ 스택의 삽입과 삭제
→ 오버플로와 언더플로
→ 스택의 응용
→ 큐의 개념
→ 선형 큐와 원형 큐
→ 데크
→ 중위표기식, 전위표기식, 후위표기식
→ 후위표기식 계산
→ 중위표기식을 후위표기식으로 변환

이번 절에서는 자료구조에서 매우 중요한 주제를 다룹니다.

왜냐하면 스택과 큐는 뒤에서 운영체제, 컴퓨터구조, 그래프 탐색, 함수 호출, 수식 계산에 계속 나옵니다.

스택

스택이란?

스택은 한쪽 끝에서만 삽입과 삭제가 일어나는 자료구조입니다.

쉽게 말하면 접시 쌓기입니다.

접시를 위에 올립니다.
꺼낼 때도 위에서부터 꺼냅니다.

먼저 넣은 접시는 아래에 깔립니다. 나중에 넣은 접시가 먼저 나옵니다.

그래서 스택의 핵심은 이것입니다.

LIFO = Last In First Out

마지막에 들어온 것이 먼저 나갑니다.

push A
push B
push C

스택 상태는 이렇게 됩니다.

위
C
B
A
아래

C → B → A

입니다.

스택의 기본 연산

스택에는 대표 연산이 있습니다.

가장 중요한 것은 push와 pop입니다.

push = 넣기
pop = 꺼내기

스택의 top

스택에서는 맨 위 위치를 가리키는 변수가 필요합니다.

그 변수를 보통 top이라고 합니다.

배열로 스택을 만들면 보통 이렇게 생각합니다.

int stack[5];
int top = -1;

처음에는 스택이 비어 있으므로 top = -1입니다.

top = -1 → 스택이 비어 있음

데이터를 하나 넣으면 top이 증가합니다.

push 10
top = 0
stack[0] = 10

push 20
top = 1
stack[1] = 20

인덱스: 0   1
값:    10  20
top = 1

맨 위 값은 stack[top], 즉 stack[1] = 20입니다.

스택 push 과정

스택에 값을 넣는 과정을 살펴보겠습니다.

stack[5]
top = -1

push(10):

top을 1 증가시킵니다.
stack[top]에 10을 넣습니다.

top = 0
stack[0] = 10

push(20):

top = 1
stack[1] = 20

push(30):

top = 2
stack[2] = 30

인덱스: 0   1   2   3   4
값:    10  20  30
top = 2

맨 위는 30입니다.

스택 pop 과정

pop은 맨 위 값을 꺼내는 연산입니다.

인덱스: 0   1   2
값:    10  20  30
top = 2

pop()을 하면:

stack[top] 값을 꺼냅니다.
top을 1 감소시킵니다.

30

top = 1

이제 맨 위는 20입니다.

```text title="다시 pop()" 꺼낸 값 = 20 top = 0

```text title="다시 `pop()`"
꺼낸 값 = 10
top = -1

이제 스택은 비었습니다.

스택 오버플로와 언더플로

스택에서 시험에 자주 나오는 말이 있습니다.

overflow
underflow

오버플로

스택이 가득 찼는데 또 넣으려고 하는 경우입니다.

overflow = 가득 찼는데 push

int stack[5];

0, 1, 2, 3, 4

top == 4이면 이미 가득 찬 상태입니다.

이때 또 push하면 오버플로입니다.

언더플로

스택이 비었는데 꺼내려고 하는 경우입니다.

underflow = 비었는데 pop

top = -1

이때 pop을 하면 꺼낼 값이 없습니다.

자료구조 예시문제에도 스택 삭제 알고리즘에서 top ≤ 0이면 호출해야 하는 처리로 언더플로 처리를 묻는 문제가 나옵니다.

스택 연산의 시간 복잡도

스택의 기본 연산은 빠릅니다.

스택은 중간 데이터를 직접 찾는 구조가 아닙니다.

스택은 맨 위만 다룹니다.

그래서 push와 pop이 단순하고 빠릅니다.

배열로 구현한 스택 코드

간단한 C 코드로 보면 다음과 같습니다.

#define SIZE 5

int stack[SIZE];
int top = -1;

void push(int item) {
    if (top == SIZE - 1) {
        printf("overflow");
    } else {
        top++;
        stack[top] = item;
    }
}

int pop(void) {
    if (top == -1) {
        printf("underflow");
        return -1;
    } else {
        int item = stack[top];
        top--;
        return item;
    }
}

중요한 부분은 다음과 같습니다.

top++;
stack[top] = item;

이것이 push다.

item = stack[top];
top--;

이것이 pop입니다.

스택 코드 추적

다음 연산을 해 보겠습니다.

push(10)
push(20)
push(30)
pop()
push(40)
pop()
pop()

top = -1

하나씩 살펴보겠습니다.

30, 40, 20

이런 문제는 손으로 스택을 그리면 쉽습니다.

스택의 응용

스택은 여러 곳에 쓰입니다.

자료구조 범위에도 스택의 응용으로 미로 찾기, 서브루틴 주소 복귀가 포함됩니다.

함수 호출과 스택

2장 3절에서 재귀를 배웠습니다.

int f(int n) {
    if (n == 1) return 1;
    return n + f(n - 1);
}

f(4)를 호출하면 내부적으로 호출 정보가 쌓입니다.

f(4)
f(3)
f(2)
f(1)

가장 나중에 호출된 f(1)이 먼저 끝납니다.

f(1) 종료
f(2) 종료
f(3) 종료
f(4) 종료

이 구조가 바로 스택입니다.

나중에 호출된 함수가 먼저 끝납니다.

그래서 함수 호출과 재귀는 스택 구조와 밀접합니다.

큐

큐란?

이제 큐로 넘어갑니다.

큐는 한쪽 끝에서는 삽입하고, 다른 쪽 끝에서는 삭제하는 자료구조입니다.

쉽게 말하면 줄서기입니다.

먼저 줄 선 사람이 먼저 나갑니다.

그래서 큐의 핵심은 이것입니다.

FIFO = First In First Out

먼저 들어온 것이 먼저 나갑니다.

enqueue A
enqueue B
enqueue C

A → B → C

순서로 나옵니다.

큐의 기본 연산

큐의 대표 연산은 다음과 같습니다.

enqueue = 줄 뒤에 서기
dequeue = 줄 앞에서 나가기

큐의 front와 rear

큐에서는 두 위치가 중요합니다.

front = 삭제되는 쪽
rear = 삽입되는 쪽

front = -1
rear = -1

또는 구현 방식에 따라 다르게 잡기도 합니다.

배열 큐에서 값을 넣으면 rear가 움직입니다.

enqueue 10 → rear 증가 → 10 저장
enqueue 20 → rear 증가 → 20 저장

값을 꺼내면 front가 움직입니다.

dequeue → front 증가 → 앞쪽 값 꺼냄

선형 큐

배열로 큐를 만들면 보통 이렇게 생깁니다.

int queue[5];
int front = -1;
int rear = -1;

enqueue(10):

rear = 0
queue[0] = 10

enqueue(20):

rear = 1
queue[1] = 20

enqueue(30):

rear = 2
queue[2] = 30

인덱스: 0   1   2   3   4
값:    10  20  30
front = -1
rear = 2

dequeue()를 하면 front가 증가하면서 앞쪽 값이 나옵니다.

front = 0
queue[0] 반환 → 10

```ascii title="다시 dequeue()" front = 1 queue[1] 반환 → 20

---

### 선형 큐의 문제점

선형 큐는 배열 앞쪽에 빈칸이 생겨도 재사용하기 어렵습니다.

예를 들어 크기 5인 큐가 있습니다.

```text
인덱스: 0   1   2   3   4
값:    10  20  30  40  50
front = -1
rear = 4

이제 dequeue()를 두 번 해서 10, 20을 꺼냈습니다.

인덱스: 0   1   2   3   4
값:    _   _   30  40  50
front = 1
rear = 4

앞쪽 0, 1번 칸은 비었지만 rear가 이미 끝에 있습니다.

단순한 선형 큐 구현에서는 더 이상 뒤에 넣을 공간이 없다고 판단할 수 있습니다.

실제로는 앞쪽 빈칸이 있지만 rear가 끝에 도달했습니다.

이 문제를 해결하는 것이 원형 큐입니다.

원형 큐

원형 큐는 배열의 끝과 처음을 연결해서 원처럼 사용하는 큐입니다.

0 → 1 → 2 → 3 → 4 → 다시 0

즉, rear가 마지막 인덱스에 도달한 뒤 다음 위치로 이동할 때 0번으로 돌아갑니다.

이때 나머지 연산 %를 씁니다.

rear = (rear + 1) % SIZE;
front = (front + 1) % SIZE;

```text title="예를 들어 SIZE = 5일 때" (4 + 1) % 5 = 0

그래서 4 다음은 0이 됩니다.

자료구조 출제범위에도 큐 단원에 <b>원형 큐</b>가 포함되어 있습니다.

---

### 원형 큐의 핵심 조건

원형 큐에서는 보통 한 칸을 비워 두는 방식으로 가득 참을 판단합니다.

```text title="대표 조건"
공백 상태: front == rear
포화 상태: (rear + 1) % SIZE == front

왜 한 칸을 비워 두냐?

공백과 포화를 구분하기 위해서입니다.

만약 모든 칸을 다 쓰면 front == rear가 공백인지 포화인지 헷갈릴 수 있습니다.

그래서 한 칸을 비워두는 구현이 많이 나옵니다.

원형 큐 예시

크기 5인 원형 큐가 있다고 가정하겠습니다.

인덱스: 0 1 2 3 4

front = 0
rear = 0

enqueue(10):

rear = (0 + 1) % 5 = 1
queue[1] = 10

enqueue(20):

rear = 2
queue[2] = 20

dequeue():

front = (0 + 1) % 5 = 1
queue[1] 반환 → 10

이런 식으로 front와 rear가 원형으로 순환합니다.

큐 연산의 시간 복잡도

큐의 기본 연산도 빠릅니다.

큐도 스택처럼 중간 데이터를 직접 다루는 구조가 아닙니다.

큐는 앞과 뒤만 다룹니다.

큐의 응용

큐는 “순서대로 처리”해야 하는 곳에 많이 쓰입니다.

운영체제에서도 큐 개념이 매우 중요합니다. 예를 들어 운영체제 범위에는 프로세스 상태, 프로세스 제어, 스케줄링 알고리즘이 포함되어 있는데, 준비 상태의 프로세스들을 관리할 때 큐 구조가 자주 사용됩니다.

스택과 큐 비교

스택 = 나중 것이 먼저
큐 = 먼저 것이 먼저

데크

데크는 Double Ended Queue의 줄임말입니다.

양쪽 끝에서 삽입과 삭제가 모두 가능한 큐

뒤에서 넣고 앞에서 뺍니다.

앞에서도 넣고 뺄 수 있고,
뒤에서도 넣고 뺄 수 있습니다.

연산은 이렇게 볼 수 있습니다.

자료구조 출제범위에도 큐 단원에 데크가 포함되어 있습니다.

수식 표기법

표기법 개요

이제 후위표기식으로 넘어갑니다.

수식 표기법에는 세 가지가 있습니다.

중위표기식
전위표기식
후위표기식

예를 들어 우리가 평소에 쓰는 식은 이것입니다.

A + B

이것은 중위표기식입니다.

왜냐하면 연산자 +가 피연산자 A와 B 사이에 있기 때문입니다.

중위표기식

중위표기식은 사람이 가장 익숙한 방식입니다.

A + B
A + B * C
(A + B) * C

사람이 읽기 쉽습니다.

컴퓨터가 계산할 때 연산자 우선순위와 괄호를 고려해야 합니다.

A + B * C

는 +보다 *를 먼저 해야 합니다.

A + (B * C)

이런 규칙을 컴퓨터가 따져야 합니다.

후위표기식

후위표기식은 연산자를 피연산자 뒤에 쓰는 방식입니다.

A + B

A B +

A + B * C

A B C * +

왜냐하면 B * C를 먼저 계산하고, 그 결과에 A를 더하기 때문입니다.

B C * → B*C
A (B*C) + → A + B*C

괄호가 필요 없습니다.
연산자 우선순위를 따로 고민하지 않아도 됩니다.
스택으로 계산하기 쉽습니다.

자료구조 출제범위에도 후위표기식의 연산, 중위표기를 후위표기로 변환이 포함되어 있습니다.

전위표기식

전위표기식은 연산자를 앞에 쓰는 방식입니다.

A + B

+ A B

A + B * C

+ A * B C

전위표기식도 괄호 없이 표현할 수 있지만, 자료구조 시험에서는 보통 후위표기식이 더 자주 중요하게 나옵니다.

표기법 비교

핵심은 연산자의 위치입니다.

중위 = 가운데
전위 = 앞
후위 = 뒤

후위표기식 계산

후위표기식 계산 방법

후위표기식은 스택으로 계산합니다.

1. 왼쪽에서 오른쪽으로 읽습니다.
2. 피연산자를 만나면 스택에 push합니다.
3. 연산자를 만나면 스택에서 피연산자 두 개를 pop합니다.
4. 두 값을 연산합니다.
5. 결과를 다시 push합니다.
6. 끝까지 반복합니다.
7. 마지막에 스택에 남은 값이 결과입니다.

연산자를 만나면 두 개를 꺼냅니다.

그리고 순서도 중요합니다.

예를 들어 -, /는 순서가 바뀌면 결과가 달라집니다.

스택에서 먼저 pop한 값이 오른쪽 피연산자입니다.

right = pop()
left = pop()
left 연산자 right

후위표기식 계산 예제 1

2 3 +

계산은 다음과 같습니다.

5

2 3 + = 2 + 3 = 5

후위표기식 계산 예제 2

2 3 4 * +

왼쪽부터 읽습니다.

14

2 + 3 * 4

입니다.

곱셈이 먼저 계산됩니다.

후위표기식 계산 예제 3

5 2 - 3 *

계산은 다음과 같습니다.

9

(5 - 2) * 3

입니다.

후위표기식 계산에서 순서 주의

5 2 -

right = pop() → 2
left = pop() → 5
left - right = 5 - 2 = 3

결과는 3입니다.

2 - 5 = -3

틀립니다.

두 번째로 꺼낸 값 연산자 첫 번째로 꺼낸 값

입니다.

left = 나중에 pop한 값
right = 먼저 pop한 값

중위표기식 변환

중위표기식을 후위표기식으로 바꾸기

이번에는 수식을 변환해 보겠습니다.

A + B

A B +

간단한 것은 쉽습니다.

하지만 이런 식은?

A + B * C

A B C * +

입니다.

(A + B) * C

A B + C *

연산자 우선순위

후위표기식 변환에서는 연산자 우선순위가 중요합니다.

거듭제곱 > 곱셈/나눗셈 > 덧셈/뺄셈

C언어에서는 거듭제곱 연산자 <b>가 기본 연산자로 존재하지 않지만, 자료구조 표기식 문제에서는 </b>가 거듭제곱 의미로 등장할 수 있습니다. 자료구조 예시문제에도 A/B**C-D*(E+F)/G를 후위표기로 바꾸는 문제가 나옵니다.

중위 → 후위 변환 기본 규칙

스택을 이용해서 변환할 때 기본 규칙은 다음과 같습니다.

1. 피연산자는 바로 출력합니다.
2. 여는 괄호 '('는 스택에 push합니다.
3. 닫는 괄호 ')'를 만나면 '('가 나올 때까지 pop해서 출력합니다.
4. 연산자를 만나면 스택 위의 연산자와 우선순위를 비교합니다.
5. 스택 위 연산자의 우선순위가 높거나 같으면 pop해서 출력합니다.
6. 현재 연산자를 push합니다.
7. 입력이 끝나면 스택에 남은 연산자를 모두 pop해서 출력합니다.

단, 거듭제곱처럼 오른쪽 결합인 연산자는 예외가 있을 수 있지만, 기본 시험 문제에서는 보통 우선순위 중심으로 처리하면 됩니다.

변환 예제 1: A + B * C

A + B * C

변환은 다음과 같습니다.

A B C * +

ABC*+

변환 예제 2: (A + B) * C

(A + B) * C

변환은 다음과 같습니다.

A B + C *

AB+C*

변환 예제 3: A * B + C

A * B + C

곱셈이 덧셈보다 먼저입니다.

A B * C +

A * B를 먼저 처리 → A B *
그 결과에 C를 더함 → A B * C +

변환 예제 4: A + B - C

A + B - C

+와 -는 우선순위가 같습니다. 왼쪽에서 오른쪽으로 계산합니다.

(A + B) - C

A B + C -

AB+C-

시험 예시형 문제

자료구조 예시문제에 다음 중위표기식을 후위표기로 바꾸는 문제가 있습니다.

A/B**C-D*(E+F)/G

ABC**/DEF+*G/-

왜 그런지 흐름을 살펴보겠습니다.

A / B**C - D * (E + F) / G

(A / (B**C)) - ((D * (E + F)) / G)

B**C → B C **
A / (B**C) → A B C ** /
E + F → E F +
D * (E + F) → D E F + *
(D * (E + F)) / G → D E F + * G /
전체 빼기 → A B C ** / D E F + * G / -

ABC**/DEF+*G/-

입니다.

이 문제는 연산자 우선순위와 괄호를 제대로 봐야 합니다.

후위표기식 계산 예제 4

6 2 / 3 4 + *

계산은 다음과 같습니다.

21

(6 / 2) * (3 + 4)

입니다.

스택과 큐의 활용

괄호 검사와 스택

스택은 괄호 검사에도 쓰입니다.

( A + B ) * C

괄호가 맞습니다.

( A + B * C

괄호가 닫히지 않았습니다.

1. 여는 괄호를 만나면 push
2. 닫는 괄호를 만나면 pop
3. 닫는 괄호가 나왔는데 스택이 비어 있으면 오류
4. 끝났는데 스택에 여는 괄호가 남아 있으면 오류
5. 끝났을 때 스택이 비어 있으면 정상

( ( ) )

( → push
( → push
) → pop
) → pop
끝 → 스택 비어 있음 → 정상

미로 찾기와 스택

미로 찾기에서도 스택을 쓸 수 있습니다.

길을 가다가 막히면 이전 위치로 되돌아가야 합니다.

이때 지나온 길을 스택에 저장합니다.

현재 위치 push
갈 수 있는 곳으로 이동
막히면 pop해서 이전 위치로 돌아감

이 방식은 깊이 우선 탐색, DFS와도 연결됩니다.

스택은 “되돌아가기”가 필요한 문제에 잘 맞습니다.

스택 = 최근 위치로 되돌아가기 좋음

큐와 BFS 미리보기

큐는 그래프 탐색 중 너비 우선 탐색, BFS에 쓰입니다.

BFS는 가까운 곳부터 차례대로 방문합니다.

시작 정점을 큐에 넣습니다.
큐에서 하나 꺼냅니다.
그 정점의 이웃들을 큐에 넣습니다.
다시 큐에서 꺼냅니다.

큐를 쓰기 때문에 먼저 발견한 정점이 먼저 처리됩니다.

그래서 BFS는 가까운 거리부터 퍼져 나가는 탐색이 됩니다.

그래프와 BFS는 3장 4절에서 본격적으로 다룹니다.

다중 스택과 다중 큐

출제범위에는 다중 스택과 다중 큐도 있습니다.

다중 스택

하나의 배열 공간 안에 여러 개의 스택을 운영하는 방식입니다.

예를 들어 배열 하나를 양쪽에서 나눠 쓸 수 있습니다.

왼쪽에서는 스택 1이 오른쪽으로 증가
오른쪽에서는 스택 2가 왼쪽으로 증가

이렇게 하면 공간을 더 유연하게 쓸 수 있습니다.

다중 큐

하나의 배열이나 메모리 공간 안에서 여러 큐를 운영하는 방식입니다.

예를 들어 운영체제에서 우선순위별로 여러 대기 큐를 둘 수 있습니다.

높은 우선순위 큐
중간 우선순위 큐
낮은 우선순위 큐

지금은 깊게 구현하지 않고, 개념만 잡으면 됩니다.

다중 스택 = 여러 스택을 한 공간에서 운영
다중 큐 = 여러 큐를 한 공간에서 운영

자주 혼동되는 출제 포인트

혼동 포인트 1. 스택은 LIFO다

A, B, C 순서로 넣으면 C, B, A 순서로 나옵니다.

FIFO와 헷갈리면 안 됩니다.

혼동 포인트 2. 큐는 FIFO다

A, B, C 순서로 넣으면 A, B, C 순서로 나옵니다.

LIFO와 헷갈리면 안 됩니다.

혼동 포인트 3. pop에서 빈 스택이면 언더플로

비었는데 꺼내기 = underflow

overflow

혼동 포인트 4. 스택의 top은 맨 위를 가리킵니다

push → top 증가
pop → top 감소

혼동 포인트 5. 큐는 front와 rear가 있습니다

front = 삭제 쪽
rear = 삽입 쪽

혼동 포인트 6. 원형 큐는 나머지 연산을 씁니다

rear = (rear + 1) % SIZE;
front = (front + 1) % SIZE;

끝에 가면 다시 처음으로 돌아갑니다.

혼동 포인트 7. 후위표기식은 연산자가 뒤에 옵니다

A + B → A B +

혼동 포인트 8. 후위표기식 계산에서 pop 순서 조심

right = pop()
left = pop()
left 연산자 right

-와 /에서 특히 중요합니다.

혼동 포인트 9. 중위표기를 후위표기로 바꿀 때 우선순위 조심

A + B * C → A B C * +

A B + C *가 아닙니다.

혼동 포인트 10. 괄호는 우선순위를 강제로 바꿉니다

(A + B) * C → A B + C *

괄호 안을 먼저 처리합니다.

이번 절의 핵심 정리

스택

LIFO = Last In First Out
나중에 들어온 것이 먼저 나감

push, pop, peek

overflow = 가득 찼는데 push
underflow = 비었는데 pop

큐

FIFO = First In First Out
먼저 들어온 것이 먼저 나감

enqueue, dequeue

front = 삭제 쪽
rear = 삽입 쪽

원형 큐

배열의 끝과 처음을 연결해서 사용

rear = (rear + 1) % SIZE;
front = (front + 1) % SIZE;

데크

양쪽 끝에서 삽입과 삭제가 모두 가능

수식 표기법

중위표기식 = A + B
전위표기식 = + A B
후위표기식 = A B +

후위표기식 계산

피연산자 → push
연산자 → 두 개 pop 후 계산, 결과 push

중위 → 후위 핵심

A + B * C → A B C * +
(A + B) * C → A B + C *

핵심 한 문장

이번 절의 핵심을 한 문장으로 정리하면 다음과 같습니다.

스택은 LIFO 구조로 최근 데이터를 먼저 처리하고, 큐는 FIFO 구조로 먼저 들어온 데이터를 먼저 처리하며, 후위표기식은 스택을 이용해 괄호 없이 수식을 계산하기 쉽게 만든 표현 방식입니다.

스택 = 나중 것 먼저
큐 = 먼저 것 먼저
후위표기식 = 연산자가 뒤

확인 문제

문제 1

스택의 특징으로 알맞은 것은?

① 먼저 들어온 것이 먼저 나갑니다 ② 나중에 들어온 것이 먼저 나갑니다 ③ 중간 원소만 삭제합니다 ④ 항상 정렬된 상태를 유지합니다

문제 2

스택의 삽입 연산은?

① pop ② push ③ enqueue ④ dequeue

문제 3

스택이 비어 있는데 삭제 연산을 수행하려 할 때 발생하는 것은?

① 오버플로 ② 언더플로 ③ 캐시 미스 ④ 인터럽트

문제 4

큐의 특징으로 알맞은 것은?

① LIFO ② FIFO ③ FILO만 가능 ④ 무조건 역순 출력

문제 5

큐에서 삽입이 일어나는 쪽은?

① front ② rear ③ top ④ base

문제 6

원형 큐에서 다음 위치를 계산할 때 자주 사용하는 연산자는?

① + ② % ③ && ④ ==

문제 7

중위표기식 A + B의 후위표기식은?

① + A B ② A + B ③ A B + ④ B A +

문제 8

중위표기식 A + B * C의 후위표기식은?

① A B + C * ② A B C * + ③ A B * C + ④ + A * B C

문제 9

중위표기식 (A + B) * C의 후위표기식은?

① A B + C * ② A B C * + ③ A B * C + ④ * A + B C

문제 10

후위표기식 2 3 4 * +의 계산 결과는?

① 9 ② 14 ③ 20 ④ 24

문제 11

후위표기식 5 2 - 3 *의 계산 결과는?

① 3 ② 7 ③ 9 ④ 15

문제 12

다음 중 스택의 대표 응용으로 가장 알맞은 것은?

① 프린터 대기열 ② 함수 호출과 복귀 주소 저장 ③ CPU 캐시 매핑 ④ 디스크 조각 모음

정답과 해설은 절별 확인문제 정답해설에서 확인합니다.

다음 3장 3절은 연결리스트, 트리, 이진트리 순회입니다. 3장 2절까지는 배열 기반 자료구조를 봤고, 3장 3절부터는 포인터로 노드를 연결하는 자료구조로 넘어갑니다.