자료구조 학습에서 자주 등장하는 문제 중 하나는 큐(Queue) 두 개만을 이용해 스택(Stack)을 구현하는 것입니다. 이 글에서는 스택과 큐의 기본 개념을 짚어본 뒤, 연결 리스트 기반의 큐 두 개를 사용해 스택의 LIFO(후입선출) 동작을 재현하는 C++ 프로그램을 단계별로 살펴보겠습니다.
스택(Stack)이란?
스택은 LIFO(Last In, First Out, 후입선출) 방식으로 동작하는 자료구조입니다. 데이터의 삽입과 삭제가 모두 한쪽 끝, 즉 top(꼭대기)에서 이루어지며, 가장 마지막에 들어간 요소가 가장 먼저 삭제됩니다.
스택의 주요 연산은 다음과 같습니다.
- push(int data) — top 위치에 데이터를 삽입합니다.
- int pop() — top 위치에서 데이터를 삭제하고 반환합니다.
큐(Queue)란?
큐는 FIFO(First In, First Out, 선입선출) 방식으로 동작하는 자료구조입니다. 데이터는 한쪽 끝인 rear(뒤쪽)에서 삽입되고, 반대쪽 끝인 front(앞쪽)에서 삭제됩니다. 따라서 가장 먼저 들어간 요소가 가장 먼저 삭제됩니다.
큐의 주요 연산은 다음과 같습니다.
- EnQueue(int data) — rear 끝에 데이터를 삽입합니다.
- int DeQueue() — front 끝에서 데이터를 삭제하고 반환합니다.
두 개의 큐로 스택을 만드는 핵심 아이디어
큐는 선입선출 방식이라 그대로는 스택처럼 동작할 수 없습니다. 여기서 보조 큐 하나를 추가하면 문제가 해결됩니다. 요소를 pop할 때, 요소가 담긴 큐에서 마지막 하나만 남을 때까지 나머지 요소들을 모두 보조 큐로 옮깁니다. 그러면 남은 마지막 요소가 곧 스택의 top, 즉 가장 최근에 push된 요소가 됩니다. 이 요소를 출력한 뒤에는 두 큐의 역할을 서로 교대로 바꿔가며 같은 과정을 반복하면 됩니다.
알고리즘
1. enqueue1 — 첫 번째 큐(qu1)에 삽입
Begin
function enqueue1 to insert item a at qu1:
Set, np1 = new qu1
np1->d1 = a
np1->n1 = NULL
if (f1 == NULL)
Then set
r1 = np1
r1->n1 = NULL
f1 = r1
else
r1->n1 = np1
r1 = np1
r1->n1 = NULL
End
2. dequeue1 — 첫 번째 큐(qu1)에서 삭제
Begin
function dequeue1 to delete item from qu1.
if queue is null
Print no elements present in queue.
Else
q1 = f1
f1 = f1->n1
a = q1->d1
delete(q1)
return a
End
3. enqueue2 — 두 번째 큐(qu2)에 삽입
Begin
function enqueue2 to insert item a at qu2.
np2 = new qu2;
np2->d2 = a;
np2->n2 = NULL;
if queue is null
Set r2 = np2
r2->n2 = NULL
f2 = r2
Else
Set r2->n2 = np2
r2 = np2
r2->n2 = NULL
End
4. dequeue2 — 두 번째 큐(qu2)에서 삭제
Begin
function dequeue2 to delete item from qu2:
if queue is null
Print no elements present in queue.
Else
q2 = f2
f2 = f2->n2
a = q2->d2
delete(q2)
return a
End
예제 코드
아래 코드는 위 알고리즘을 그대로 구현한 전체 C++ 프로그램입니다. 각 큐는 연결 리스트 노드 구조체로 표현되며, front(f)와 rear(r) 포인터로 관리됩니다.
#include<iostream>
using namespace std;
struct qu1// queue1 declaration {
qu1 *n1;
int d1;
}*f1 = NULL, *r1 = NULL, *q1 = NULL, *p1 = NULL, *np1 = NULL;
struct qu2// queue2 declaration {
qu2 *n2;
int d2;
}*f2 = NULL, *r2 = NULL, *q2 = NULL, *p2 = NULL, *np2 = NULL;
void enqueue1(int a) {
np1 = new qu1;
np1->d1 = a;
np1->n1 = NULL;
if (f1 == NULL) {
r1 = np1;
r1->n1 = NULL;
f1 = r1;
} else {
r1->n1 = np1;
r1 = np1;
r1->n1 = NULL;
}
}
int dequeue1() {
int a;
if (f1 == NULL) {
cout<<"no elements present in queue\n";
} else {
q1 = f1;
f1 = f1->n1;
a = q1->d1;
delete(q1);
return a;
}
}
void enqueue2(int a) {
np2 = new qu2;
np2->d2 = a;
np2->n2 = NULL;
if (f2 == NULL) {
r2 = np2;
r2->n2 = NULL;
f2 = r2;
} else {
r2->n2 = np2;
r2 = np2;
r2->n2 = NULL;
}
}
int dequeue2() {
int a;
if (f2 == NULL) {
cout<<"no elements present in queue\n";
} else {
q2 = f2;
f2 = f2->n2;
a = q2->d2;
delete(q2);
return a;
}
}
int main() {
int n, a, i = 0;
cout<<"Enter the number of elements to be entered into stack\n";
cin>>n;
while (i < n) {
cout<<"enter the element to be entered\n";
cin>>a;
enqueue1(a);
i++;
}
cout<<"\n\nElements popped\n\n";
while (f1 != NULL || f2 != NULL)// if both queues are not null {
if (f2 == NULL)// if queue 2 is null {
while (f1->n1 != NULL) {
enqueue2(dequeue1());
}
cout<<dequeue1()<<endl;
} else if (f1 == NULL)//if queue 1 is null {
while (f2->n2 != NULL) {
enqueue1(dequeue2());
}
cout<<dequeue2()<<endl;
}
}
}
실행 결과
Enter the number of elements to be entered into stack 5 enter the element to be entered 1 enter the element to be entered 2 enter the element to be entered 3 enter the element to be entered 4 enter the element to be entered 5 Elements popped 5 4 3 2 1
동작 원리 상세 분석
위 실행 결과에서 1, 2, 3, 4, 5 순서로 입력했음에도 출력은 5, 4, 3, 2, 1 순서로 나타납니다. 이것이 바로 스택의 LIFO 특성입니다. 내부 동작 흐름을 살펴보면 다음과 같습니다.
- push 단계: 사용자가 입력한 값들이 enqueue1()을 통해 첫 번째 큐에 차례대로 쌓입니다.
- pop 단계: 두 번째 큐가 비어 있으면, 첫 번째 큐에서 마지막 요소 하나만 남을 때까지 앞의 요소들을 모두 dequeue1() → enqueue2()로 옮깁니다.
- 출력 단계: 남겨진 마지막 요소를 dequeue1()로 꺼내 출력합니다. 이 값이 스택의 top에 해당합니다.
- 역할 교대: 다음 pop부터는 두 큐의 역할이 서로 바뀌어, 같은 방식으로 반복 수행됩니다.
마무리 및 참고 사항
이 방식은 시간 복잡도 측면에서 비효율적일 수 있습니다. 매번 pop할 때마다 대부분의 요소를 다른 큐로 옮겨야 하기 때문에 한 번의 pop에 O(n)의 시간이 걸릴 수 있습니다. 실무에서는 std::stack 컨테이너 어댑터를 사용하는 것이 일반적이지만, 이 예제는 두 개의 큐만으로 스택의 논리를 구현하는 자료구조 사고력을 기르는 데 훌륭한 연습 문제입니다. 또한 연결 리스트 기반 큐의 삽입·삭제, 포인터 처리, 메모리 해제(delete)까지 함께 익힐 수 있어 학습 가치가 높습니다.