I-2 Stack과 Queue — 넣은 순서와 꺼내는 순서만 추적하기
먼저 이 문제의 정체부터
이 문제는 용어 네 개만 확실히 연결하면 풀립니다. Stack은 LIFO, Queue는 FIFO입니다. 하지만 약어만 외우면 시험장에서 섞이기 쉬우므로 a와 b 두 원소를 직접 넣고 무엇이 먼저 나오는지 확인하는 습관이 더 안전합니다.
문장에 'beide(둘 다)'가 있으면 특히 조심합니다. Stack과 Queue는 모두 원소를 저장하는 추상 자료형이지만 제거 규칙이 서로 반대입니다. 하나에만 맞는 원리를 둘 다에 적용한 선택지는 즉시 거짓입니다.
여기서는 구현 배열이나 연결 리스트의 세부 사항보다 ADT가 사용자에게 약속하는 동작이 핵심입니다. 내부 구현이 달라도 Stack의 pop은 가장 최근 원소를, Queue의 dequeue는 가장 오래 기다린 원소를 반환해야 합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · ADT와 구현의 차이
추상 자료형(Abstrakter Datentyp, ADT)은 어떤 연산을 제공하고 그 연산이 어떤 의미를 가지는지 정한 계약입니다. Stack은 push/pop/top, Queue는 enqueue/dequeue/front 같은 연산을 약속합니다.
배열로 구현하든 연결 리스트로 구현하든 외부에서 관찰되는 제거 순서가 같으면 같은 ADT입니다. 이 문항은 저장 공간의 모양이 아니라 이 계약을 묻습니다.
수식으로 정확히 쓰기
핵심 규칙Stack: push(x), pop(), top()
핵심 규칙Queue: enqueue(x), dequeue(), front()
이 절에서 꼭 기억할 것
- \(\text{ADT}=\)
ADT=무엇을 하는가 - 구현=어떻게 하는가
개념 2 · Stack과 LIFO
Stack은 Last In, First Out입니다. 마지막에 들어간 원소가 첫 번째로 나옵니다. push(a), push(b) 뒤에 pop()하면 b가 반환됩니다.
접시를 위로 쌓는 모습을 생각하면 아래 접시 a를 꺼내기 전에 위 접시 b를 먼저 치워야 합니다. 삽입과 삭제가 같은 끝(top)에서 일어납니다.
수식으로 정확히 쓰기
핵심 규칙\(\text{push}(a), \text{push}(b), \text{pop}() \to b\)push(a), push(b), pop() → b
핵심 규칙제거 순서 = 삽입 순서의 역순
이 절에서 꼭 기억할 것
- top이 가장 최근 원소다.
- LIFO의 L은 last inserted를 뜻한다.
개념 3 · Queue와 FIFO
Queue는 First In, First Out입니다. 먼저 들어온 원소가 먼저 나옵니다. enqueue(a), enqueue(b) 뒤에 dequeue()하면 a가 반환됩니다.
새 원소는 뒤(rear)에 서고, 제거는 앞(front)에서 일어납니다. Stack처럼 한쪽 끝만 사용하는 것이 아니라 논리적으로 서로 다른 두 끝을 사용합니다.
수식으로 정확히 쓰기
핵심 규칙\(\text{enqueue}(a), \text{enqueue}(b), \text{dequeue}() \to a\)enqueue(a), enqueue(b), dequeue() → a
핵심 규칙제거 순서 = 삽입 순서
이 절에서 꼭 기억할 것
- front가 가장 오래 기다린 원소다.
- FIFO의 F는 first inserted를 뜻한다.
개념 4 · 두 원소 시뮬레이션
약어가 순간적으로 헷갈리면 a, b를 순서대로 넣는 작은 실험을 종이에 씁니다. Stack은 [a,b]에서 top b를 제거하고, Queue는 front a를 제거합니다.
이 실험 하나로 네 선택지를 모두 판정할 수 있습니다. 정의를 장황하게 떠올리는 것보다 관찰 가능한 반환값을 만들면 말장난에 덜 속습니다.
수식으로 정확히 쓰기
핵심 규칙입력 순서: a 다음 b
핵심 규칙스택의 첫 출력: b
핵심 규칙큐의 첫 출력: a
이 절에서 꼭 기억할 것
- 최소 예시는 두 원소면 충분하다.
- 빈 자료구조 예외는 이 문항의 핵심이 아니다.
개념 5 · 시험 문장의 논리
'Stack und Queue arbeiten beide ...'는 두 구조 모두 뒤의 성질을 만족해야 참인 AND 명제입니다. Stack만 맞거나 Queue만 맞아도 전체 문장은 거짓입니다.
정확히 하나 선택(exactly one)이므로 각 선택지를 독립적으로 판정한 뒤 참이 하나인지 확인합니다. C는 두 구조의 원리를 서로 다르게 정확히 배치합니다.
수식으로 정확히 쓰기
핵심 규칙P와 Q가 모두 참 ⇔ \(P=\)P=참 그리고 \(Q=\)Q=참
이 절에서 꼭 기억할 것
- beide를 보면 양쪽을 각각 검사한다.
- 한 절반이 맞는 선택지는 정답이 아니다.
1. 시험장에서 따라 할 풀이 순서
정확히 하나 선택\((\text{exactly}_{\text{one}})\)(exactly(one))
스택: a, b를 넣으면 b가 먼저 나옴(LIFO)
큐: a, b를 넣으면 a가 먼저 나옴(FIFO)
\(A=\)A=거짓
선택 규칙을 표시한다
정확히 하나의 참을 찾아야 합니다.
핵심 규칙정확히 하나 선택\((\text{exactly}_{\text{one}})\)
(exactly(one))스택(Stack) 실험을 쓴다
a 다음 b를 push하면 pop은 b입니다.
핵심 규칙스택: a, b를 넣으면 b가 먼저 나옴(LIFO)
큐(Queue) 실험을 쓴다
a 다음 b를 enqueue하면 dequeue는 a입니다.
핵심 규칙큐: a, b를 넣으면 a가 먼저 나옴(FIFO)
A를 양쪽으로 검사한다
\(\text{Stack}=\text{LIFO}\)
Stack=LIFO는 맞지만 \(\text{Queue}=\text{LIFO}\)Queue=LIFO는 틀려 전체가 거짓입니다.\[A=거짓\]A=거짓B를 양쪽으로 검사한다
\(\text{Queue}=\text{FIFO}\)
Queue=FIFO는 맞지만 \(\text{Stack}=\text{FIFO}\)Stack=FIFO는 틀려 전체가 거짓입니다.\[B=거짓\]B=거짓C와 D를 대조한다
C만 \(\text{Stack}=\text{LIFO}, \text{Queue}=\text{FIFO}\)
Stack=LIFO, Queue=FIFO로 정확합니다. D는 둘을 완전히 뒤집었습니다.\[C=참, D=거짓\]C=참, D=거짓참 개수를 확인한다
참은 C 하나이므로 선택 규칙과 일치합니다.
\[참의 개수=1\]참의 개수=1
2. 이 문제를 실제로 끝까지 풀기
Stack에 a를 push하고 이어서 b를 push합니다. 가장 나중에 들어온 b가 top에 있으므로 pop()은 b를 반환합니다. 따라서 Stack은 LIFO입니다.
Queue에 a를 enqueue하고 이어서 b를 enqueue합니다. 먼저 들어온 a가 front에 있으므로 dequeue()는 a를 반환합니다. 따라서 Queue는 FIFO입니다.
A는 두 구조가 모두 LIFO라고 하지만 Queue 부분이 틀립니다. B는 둘 다 FIFO라고 하지만 Stack 부분이 틀립니다. C는 \(\text{Stack}=\text{LIFO}\)Stack=LIFO와 \(\text{Queue}=\text{FIFO}\)Queue=FIFO를 정확히 연결합니다. D는 두 연결을 모두 반대로 썼습니다.
따라서 유일하게 참인 선택지는 C입니다. 이 결론은 배열 구현인지 연결 리스트 구현인지와 무관합니다. ADT가 약속한 제거 순서로 판정했기 때문입니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
Stack은 LIFO지만 Queue는 FIFO입니다. '둘 다 LIFO'라는 결합 명제에서 Queue 부분이 실패합니다.
빠른 확인법: Queue에 a,b를 넣으면 a가 먼저 나오므로 LIFO가 아닙니다.
-
B거짓
Queue는 FIFO지만 Stack은 LIFO입니다. Stack에 먼저 넣은 a가 아니라 나중에 넣은 b가 먼저 나옵니다.
빠른 확인법: Stack에 a,b를 넣고 pop하면 b입니다.
-
C참 — 정답 후보
Stack은 최근 원소를 먼저 제거하는 LIFO이고 Queue는 가장 오래된 원소를 먼저 제거하는 FIFO입니다. 두 정의가 모두 정확합니다.
빠른 확인법: \(\text{Stack}\to b, \text{Queue}\to a\)
Stack→b, Queue→a라는 두 원소 실험과 일치합니다. -
D거짓
Stack과 Queue의 원리를 정확히 반대로 배치했습니다.
빠른 확인법: LIFO를 Stack에, FIFO를 Queue에 다시 연결하면 C가 됩니다.
4. 초보자가 가장 자주 틀리는 이유
- LIFO의 first를 '먼저 넣은 것'으로 잘못 읽는다.
- Queue도 한쪽 끝에 쌓인다고 상상해 Stack과 혼동한다.
- 선택지의 앞 절반만 맞으면 전체가 맞다고 판단한다.
- push/pop과 enqueue/dequeue 명칭만 외우고 반환 순서를 시뮬레이션하지 않는다.
- 배열이나 linked list 구현 세부로 빠져 정작 ADT의 제거 순서를 놓친다.
- 빈 구조에서의 underflow를 고민하지만 이 문항에는 필요하지 않다.
5. 시험 답안 템플릿
두 원소 a,b를 이 순서로 넣어 본다. Stack에서는 pop()이 b를 반환하므로 LIFO이고, Queue에서는 dequeue()가 a를 반환하므로 FIFO이다. 따라서 유일하게 참인 선택지는 C이다.
6. 스스로 이해했는지 확인
push(1), push(2), push(3) 뒤 첫 pop 결과는?
정답: 3입니다. 마지막에 들어온 원소가 먼저 나옵니다.
enqueue(1), enqueue(2), enqueue(3) 뒤 첫 dequeue 결과는?
정답: 1입니다. 먼저 들어온 원소가 먼저 나옵니다.
Stack의 삽입·삭제가 일어나는 논리적 위치는?
정답: 둘 다 top입니다.
Queue의 삽입과 삭제 위치는?
정답: 삽입은 rear, 삭제는 front입니다.
Stack을 연결 리스트로 만들면 FIFO가 되는가?
정답: 아닙니다. 구현과 무관하게 Stack ADT의 pop 의미는 LIFO입니다.
정답을 한 문장으로 말하면?
정답: Stack은 LIFO, Queue는 FIFO이므로 C입니다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice I.2
복기된 문제 문언과 선택지Vorlesung\03BasicDataStructures.pdf· p. 4 and p. 29
Stack과 Queue ADT 및 LIFO/FIFO 정의Übung\AuD26_Sheet04-Sol.pdf· pp. 4-5
Stack/Queue 연산의 공식 연습 해설