나중에 넣은 것과 먼저 넣은 것을 구분해요
vector·조건·반복·함수를 알고 시작해요. 스택은 마지막에 넣은 값을 먼저 꺼내고, 큐는 먼저 넣은 값을 먼저 꺼내요. <stack>의 stack<int>는 push(value)로 넣고, top()으로 마지막 값을 읽고, pop()으로 제거해요. empty()는 비었는지 알려줘요.
스택에 4, 7, 9를 넣으면 top은 9예요. pop 한 번 뒤 top은 7이에요. top은 읽기만 하므로 값을 없애려면 pop도 실행해야 해요. 빈 스택에는 top이나 pop을 호출하지 않아요.
두 번 뒤집으면 먼저 넣은 값을 꺼낼 수 있어요
입력용 스택 in에 4, 7, 9를 넣고, in의 top을 출력용 out에 옮기며 in에서 제거해요.
| 옮긴 값 | in의 아래→위 | out의 아래→위 |
|---|---|---|
| 9 | 4, 7 | 9 |
| 7 | 4 | 9, 7 |
| 4 | 비어 있음 | 9, 7, 4 |
out의 top은 먼저 넣은 4가 돼요. 이후 out에서 꺼내면 4, 7, 9 순서예요. 새 값은 계속 in으로 넣어요.
꺼낼 값이 남아 있을 때는 옮기지 않아요
4, 7을 넣고 4를 꺼낸 다음 9를 새로 넣었다고 해요. out의 top에는 아직 7, in에는 9가 있어요. 다음에 꺼낼 값은 무엇일까요? 먼저 들어온 7이에요.
out에 값이 있는데 in을 옮기면 top이 9가 되어 순서를 바꿔 버려요. out이 비었을 때만 in 전체를 옮기면 오래된 값이 언제나 먼저 나와요. 다음 과제는 빈칸으로 이 전환 시점과 옮기는 값을 읽게 해요.
직접 풀어봐요
operations의 양수는 그 번호를 큐 뒤에 넣으라는 명령이고, 0은 큐 앞에서 하나를 꺼내라는 명령이에요. 꺼낸 번호들을 순서대로 vector에 담아 반환해요. 두 스택을 사용하는 제공 코드의 빈칸을 채워요.
명령 수는 250, 넣는 번호는 11000이에요. 명령에는 0이 적어도 한 번 있고, 0이 나오는 모든 시점에 큐가 비어 있지 않아요. 같은 번호를 여러 번 넣을 수 있어요. push_back은 결과 vector 끝에 원소를 추가해요.
제공 코드의 for (int operation : operations)는 vector에서 값을 하나씩 꺼내 operation에 담는 범위 반복이에요. !in.empty()는 in이 비어 있지 않다는 뜻이에요.
실행용 입력은 첫 줄 명령 수 n, 다음 줄 n개 명령이에요. 출력은 꺼낸 번호들을 공백으로 구분한 한 줄이에요. main은 반환 vector를 출력하는 하네스 역할이에요.
예시 1: {3,8,0,0} → {3,8}. 넣은 순서대로 꺼내요.
예시 2: {5,9,0,2,0,0} → {5,9,2}. 5를 꺼낸 뒤 2가 들어와도 9가 먼저 나와요.
예시 입력
4 3 8 0 0
예상 결과
3 8
예시 입력
6 5 9 0 2 0 0
예상 결과
5 9 2
핵심 개념
stack-queue: 스택은 나중에 넣은 값부터, 큐는 먼저 넣은 값부터 꺼내요. 두 스택을 쓰는 큐는 출력용이 비었을 때만 입력용 전체를 뒤집어 옮겨요.