[C 자료구조] Queue - Queue using Two Stacks

0) 제목

Hackerrank 의 Queue 부분의 Queue using Two Stacks 문제입니다.

C언어를 이용하여 풀었습니다.

1) 문제설명

두개의 Stack을 가지고 Queue를 구현을 하는 문제입니다.

2) 풀이과정

두개의 Stack을 가지고 Queue를 구현을 하는 문제입니다.

동적할당으로 구현했습니다.

Queue에서 dequeue했을때,

Main Stack의 데이터들을 모두 pop 해서 Sub Stack에 push하는 방식으로 데이터 순서를 바꿨습니다.

그리고 나서 Sub Stack의 맨위 데이터를 pop 해서 dequeue를 구하고,

다시 Sub Stack에 있는 데이터를 모두 pop하고 Main Stack으로 push해서 데이터 순서를 돌렸습니다.

두개의 스택으로 구현하라고 하여서 제가 생각한 방법은 이 방법이었습니다.

더 좋은방법이 있을까요?

3) 코드

#include <stdio.h>
#include <stdlib.h>
 
enum {ENQUEUE=1, DEQUEUE, PEEK};
 
typedef long long Data;
typedef struct _stack{
    Data * arr;
    int top;
} Stack;
 
//stack 초기화
void StackInit(Stack *ps, int q){
    ps->arr = (Data *)malloc(sizeof(Data)*q);
    ps->top = -1;
}
//stack push
void push(Stack * ps, Data data){
    ps->arr[++(ps->top)] = data;
}
//stack pop
Data pop(Stack * ps){
    if(ps->top == -1) return -1;
    return ps->arr[(ps->top)--];
}
//stack peek
Data peekStack(Stack * ps){
    if(ps->top == -1) return -1;
    return ps->arr[ps->top];
}
//stack free
void StackFree(Stack * ps){
    free(ps->arr);
}
//main stack에 data를 push.
void enqueue(Stack * ps, Data data){
    push(ps, data);
}
 
//main stack에 있는 데이터 pop -> sub stack으로 push해서,
//sub stack에서 pop을 한번한다. (dequeue 때문에)
//그러고 나서 다시 sub stack의 데이터를 pop -> main stack 으로 push.
Data dequeue(Stack * main, Stack * sub){
    Data tmp, data;
    while(1){
        tmp = pop(main);
        if(tmp==-1) break;
        push(sub, tmp);
    }
    data=pop(sub);
    while(1){
        tmp = pop(sub);
        if(tmp == -1) break;
        push(main,tmp);
    }
    return data;
}
//main 스택의 첫번째 data return.
Data peek(Stack * ps){
    return ps->arr[0];
}
 
int main(void){
    int q, i, type;
    Data data;
    scanf("%d", &q);
    Stack stack, tmpStack;
    StackInit(&stack, q);
    StackInit(&tmpStack, q);
    
    for(i=0; i<q;i++){
        scanf("%d", &type);
        switch(type){
            case ENQUEUE:
                scanf("%lld", &data);
                enqueue(&stack, data);
                break;
            case DEQUEUE:
                dequeue(&stack, &tmpStack);
                break;
            case PEEK:
                printf("%lld\n",peek(&stack));
                break;
        }
    }
    
    StackFree(&stack);
    StackFree(&tmpStack);
    return 0;
}

경로 : Dashboard>Data Structures>Queue using Two Stacks

문제 출처 : [HackerRank] https://www.hackerrank.com/challenges/queue-using-two-stacks