스택 2개를 이용한 선형 큐의 구현

2개의 스택을 사용하여 하나는 큐의 enqueue를 기능하게 하는 스택으로, 다른 하나를 큐의 dequeue 연산을 가능하게 하는 스택으로 생각해 볼 수 있다. 

왜냐하면 enqueue(값)을 할때, 값을 스택에 저장하게 되면 저장되는 순서는 먼저 입력된 순서대로 push하고 늦게push된 요소가 먼저pop된다.

예를들어 설명하자면 enqueue(10),enqueue(20), enqueue(30)을 한다고 할때, 스택1번에 10->20->30 순으로 push하면 아래서부터 쌓여있는 모습을 떠올릴 수 있다. 이는 스택의 성질인 (LIFO : Last In FIrst Out)을 이용하여 pop을 할때 30->20->10 순서대로 pop 될 것이다.

dequeue연산을 하게되면 스택1번에 저장된 요소들이 pop되는 순서를 이용하여, 스택 2번에 pop되는 순서대로 push를 해주게되면 스택 2번에 30->20->10으로 요소들이 쌓이게(저장)된다. 이제 스택 2번에서 pop되는 순서는 우리가 알고있는 큐의 (FIFO : First In First Out) 성질대로 순서에 맞춰 dequeue할 수 있게된다.

따라서 이 성질을 이용하여 두개의 스택으로 선형 큐를 구현해볼 수 있다.

선형 큐의 기능을 구현하기에 앞서 선형 큐의 ADT를 살펴보면 구현해야할 내용은 다음과 같다.

• isFull()
• isEmpty()
• enqueue
• dequeue

이 외 추가 기능이나 함수가 생길 수 있지만 필수적으로 구현해야 하는것들은 위의 4가지이다.

일단 스택으로 큐를 구현하는것이기에 isFull(),isEmpty()는 스택 1번, 스택 2번이 경우를 나누어서 생각하면 되는문제이니 스택의 오버플로우나 언더플로우 상태 검사를 그대로 써도된다. 단지 enqueue(),dequeue()구현에 있어 스택검사를 두개의 스택을 구분해서 잘 진행하면 될 것이다.

중요한 기능인 enqueue는 일단 두개의 스택이 있을때, 하나의 스택이 full이지 않은경우 push(값)을 해주면된다.

그리고 dequeue는 위에서 설명한대로 스택이 pop될때 순서가 뒤집힌다는 성질을 이용하여 스택 2번이 비어있는경우에 스택 1번의 모든 요소를 pop하여 그대로 스택2번에 push하고, 스택 2번을 pop하면된다. 이렇게 하면 큐의 dequeue와 같은 순서대로 나올수 있다.

// enqueue 후 상태 출력
void enqueue(StackType *s1, StackType *s2, element e) {
    if (isFullStack(s1)) {
        fprintf(stderr, "EnqueueStack is full\n");
        exit(1);
    }
    push(s1, e);
    printf("Enqueued %d\n", e);
    printStack(s1, "Stack 1 (enqueue stack)");
    printStack(s2, "Stack 2 (dequeue stack)");
}

// dequeue 후 상태 출력
element dequeue(StackType *s1, StackType *s2) {
    if (isEmptyStack(s2)) {
        while(!isEmptyStack(s1)) {
            push(s2, pop(s1));
        }
        printf("Transferred elements from Stack 1 to Stack 2\n");
    }
    element e = pop(s2);
    printf("Dequeued %d\n", e);
    printStack(s1, "Stack 1 (enqueue stack)");
    printStack(s2, "Stack 2 (dequeue stack)");
    return e;
}

 

기본적인 스택의 기능을 담은 코드

#define MAX_SIZE 100

typedef int element;
typedef struct {
    element data[MAX_SIZE];
    int top;
}StackType;
void initStack(StackType *stack) {
    stack->top = -1;
}

int isEmptyStack(StackType *stack) {
    return stack->top == -1;
}
int isFullStack(StackType *stack) {
    return stack->top == MAX_SIZE - 1;
}
void push(StackType *stack, element e) {
    if (isFullStack(stack)) {
        fprintf(stderr, "Stack is full\n");
        exit(1);
    }
    stack->data[++stack->top] = e;
}
element pop(StackType *stack) {
    if (isEmptyStack(stack)) {
        fprintf(stderr, "Stack is empty\n");
        exit(1);
    }
    return stack->data[stack->top--];
}

 

 

스택을 출력하는 함수와 메인함수(예시)

// 스택의 상태를 출력하는 함수
void printStack(StackType *stack, const char *stackName) {
    printf("%s: [", stackName);
    for (int i = 0; i <= stack->top; i++) {
        printf("%d", stack->data[i]);
        if (i < stack->top) {
            printf(", ");
        }
    }
    printf("] (top = %d)\n", stack->top);
}

int main() {
    StackType s1, s2;
    initStack(&s1);
    initStack(&s2);

    enqueue(&s1, &s2, 10);
    enqueue(&s1, &s2, 20);
    enqueue(&s1, &s2, 30);

    dequeue(&s1, &s2);
    dequeue(&s1, &s2);
    enqueue(&s1, &s2, 40);
    dequeue(&s1, &s2);

    return 0;
}

 

출력: