[임베디드기사 실기 20부작 18편] Stack, Queue, Tree와 전위·중위·후위식 — 자료구조와 수식 표기법 완전 정리
임베디드기사 실기에서는 C 코드, 포인터, 메모리 문제뿐 아니라 자료구조와 수식 표기법을 결합한 문제도 충분히 나올 수 있습니다. 특히 Stack과 Queue의 동작 원리, Tree 순회, 이진 탐색 트리, Infix·Prefix·Postfix 변환과 계산은 서로 따로 보이지만 실제로는 하나의 연결된 주제입니다.
이번 편에서는 단순 정의 암기보다 “왜 Stack을 쓰는가, 왜 Postfix는 괄호가 필요 없는가, Tree 순회 순서와 Prefix/Postfix가 왜 연결되는가”를 중심으로 정리합니다. 나중에 책으로 묶었을 때 자료구조 장의 핵심 파트가 되도록 예제와 풀이 과정을 충분히 넣었습니다.
Stack은 LIFO(Last In, First Out) 구조입니다. 접시를 쌓아 두었다가 가장 위의 접시부터 꺼내는 모습을 떠올리면 쉽습니다.
대표 연산은 push와 pop입니다.
push(10)
push(20)
push(30)
Stack Top
30 ← 먼저 pop
20
10
Stack은 함수 호출, 재귀호출, 수식 계산, 괄호 검사, DFS, Interrupt Context 저장 등 매우 다양한 곳에서 사용됩니다.
Overflow는 Stack이 가득 찼는데 더 Push하려는 상태이고, Underflow는 비어 있는데 Pop하려는 상태입니다.
임베디드 시스템에서는 Task마다 Stack 크기가 제한되는 경우가 많기 때문에 재귀 호출이나 큰 지역 배열, 깊은 함수 호출 체인은 Stack Overflow의 원인이 될 수 있습니다.
Queue는 FIFO(First In, First Out) 구조입니다. 먼저 줄을 선 사람이 먼저 서비스를 받는 대기열과 같습니다.
대표 연산은 enqueue와 dequeue입니다.
Front → [10] [20] [30] ← Rear
dequeue() → 10
enqueue(40)
Front → [20] [30] [40] ← Rear
일반 배열 Queue에서 Rear가 배열 끝에 도달하면 앞쪽 공간이 비어 있어도 더 이상 데이터를 넣지 못하는 문제가 생길 수 있습니다. 이를 해결하기 위해 Circular Queue를 사용합니다.
Rear와 Front가 배열의 끝에 도달하면 다시 처음 위치로 돌아가도록 구성합니다. 보통 다음과 같은 식을 사용합니다.
rear = (rear + 1) % SIZE;
front = (front + 1) % SIZE;
Queue 자료는 운영체제 Scheduling Queue, UART 수신 Buffer, Producer-Consumer Buffer, Message Queue와 연결해 이해하면 실무적으로도 기억하기 쉽습니다.
| 항목 | Stack | Queue |
|---|---|---|
| 원리 | LIFO | FIFO |
| 삽입 | push | enqueue |
| 삭제 | pop | dequeue |
| 대표 활용 | 함수 호출, DFS, 수식 계산 | Scheduling, BFS, Buffer |
Tree는 Node와 Edge로 구성되는 비선형 자료구조입니다. 최상위 Node를 Root라고 하고, 각 Node는 Parent와 Child 관계를 가질 수 있습니다.
대표 용어는 Root, Parent, Child, Sibling, Leaf, Depth, Height입니다.
A
/ \
B C
/ \
D E
A는 Root, D와 E는 Leaf, B와 C는 A의 Child입니다.
Binary Tree는 각 Node가 최대 두 개의 Child를 갖는 Tree입니다. 왼쪽 Child와 오른쪽 Child로 구분합니다.
이 구조는 Binary Search Tree, Heap, Expression Tree 등 여러 중요한 자료구조의 기반이 됩니다.
BST(Binary Search Tree)는 다음 규칙을 따릅니다.
왼쪽 Subtree의 모든 값은 Root보다 작고, 오른쪽 Subtree의 모든 값은 Root보다 큽니다.
4
/ \
2 6
/ \ / \
1 3 5 7
BST를 Inorder Traversal하면 값이 오름차순으로 출력됩니다.
이 특징은 2025년 실기 기출의 Tree 문제와도 연결되는 핵심 포인트입니다.
Tree 순회에는 대표적으로 Preorder, Inorder, Postorder가 있습니다.
Preorder = Root → Left → Right
Inorder = Left → Root → Right
Postorder = Left → Right → Root
A
/ \
B C
/ \
D E
Preorder: A → B → D → E → C
Inorder: D → B → E → A → C
Postorder: D → E → B → C → A
암기 포인트는 Root가 어디에 나오느냐입니다. Preorder는 Root가 앞, Inorder는 가운데, Postorder는 뒤에 옵니다.
수식 표기법도 Tree Traversal과 매우 밀접합니다.
| 표기법 | 형태 | 예 |
|---|---|---|
| Infix | 피연산자 연산자 피연산자 | A + B |
| Prefix | 연산자 피연산자 피연산자 | + A B |
| Postfix | 피연산자 피연산자 연산자 | A B + |
Expression Tree에서 Operator가 내부 Node, Operand가 Leaf라면 다음 관계가 성립합니다.
Preorder Traversal → Prefix
Inorder Traversal → Infix
Postorder Traversal → Postfix
즉 Tree 순회와 수식 표기법은 사실 같은 구조를 다른 방식으로 읽는 것입니다.
Infix:
(A + B) * C
Expression Tree는 다음과 같습니다.
*
/ \
+ C
/ \
A B
Prefix: * + A B C
Postfix: A B + C *
곱셈이 덧셈보다 우선순위가 높으므로 실제 구조는 A + (B×C)입니다.
+
/ \
A *
/ \
B C
Prefix: + A * B C
Postfix: A B C * +
Postfix에서는 연산자가 항상 피연산자 뒤에 나타나기 때문에 연산 순서가 식 자체에 포함되어 있습니다.
예를 들어 A B + C *는 먼저 A와 B를 더하고, 그 결과와 C를 곱한다는 의미가 명확합니다. 그래서 Infix처럼 괄호나 연산자 우선순위 규칙을 별도로 적용할 필요가 없습니다.
Postfix 표현식은 왼쪽에서 오른쪽으로 읽으면서 Operand는 Stack에 Push하고 Operator를 만나면 두 값을 Pop해 연산합니다.
예를 들어 다음 식을 계산해 보겠습니다.
2 3 + 4 *
① 2 Push
② 3 Push
③ + : 3과 2를 Pop → 2+3=5 → 5 Push
④ 4 Push
⑤ * : 4와 5를 Pop → 5×4=20
최종 결과는 20입니다.
덧셈과 곱셈은 순서를 바꿔도 결과가 같지만, 뺄셈과 나눗셈은 다릅니다.
8 3 -
Operator '-'를 만나면 먼저 Pop한 3이 오른쪽 Operand, 다음에 Pop한 8이 왼쪽 Operand입니다.
따라서 계산은 8 - 3 = 5입니다.
Prefix 계산은 Postfix와 반대로 오른쪽에서 왼쪽으로 읽는 방식으로 처리할 수 있습니다.
Operand는 Stack에 넣고, Operator를 만나면 두 값을 꺼내 연산합니다.
즉 다음처럼 기억하면 좋습니다.
Postfix = 왼쪽 → 오른쪽
Prefix = 오른쪽 → 왼쪽
Binary Operator만 있다고 가정하면, 정상적인 Postfix 표현식은 모든 연산이 끝난 뒤 Stack에 정확히 하나의 값만 남아야 합니다.
예를 들어 다음 표현을 보겠습니다.
a b c + * d - 1
마지막의 1은 연산자가 없어 Stack에 하나 더 남게 됩니다. 따라서 Binary Operator 기준으로는 불완전한 Postfix 식입니다.
예를 들어 a(b+c)-d-1이라면 올바른 Postfix는 다음과 같습니다.
a b c + * d - 1 -
자료구조는 서로 연결됩니다.
DFS(Depth First Search)는 Stack 또는 Recursion을 사용하고, BFS(Breadth First Search)는 Queue를 사용합니다.
무가중치 Graph에서 최단 경로 탐색에는 BFS가 적합하고, 깊게 탐색하면서 Backtracking이 필요한 문제에는 DFS가 적합합니다.
자료구조 문제를 시험용으로만 생각하면 기억이 오래가지 않습니다. 임베디드 시스템에서는 다음처럼 실제 사용됩니다.
Stack: 함수 호출, Context Save, Interrupt 진입, Parser, State Backtracking
Queue: UART RX Buffer, Message Queue, Task Scheduling, Producer-Consumer
Tree: 설정 데이터, Search Structure, Expression Parser, File/Directory 구조
자료구조 문제는 다음 순서로 푸는 것이 좋습니다.
① Stack인지 Queue인지 먼저 판별
② Push/Pop 또는 Enqueue/Dequeue 순서를 적음
③ Tree라면 Root·Left·Right 구조를 그림
④ Traversal 문제는 Root 위치 기준으로 판단
⑤ Infix는 먼저 연산자 우선순위와 괄호를 확인
⑥ Prefix/Postfix 변환은 Expression Tree를 그리면 안전
⑦ Postfix 계산은 Stack 상태를 한 단계씩 기록
문제 1. Stack과 Queue의 차이를 설명하시오.
모범답안: Stack은 마지막에 입력된 데이터가 먼저 출력되는 LIFO 구조이고, Queue는 먼저 입력된 데이터가 먼저 출력되는 FIFO 구조이다. Stack은 push/pop, Queue는 enqueue/dequeue 연산을 사용한다.
문제 2. Binary Search Tree를 Inorder Traversal했을 때의 특징은?
모범답안: BST에서 Inorder Traversal은 Left → Root → Right 순서로 방문하며, 결과가 Key의 오름차순으로 출력된다.
문제 3. Infix (A+B)*C를 Prefix와 Postfix로 변환하시오.
답:
Prefix = * + A B C
Postfix = A B + C *
문제 4. Infix A+B*C를 Postfix로 변환하시오.
답: A B C * +
문제 5. Postfix 2 3 + 4 *의 계산 결과는?
답: 20
문제 6. DFS와 BFS가 사용하는 대표 자료구조는?
답: DFS는 Stack/Recursion, BFS는 Queue를 사용한다.
Stack = LIFO / push / pop
Queue = FIFO / enqueue / dequeue
Circular Queue = modulo로 배열 재사용
Preorder = Root → Left → Right
Inorder = Left → Root → Right
Postorder = Left → Right → Root
Prefix = Operator가 앞
Infix = Operator가 가운데
Postfix = Operator가 뒤
Preorder = Prefix
Inorder = Infix
Postorder = Postfix
Postfix 계산 = 왼쪽→오른쪽 + Stack
Prefix 계산 = 오른쪽→왼쪽 + Stack
BST Inorder = 오름차순
Stack, Queue, Tree, Prefix/Postfix를 각각 따로 암기하면 금방 헷갈립니다. 하지만 아래의 연결 관계를 기억하면 훨씬 쉬워집니다.
Stack → 함수호출·수식계산·DFS
Queue → Buffer·Scheduling·BFS
Tree Traversal → Prefix/Infix/Postfix
Postfix → Stack으로 계산
실기에서는 정답만 맞히는 것보다 풀이과정을 빠르게 재현할 수 있어야 합니다. 따라서 Tree 그림과 Stack 상태를 직접 손으로 그리는 연습이 특히 중요합니다.
19편 — UML, Use Case, Aggregation, White/Black Box Test: 소프트웨어 설계와 검증 핵심 정리
#임베디드기사 #임베디드기사실기 #자료구조 #Stack #Queue #CircularQueue #Tree #BinaryTree #BST #TreeTraversal #Preorder #Inorder #Postorder #Prefix #Infix #Postfix #DFS #BFS #ExpressionTree #자격증공부