II-3 Stack·Queue 연산과 ADT 접근 규칙 — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
Stack은 top만, Queue는 front와 rear만 노출하는 사용 계약입니다. 내부가 배열이어도 Stack ADT가 중간 원소 접근 연산을 제공하는 것은 아닙니다.
과자 자판기 내부 선반이 보여도 사용자는 정해진 투입·배출구만 이용하는 것과 같습니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. 연산표를 쓰고 Queue [y]에 x를 enqueue한 작은 반례로 선택지 D를 확인합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
Stack은 top만, Queue는 front와 rear만 노출하는 사용 계약입니다. 내부가 배열이어도 Stack ADT가 중간 원소 접근 연산을 제공하는 것은 아닙니다.
이 문항에서 가장 먼저 붙잡을 문장은 'Stack push/pop은 보통 \(O(1)\)O(1)이다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- Stack push/pop은 보통 \(O(1)\)
O(1)이다. - 연산표를 쓰고 Queue [y]에 x를 enqueue한 작은 반례로 선택지 D를 확인합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, Stack push/pop은 보통 \(O(1)\)O(1)이다. 둘째, Queue enqueue/dequeue도 적절한 구현에서는 \(O(1)\)O(1)이다.
셋째, Stack 중간 접근은 ADT의 기본 연산이 아니다. 넷째, 비어 있지 않은 Queue에서는 새 원소보다 기존 front가 먼저 나온다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- Stack push/pop은 보통 \(O(1)\)
O(1)이다. - Queue enqueue/dequeue도 적절한 구현에서는 \(O(1)\)
O(1)이다. - Stack 중간 접근은 ADT의 기본 연산이 아니다.
- 비어 있지 않은 Queue에서는 새 원소보다 기존 front가 먼저 나온다.
개념 3 · 강의 정의를 초보자 언어로 해체
스택(Stack)은 접시 더미와 같다. 위에 올린 것을 위에서 먼저 꺼낸다. 큐(Queue)는 줄과 같아서 먼저 선 사람이 먼저 나간다. 연결 리스트(linked list)는 배열처럼 칸 번호로 바로 뛰어가는 구조가 아니라, 노드가 다음 노드를 가리키는 길이다. ADT는 '메뉴판'이고 구현(implementation)은 '주방 설비'다.
스택 ADT(Stack ADT)는 new, isEmpty, push, pop을 제공하고 후입선출(LIFO)을 만족한다. 큐 ADT(Queue ADT)는 new, isEmpty, enqueue, dequeue를 제공하고 선입선출(FIFO)을 만족한다. 단일 연결 리스트(singly linked list, einfach verkettete Liste)의 각 원소는 다음 원소를 가리키는 next 포인터를 가지지만 이전 원소를 가리키는 prev 포인터는 없다. 이중 연결 리스트(doubly linked list, doppelt verkettete Liste)는 next와 prev를 모두 가져 앞뒤 순회가 가능하다. 추상 자료형(ADT, abstrakter Datentyp)은 가능한 값과 연산 및 행동을 설명하며, 배열인지 리스트인지 같은 저장 방식은 별도의 구현 문제다.
수식으로 정확히 쓰기
핵심 규칙스택의 push·pop은 보통 \(O(1)\)O(1)이다. 큐의 enqueue·dequeue는 원형 배열 또는 front/rear 연결 리스트 구현에서 보통 \(O(1)\)O(1)이다. 연결 리스트에서 값 탐색·인덱스형 접근은 \(\Theta(n)\)Θ(n)이고, 위치를 이미 알고 있을 때 포인터 갱신으로 하는 삽입·삭제는 \(O(1)\)O(1)이다.
이 절에서 꼭 기억할 것
- 원소 삽입 순서와 제거 순서를 작은 예시로 추적할 수 있어야 합니다.
- next 포인터와 prev 포인터의 차이를 알아야 한다.
- \(O(1)\)
O(1)과 \(\Theta(n)\)Θ(n)의 차이를 '입력 크기에 따라 비용이 변하는가'로 판단할 수 있어야 한다.
개념 4 · 성립 조건·불변식·경계 사례
스택 불변식(Stack invariant)에 따르면 pop은 아직 제거되지 않은 원소 중 가장 최근에 push된 원소를 반환한다. 큐 불변식(Queue invariant)에 따르면 dequeue는 아직 제거되지 않은 원소 중 가장 오래전에 enqueue된 원소를 반환한다. 단일 연결 리스트는 현재 노드에서 next 방향으로 갈 수 있지만 prev 포인터나 보조 정보 없이는 뒤로 갈 수 없다. 같은 큐 ADT도 원형 배열(circular array), 단일 연결 리스트 또는 두 스택(two-stack) 방식 등 여러 구현을 가질 수 있다.
빈 스택이나 큐에서 pop 또는 dequeue를 하면 명세에 따라 언더플로(underflow)나 오류가 발생한다. enqueue(x) 직후 dequeue()가 x를 반환하는 것은 enqueue 전에 큐가 비어 있었을 때뿐이며, 그렇지 않으면 더 오래된 맨 앞 원소가 먼저 나온다. 단일 연결 리스트 끝에 추가하는 비용은 표현 방식에 따라 달라서 tail 포인터가 있으면 \(O(1)\)O(1)이지만 head 포인터만 있으면 순회가 필요할 수 있다. 또한 이미 알고 있는 노드를 삭제하는 것과 값으로 삭제하는 것은 다르며, 값으로 삭제하려면 이전 노드를 찾아야 할 수 있다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
강의 03의 실행시간 표에서 스택의 push·pop과 큐의 enqueue·dequeue는 보통 \(\Theta(1)\)Θ(1)이다. 연결 리스트에서 값 탐색은 \(\Theta(n)\)Θ(n)이며 인덱스처럼 임의 위치에 곧바로 접근하는 것은 기본 직접 연산이 아니다. 이미 알고 있는 노드·위치에서 삽입·삭제는 \(\Theta(1)\)Θ(1)일 수 있지만, 값이나 이전 노드를 찾는 데는 \(\Theta(n)\)Θ(n)이 들 수 있다. 단일 연결 노드는 prev가 없으므로 이중 연결 노드보다 포인터 저장 공간이 적다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 B, D입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: B, D
이 절에서 꼭 기억할 것
- ADT 수준에서 허용한 접근과 구현 수준의 저장 방식은 다르다. 배열로 구현한 스택도 스택 ADT를 통해 임의의 중간 원소에 직접 접근하게 해 주지는 않는다.
- 실행시간은 강의 요약표를 떠올린다. D는 큐에 y가 든 상태에서 enqueue(x), dequeue()를 해 보면 y가 나온다는 것으로 확인한다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
Stack·Queue 연산과 ADT 접근 규칙
Stack push/pop은 보통 \(O(1)\)O(1)이다. | Queue enqueue/dequeue도 적절한 구현에서는 \(O(1)\)O(1)이다. | Stack 중간 접근은 ADT의 기본 연산이 아니다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
스택과 큐에 대한 진술 중 정확히 두 개를 고르시오.
핵심 규칙Stack·Queue 연산과 ADT 접근 규칙
핵심 도구를 종이에 꺼낸다
연산표를 쓰고 Queue [y]에 x를 enqueue한 작은 반례로 선택지 D를 확인합니다.
핵심 규칙Stack push/pop은 보통 \(O(1)\)
O(1)이다. | Queue enqueue/dequeue도 적절한 구현에서는 \(O(1)\)O(1)이다. | Stack 중간 접근은 ADT의 기본 연산이 아니다.선택지 A를 독립 판정한다
Stack ADT의 공개 연산은 top 중심입니다. 중간 원소를 보려면 위의 원소를 pop하거나, ADT 밖의 array-index 구현 세부사항을 사용해야 합니다.
\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
고정 배열 stack에서는 top index를 한 칸 이동하고 값을 읽거나 쓰면 됩니다. 동적 resizing은 가끔 비싸지만 강의의 요약표와 표준 구현에서는 push/pop을 전형적으로 \(O(1)\)
O(1)로 봅니다.\[선택지 B = 참\]선택지 B = 참선택지 C를 독립 판정한다
강의 03의 원형 배열 큐와 연결 리스트 큐는 front·rear 포인터를 갱신하여 enqueue·dequeue를 \(O(1)\)
O(1)에 수행합니다. \(O(n)\)O(n)은 비효율적인 구현이나 두 스택 큐의 최악 dequeue 같은 특수한 경우입니다.\[선택지 C = 거짓\]선택지 C = 거짓선택지 D를 독립 판정한다
Queue가 비어 있으면 x가 front이자 rear이므로 바로 dequeue하면 x가 나옵니다. 이미 y가 front에 있었다면 enqueue(x)는 x를 뒤에 붙이고 dequeue는 y를 먼저 반환합니다.
\[선택지 D = 참\]선택지 D = 참정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 B, D입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = B, D\]검증된 정답 = B, D
2. 이 문제를 실제로 끝까지 풀기
Stack은 top만, Queue는 front와 rear만 노출하는 사용 계약입니다. 내부가 배열이어도 Stack ADT가 중간 원소 접근 연산을 제공하는 것은 아닙니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) Stack push/pop은 보통 \(O(1)\)O(1)이다. (2) Queue enqueue/dequeue도 적절한 구현에서는 \(O(1)\)O(1)이다. (3) Stack 중간 접근은 ADT의 기본 연산이 아니다. (4) 비어 있지 않은 Queue에서는 새 원소보다 기존 front가 먼저 나온다.
선택지 A는 거짓입니다. Stack ADT의 공개 연산은 top 중심입니다. 중간 원소를 보려면 위의 원소를 pop하거나, ADT 밖의 array-index 구현 세부사항을 사용해야 합니다. 가장 작은 확인 예는 Stack bottom-to-top [a,b,c]에서 b는 top이 아니므로 pop 없이 표준 pop/top 연산만으로 직접 꺼낼 수 없습니다.
선택지 B는 참입니다. 고정 배열 stack에서는 top index를 한 칸 이동하고 값을 읽거나 쓰면 됩니다. 동적 resizing은 가끔 비싸지만 강의의 요약표와 표준 구현에서는 push/pop을 전형적으로 \(O(1)\)O(1)로 봅니다.
선택지 C는 거짓입니다. 강의 03의 원형 배열 큐와 연결 리스트 큐는 front·rear 포인터를 갱신하여 enqueue·dequeue를 \(O(1)\)O(1)에 수행합니다. \(O(n)\)O(n)은 비효율적인 구현이나 두 스택 큐의 최악 dequeue 같은 특수한 경우입니다. 가장 작은 확인 예는 원형 배열 큐에서 enqueue는 \(\text{rear} = (\text{rear}+1) \bmod \text{MAX}\)rear = (rear+1) mod MAX로 이동한 뒤 저장하고, dequeue는 front만 이동하므로 \(O(1)\)O(1)입니다.
선택지 D는 참입니다. Queue가 비어 있으면 x가 front이자 rear이므로 바로 dequeue하면 x가 나옵니다. 이미 y가 front에 있었다면 enqueue(x)는 x를 뒤에 붙이고 dequeue는 y를 먼저 반환합니다.
따라서 현재 문언에서 참으로 검증된 선택지는 B, D입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. 연산표를 쓰고 Queue [y]에 x를 enqueue한 작은 반례로 선택지 D를 확인합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
Stack ADT의 공개 연산은 top 중심입니다. 중간 원소를 보려면 위의 원소를 pop하거나, ADT 밖의 array-index 구현 세부사항을 사용해야 합니다.
빠른 확인법: Stack bottom-to-top [a,b,c]에서 b는 top이 아니므로 pop 없이 표준 pop/top 연산만으로 직접 꺼낼 수 없습니다.
-
B참 — 정답 후보
고정 배열 stack에서는 top index를 한 칸 이동하고 값을 읽거나 쓰면 됩니다. 동적 resizing은 가끔 비싸지만 강의의 요약표와 표준 구현에서는 push/pop을 전형적으로 \(O(1)\)
O(1)로 봅니다.빠른 확인법: 스택의 push와 pop 연산 시간복잡도는 보통 \(O(1)\)
O(1)이다. -
C거짓
강의 03의 원형 배열 큐와 연결 리스트 큐는 front·rear 포인터를 갱신하여 enqueue·dequeue를 \(O(1)\)
O(1)에 수행합니다. \(O(n)\)O(n)은 비효율적인 구현이나 두 스택 큐의 최악 dequeue 같은 특수한 경우입니다.빠른 확인법: 원형 배열 큐에서 enqueue는 \(\text{rear} = (\text{rear}+1) \bmod \text{MAX}\)
rear = (rear+1) mod MAX로 이동한 뒤 저장하고, dequeue는 front만 이동하므로 \(O(1)\)O(1)입니다. -
D참 — 정답 후보
Queue가 비어 있으면 x가 front이자 rear이므로 바로 dequeue하면 x가 나옵니다. 이미 y가 front에 있었다면 enqueue(x)는 x를 뒤에 붙이고 dequeue는 y를 먼저 반환합니다.
빠른 확인법: Queue에서 enqueue 후 바로 dequeue가 같은 원소를 돌려주는 것은 Queue가 이전에 비어 있었을 때뿐이다.
4. 초보자가 가장 자주 틀리는 이유
- ADT 수준에서 허용한 접근과 구현 수준의 저장 방식은 다르다. 배열로 구현한 스택도 스택 ADT를 통해 임의의 중간 원소에 직접 접근하게 해 주지는 않는다.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
연산표를 쓰고 Queue [y]에 x를 enqueue한 작은 반례로 선택지 D를 확인합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 B, D이다. 핵심 근거: Stack push/pop은 보통 \(O(1)\)O(1)이다. Queue enqueue/dequeue도 적절한 구현에서는 \(O(1)\)O(1)이다. Stack 중간 접근은 ADT의 기본 연산이 아니다. 비어 있지 않은 Queue에서는 새 원소보다 기존 front가 먼저 나온다.
6. 스스로 이해했는지 확인
II-3의 주제를 한 문장으로 설명하면?
정답: Stack은 top만, Queue는 front와 rear만 노출하는 사용 계약입니다. 내부가 배열이어도 Stack ADT가 중간 원소 접근 연산을 제공하는 것은 아닙니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: 연산표를 쓰고 Queue [y]에 x를 enqueue한 작은 반례로 선택지 D를 확인합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: Stack push/pop은 보통 \(O(1)\)O(1)이다.
핵심 사실 네 가지 중 두 번째는?
정답: Queue enqueue/dequeue도 적절한 구현에서는 \(O(1)\)O(1)이다.
가장 위험한 함정은?
정답: ADT 수준에서 허용한 접근과 구현 수준의 저장 방식은 다르다. 배열로 구현한 스택도 스택 ADT를 통해 임의의 중간 원소에 직접 접근하게 해 주지는 않는다.
정답 label은?
정답: B, D
스택과 큐를 각각 LIFO·FIFO 용어로 한 문장씩 정의하라.
정답: 스택은 LIFO라서 마지막에 push한 원소가 먼저 pop된다. 큐는 FIFO라서 먼저 enqueue한 원소가 먼저 dequeue된다.
단일 연결 리스트(einfach verkettete Liste)와 이중 연결 리스트(doppelt verkettete Liste)의 포인터 차이를 말하라.
정답: 단일 연결(singly/einfach)은 보통 next만 저장하고 이전 노드 포인터(predecessor pointer)가 없다. 이중 연결(doubly/doppelt)은 next와 prev를 저장한다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-3
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· MC section, chunk window 1
2025년 여름학기(SoSe 2025) 복원 문항 I-2, I-3, II-3, II-4의 문구와 각각 하나·둘을 고르는 선택 규칙을 뒷받침한다.Vorlesung\03BasicDataStructures.pdf· pp. 3-9
추상 자료형(ADT)과 구체적 자료구조를 구분하고, 후입선출(LIFO) 방식의 스택 연산과 배열 기반 push·pop을 정의한다.Vorlesung\03BasicDataStructures.pdf· pp. 19-27
연결 리스트 노드의 next 포인터와 이중 연결 리스트의 prev 포인터를 정의하며, 탐색은 선형 시간이고 위치를 가리키는 포인터를 이미 알 때 삽입·삭제는 상수 시간임을 설명한다.Vorlesung\03BasicDataStructures.pdf· pp. 28-38
큐를 선입선출(FIFO) 구조로 정의하고, 원형 배열과 단일 연결 리스트의 enqueue·dequeue 연산 및 스택·큐·연결 리스트의 실행시간을 정리한다.