스택과 큐의 상호 시뮬레이션
두 개의 스택으로 큐를 구현하고 두 개의 큐로 스택을 구현하며, 각 방식의 분할 상환 비용을 설명합니다.
스택과 큐의 상호 시뮬레이션은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
서로 바꿔 시뮬레이션하는 이유
두 개의 스택으로 큐를 구현하는 것과 두 개의 큐로 스택을 구현하는 것은 고전적인 설계 면접 문제입니다. 이 문제는 두 자료 구조의 불변식에 대한 이해와, 한 자료 구조의 기본 연산을 사용하면서 다른 자료 구조의 보장을 유지하는 능력을 평가합니다. 면접에서는 이를 분할 상환 복잡도를 논의하는 출발점으로 활용하기도 합니다.
핵심은 스택이 LIFO이고 큐가 FIFO라는 점입니다. 둘을 서로 바꾸려면 순서를 뒤집어야 합니다. 스택을 다른 스택으로 옮기면 삽입 순서가 복원되고, 그 순서는 FIFO가 됩니다.
두 스택으로 큐 구현하기(지연 방식)
지연 방식에서는 push를 위한 inbox 스택과 pop을 위한 outbox 스택을 사용합니다. 큐에서 꺼내는 연산이 호출되었을 때 outbox가 비어 있으면 inbox의 모든 요소를 outbox로 옮깁니다. 이 반전으로 FIFO 순서가 복원됩니다. outbox가 비어 있지 않으면 그곳에서 바로 pop합니다. 요소 이동은 필요할 때만 수행되므로 O(n)의 이동 비용을 여러 연산에 분산하여 처리할 수 있습니다.
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def _transfer(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._transfer()
return self.outbox.pop()
def peek(self):
self._transfer()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
q = MyQueue()
q.push(1); q.push(2); q.push(3)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.pop()) # 2
q.push(4)
print(q.pop()) # 3스택으로 구현한 큐의 분할 상환 O(1) 분석
각 요소는 inbox에서 outbox로 최대 한 번만 이동합니다. outbox에서 pop하는 연산이 O(1)이고 outbox가 비어 있을 때만 이동이 발생하므로, n번의 push와 n번의 pop에 필요한 전체 작업량은 최대 2n번의 스택 연산입니다. 따라서 전체 시간은 O(n)이고 연산 하나당 분할 상환 시간은 O(1)입니다. 즉 최악의 경우 개별 연산은 O(n)일 수 있지만 평균 시간은 O(1)입니다.
# Trace transfer costs for 10 push/pop interleaved
class TrackedQueue:
def __init__(self):
self.inbox = []; self.outbox = []; self.transfers = 0
def push(self, x): self.inbox.append(x)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
self.transfers += 1
return self.outbox.pop()
q = TrackedQueue()
for i in range(5):
q.push(i)
for _ in range(5):
q.pop()
q.push(10); q.push(20)
q.pop()
print('Total transfer operations:', q.transfers) # at most n두 큐로 스택 구현하기(지연 pop)
큐는 FIFO이므로 두 개의 큐로 스택을 구현하는 방식은 자연스럽지 않습니다. 지연 pop 방식에서는 주 큐 하나와 임시 큐 하나를 유지합니다. push할 때는 주 큐에 삽입하므로 O(1)입니다. pop 또는 peek할 때는 마지막 요소를 제외한 모든 요소를 임시 큐로 옮기고 마지막 요소를 저장한 다음 두 큐를 교환합니다. pop마다 O(n)이지만 push마다 O(1)입니다.
from collections import deque
class MyStack:
def __init__(self):
self.main = deque()
self.temp = deque()
def push(self, x):
self.main.append(x) # O(1)
def pop(self):
# Move all but last element to temp
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main.popleft() # the 'top'
self.main, self.temp = self.temp, self.main # swap
return val
def top(self):
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main[0]
self.temp.append(self.main.popleft())
self.main, self.temp = self.temp, self.main
return val
def empty(self):
return len(self.main) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.pop()) # 2한 큐로 스택 구현하기(push 시 회전)
한 큐를 사용하는 우아한 구현 방법은 다음과 같습니다. push할 때 새 요소를 큐에 삽입한 다음 큐를 회전하여 새 요소가 앞쪽에 오게 합니다. 회전이란 push 전에 큐에 있던 모든 요소를 꺼냈다가 다시 삽입하는 것을 의미합니다. 그러면 pop과 peek는 앞쪽에서 꺼내거나 확인하기만 하면 되므로 O(1)입니다. push는 O(n)으로, 두 큐를 사용하는 방식과 반대되는 선택입니다.
from collections import deque
class MyStackOneQueue:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
# Rotate: move all preceding elements behind x
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStackOneQueue()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2절충안 요약: 어떤 변형을 선택할까요?
두 스택으로 큐를 구현하는 경우: push는 O(1), pop과 peek는 분할 상환 O(1)이므로 pop 연산이 자주 발생할 때 적합합니다. 두 큐로 스택을 구현하는 경우: push는 O(1), pop은 O(n)이므로 pop보다 push가 훨씬 자주 발생할 때 적합합니다. 한 큐로 스택을 구현하는 경우: push는 O(n), pop은 O(1)이므로 pop이 많은 경우에 적합합니다. 면접에서는 이러한 절충안을 명확히 설명하여 단순히 ‘작동한다’는 것 이상으로 생각한다는 점을 보여 주십시오.
print('Queue from 2 stacks: push O(1), pop O(1) amortised')
print('Stack from 2 queues: push O(1), pop O(n)')
print('Stack from 1 queue: push O(n), pop O(1)')순서를 뒤집으면 FIFO가 복원되는 이유
요소 1, 2, 3을 스택(inbox)에 push하면 아래에서 위로 1, 2, 3 순서로 놓입니다. 모든 요소를 두 번째 스택(outbox)으로 pop하면 순서가 뒤집혀 outbox에는 아래에서 위로 3, 2, 1이 놓입니다. outbox에서 pop하면 1, 2, 3 순서로 나오므로 정확히 FIFO 삽입 순서가 됩니다. 이것이 두 번의 순서 뒤집기, 즉 두 개의 스택이 FIFO를 복원하는 이유입니다. 스택 하나만 사용하면 LIFO가 됩니다.
# Demonstrate double-reversal = FIFO
inbox = [1, 2, 3] # pushed in this order
outbox = []
while inbox:
outbox.append(inbox.pop())
print('outbox (one reversal):', outbox) # [3, 2, 1] top-to-bottom
# Pop from outbox gives FIFO
result = []
while outbox:
result.append(outbox.pop())
print('dequeued:', result) # [1, 2, 3] — FIFO!LeetCode 232: 스택으로 큐 구현하기
LeetCode 232는 ‘두 스택으로 큐 구현하기’ 문제입니다. 기대되는 풀이는 지연 방식의 outbox 이동입니다. 면접에서는 각 요소가 inbox에서 outbox로 최대 한 번만 이동하므로 모든 연산의 분할 상환 시간이 O(1)이라고 설명하십시오. 개별 pop 호출은 최악의 경우 O(n)일 수 있습니다(outbox가 비어 있을 때). 하지만 n번의 연산 전체에서 평균 시간은 O(1)이라고 덧붙이십시오.
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def pop(self):
self.peek() # ensure outbox is populated
return self.outbox.pop()
def peek(self):
if not self.outbox:
while self.inbox: # transfer lazily
self.outbox.append(self.inbox.pop())
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
# Simulation
q = MyQueue()
q.push(1); q.push(2)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.empty()) # FalseLeetCode 225: 큐로 스택 구현하기
LeetCode 225는 ‘큐로 스택 구현하기’ 문제입니다. 한 큐를 사용하여 push할 때 회전하는 풀이가 가장 깔끔합니다. 요소 x를 push한 뒤, 이미 큐에 있던 모든 요소를 x 뒤로 이동하여 큐를 회전합니다. push마다 O(n)이 들지만 top과 pop은 O(1)이 됩니다. 이 절충안을 설명하고, 문제의 제약 조건과 일치하는지 확인하십시오(예: push가 적거나 pop이 많은 작업량).
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x): # O(n)
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self): # O(1)
return self.q.popleft()
def top(self): # O(1)
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2
print(s.empty()) # False배열 하나로 스택 세 개 구현하기
관련된 설계 과제로 배열 하나를 사용해 스택 세 개를 구현하는 문제가 있습니다. 한 가지 방법은 배열을 크기가 같은 세 개의 고정 영역으로 나누는 것입니다. 더 유연한 방법은 포인터를 사용해 데이터를 교차 저장하고, 각 스택을 자신의 영역에서 확장하다가 경계가 충돌하면 복사하는 방식입니다. 이 문제는 동적 배열 관리 능력을 확인하며, 시니어급 면접에서 출제됩니다. 고정 영역 방식은 더 단순하지만 스택이 서로 다른 비율로 커지면 공간을 낭비합니다.
class ThreeStacks:
def __init__(self, size):
self.data = [0] * (3 * size)
self.tops = [-1, -1, -1] # relative top of each stack
self.size = size
def push(self, stack_num, val):
self.tops[stack_num] += 1
if self.tops[stack_num] >= self.size:
raise OverflowError('stack full')
self.data[stack_num * self.size + self.tops[stack_num]] = val
def pop(self, stack_num):
if self.tops[stack_num] < 0:
raise IndexError('stack empty')
val = self.data[stack_num * self.size + self.tops[stack_num]]
self.tops[stack_num] -= 1
return val
ts = ThreeStacks(5)
ts.push(0, 10); ts.push(1, 20); ts.push(2, 30)
print(ts.pop(0), ts.pop(1), ts.pop(2)) # 10 20 30핵심 정리: 시뮬레이션 패턴
상호 시뮬레이션 문제는 더 넓은 원리를 가르쳐 줍니다. 충분한 중간 버퍼와 역순 처리를 사용하면 어떤 자료구조든 다른 자료구조로 구현할 수 있습니다. 시뮬레이션의 비용은 어떤 연산을 최적화하느냐에 따라 달라집니다. push를 항상 O(1)로 만들거나 pop을 항상 O(1)로 만들 수 있지만, 둘 다 O(1)로 만들려면 분할 상환이나 여러 보조 자료구조가 필요합니다.
면접에서는 항상 ‘어떤 연산이 더 자주 수행되나요?’라고 질문해 보세요. 이 질문은 구현 변형을 선택하는 데 도움이 되며, 연산 요구 사항을 고려하는 시니어급 사고방식을 보여 줍니다.
이해도 확인
이 단원에서 배운 자료구조 및 알고리즘 — 코딩 면접 대비 개념을 얼마나 이해했는지 확인해 보세요.
단원 복습
이 단원에서는 다음을 배웠습니다. 두 개의 스택으로 큐를 구현하면 inbox에서 outbox로 요소를 필요할 때만 옮겨 pop을 분할 상환 O(1)에 수행할 수 있습니다. 또한 하나의 큐로 스택을 구현하면 push할 때마다 큐를 회전시켜 pop을 O(1)에 수행할 수 있지만 push는 O(n)이 됩니다. 그리고 어떤 연산을 O(1)로 만들지는 사용 패턴에 따라 결정됩니다. 다음 단원에서는 해시 맵의 내부 구조와 충돌 처리를 살펴봅니다.
자주 묻는 질문
“스택과 큐의 상호 시뮬레이션” 강의는 무료인가요?
네 — “스택과 큐의 상호 시뮬레이션” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“스택과 큐의 상호 시뮬레이션”에서 뭘 배우나요?
두 개의 스택으로 큐를 구현하고 두 개의 큐로 스택을 구현하며, 각 방식의 분할 상환 비용을 설명합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“스택과 큐의 상호 시뮬레이션” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.