C++로 두 개의 스택을 활용해 큐(Queue) 구현하기

개요

이 글에서는 두 개의 스택(Stack)을 사용하여 큐(Queue)를 구현하는 C++ 프로그램을 소개합니다. 스택과 큐는 각각 LIFO와 FIFO라는 서로 다른 데이터 처리 순서를 가지기 때문에, 두 개의 스택을 조합하면 큐의 동작 방식을 효율적으로 흉내 낼 수 있습니다.

스택(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(앞쪽)에서 요소를 삭제하고 반환합니다.

함수 동작 원리

이 프로그램의 핵심 로직은 다음과 같습니다.

• enQueue() 함수: 큐에 항목을 삽입합니다.
  • s1 스택에 push 합니다.
• deQueue() 함수: 큐에서 항목을 삭제합니다.
  • 두 스택이 모두 비어 있으면 "큐가 비어 있습니다"라는 메시지를 출력합니다.
  • s2가 비어 있다면, s1의 모든 요소를 s2로 옮깁니다.
  • s2에서 요소를 pop하여 반환합니다.
• push() 함수: 스택에 항목을 삽입합니다.
• pop() 함수: 스택에서 항목을 제거합니다.

이 방식의 장점은 deQueue() 시점에 s2로 요소를 옮길 때만 O(n) 작업이 발생하고, 나머지 대부분의 연산이 O(1)로 처리된다는 점입니다. 각 요소는 최대 두 번(s1 → s2)만 이동하기 때문에 전체적으로 분할 상환(amortized) O(1)의 효율성을 보장합니다.

예제 코드

#include<stdlib.h>
#include<iostream>
using namespace std;

// 노드 선언
struct nod {
    int d;
    struct nod *n;
};

// 함수 프로토타입
void push(struct nod** top_ref, int n_d);
int pop(struct nod** top_ref);

// 두 개의 스택을 포함하는 큐 구조체
struct queue {
    struct nod *s1;
    struct nod *s2;
};

void enQueue(struct queue *q, int m) {
    push(&q->s1, m);
}

int deQueue(struct queue *q) {
    int m;
    // 두 스택이 모두 비어 있는 경우
    if (q->s1 == NULL && q->s2 == NULL) {
        cout << "Queue is empty";
        exit(0);
    }
    // s2가 비어 있으면 s1의 요소를 모두 s2로 이동
    if (q->s2 == NULL) {
        while (q->s1 != NULL) {
            m = pop(&q->s1);
            push(&q->s2, m);
        }
    }
    m = pop(&q->s2);
    return m;
}

void push(struct nod** top_ref, int n_d) {
    struct nod* new_node = (struct nod*) malloc(sizeof(struct nod));

    if (new_node == NULL) {
        cout << "Stack underflow \n";
        exit(0);
    }
    // 스택에 항목 추가
    new_node->d = n_d;
    new_node->n = (*top_ref);
    (*top_ref) = new_node;
}

int pop(struct nod** top_ref) {
    int res;
    struct nod *top;
    if (*top_ref == NULL) { // 스택이 비어 있는 경우
        cout << "Stack overflow \n";
        exit(0);
    } else { // 스택에서 요소 제거
        top = *top_ref;
        res = top->d;
        *top_ref = top->n;
        free(top);
        return res;
    }
}

int main() {
    struct queue *q = (struct queue*) malloc(sizeof(struct queue));
    q->s1 = NULL;
    q->s2 = NULL;

    cout << "Enqueuing..7";
    cout << endl;
    enQueue(q, 7);

    cout << "Enqueuing..6";
    cout << endl;
    enQueue(q, 6);

    cout << "Enqueuing..2";
    cout << endl;
    enQueue(q, 2);

    cout << "Enqueuing..3";
    cout << endl;
    enQueue(q, 3);

    cout << "Dequeuing...";
    cout << deQueue(q) << " ";
    cout << endl;

    cout << "Dequeuing...";
    cout << deQueue(q) << " ";
    cout << endl;

    cout << "Dequeuing...";
    cout << deQueue(q) << " ";
    cout << endl;
}

실행 결과

Enqueuing..7
Enqueuing..6
Enqueuing..2
Enqueuing..3
Dequeuing...7
Dequeuing...6
Dequeuing...2

출력 결과에서 확인할 수 있듯이, 삽입한 순서인 7, 6, 2, 3 중에서 먼저 들어간 7, 6, 2 순서대로 FIFO 방식으로 정상적으로 삭제되는 것을 볼 수 있습니다. 이처럼 두 개의 스택을 활용하면 스택의 LIFO 특성을 조합하여 큐의 FIFO 특성을 완벽하게 재현할 수 있습니다.