문제 개요
큐(Queue)를 사용하여 하나의 스택(Stack)을 구현한다고 가정해 보겠습니다. 이를 위해서는 스택에 필요한 다음과 같은 메서드들을 정의해야 합니다.
push(x) − x를 스택에 삽입합니다.
pop() − 스택의 최상단 요소를 제거한 후 반환합니다.
top() − 스택의 최상단 요소를 반환합니다.
empty() − 스택이 비어 있는지 여부를 반환합니다.
예를 들어, push(10)과 push(20)을 차례로 호출한 뒤 pop()을 두 번 호출하면 출력 결과는 20, 10 순서로 나타납니다. 이는 스택의 LIFO(Last In First Out, 후입선출) 특성 때문입니다.
해결 접근 방법
이 문제는 C++ STL의 deque(덱) 자료구조를 활용하면 간단하게 해결할 수 있습니다. deque는 양쪽 끝에서 모두 삽입과 삭제가 가능하기 때문에, 맨 앞쪽으로 데이터를 삽입하면 스택처럼 동작하도록 만들 수 있습니다. 해결 절차는 다음과 같습니다.
deque 타입의 변수 q를 하나 선언합니다.
push(x) 함수를 정의합니다. 이 함수는 x를 매개변수로 받습니다.
x를 q의 맨 앞에 삽입합니다(push_front).
pop() 함수를 정의합니다.
k := q의 첫 번째(맨 앞) 요소로 설정합니다.
q에서 맨 앞 요소를 삭제합니다(pop_front).
k를 반환합니다.
top() 함수를 정의합니다.
q의 첫 번째 요소를 그대로 반환합니다.
empty() 함수를 정의합니다.
q가 비어 있다면 true를 반환합니다.
그렇지 않다면 false를 반환합니다.
예제 코드
아래 구현 예시를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class MyStack {
private:
deque<int> q;
public:
void push(int x){
q.push_front(x);
}
int pop(){
int k = q.front();
q.pop_front();
return k;
}
int top(){
return q.front();
}
bool empty(){
if (q.empty())
return true;
else
return false;
}
};
main(){
MyStack ob;
ob.push(10);
ob.push(20);
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
}입력
push(10),push(20),pop(),pop()
출력
20 10
동작 원리 정리
핵심은 push_front()입니다. 새로운 요소를 항상 덱의 맨 앞에 삽입하기 때문에, 가장 마지막에 들어온 요소가 항상 맨 앞에 위치하게 됩니다. 따라서 front()로 요소를 확인·삭제하면 자연스럽게 LIFO 방식의 스택 동작을 구현할 수 있습니다. 모든 연산이 O(1) 시간 복잡도로 처리되므로 효율적입니다.