Implement Stack using Queue

Problem Statement:

Implement a Stack using Queue.

Solution:

Utilize two Queues.
Use Q1 to push the elements.
Use Q2 as temporary, to store the  other elements while popping.

Code:

<ankzcode>

#include <stdio.h>
#include <malloc.h>

typedef struct __node {
    int data;
    struct __node *next;
    struct __node *prev;
}Node, *PNode;

typedef struct __q {
    PNode head;
    PNode tail;
    int   elemCount;
}Q, *PQ;

void enqueue(PQ q, int val)
{
    PNode node=NULL;
  
    if(q == NULL) { printf("Error: Q empty\n"); return;}

    node = (PNode) malloc (sizeof(Node));

    if(node==NULL) return;
  
    node->data =  val;
    node->next = NULL;
    node->prev = NULL;

    if(q->tail == NULL) {
        q->tail    = node;
        q->head    = node;
    } else {
        node->next = q->tail;
        q->tail->prev = node;
        q->tail = node;
    }
    q->elemCount++;
}

int dequeue(PQ q)
{
    int res = -1;
    PNode tmp;

    if((q == NULL) || (q->head == NULL)) return -1;
    res = q->head->data;
    tmp = q->head;
    q->head = tmp->prev;
    if(q->head != NULL) q->head->next = NULL;
    else q->tail = q->head;
    free(tmp);

    q->elemCount--;

    return res;
}

void initQ(PQ q)
{
    if(q == NULL) return;

    q->head = NULL;
    q->tail = NULL;
    q->elemCount=-1;
    return;
}

void displayQ(PQ q)
{
    PNode tmp = NULL;
    if(q == NULL) return;

    tmp = q->head;
    printf("Queue status: ");
    while( tmp ) {
          printf("%d ", tmp->data);
          tmp = tmp->prev;
    }
    printf("\n");
}

int testQ()
{
    Q q;

    initQ(&q);

    enqueue(&q,3);
    enqueue(&q,2);
    enqueue(&q,6);
    enqueue(&q,1);
    printf("%d\n", dequeue(&q));
    printf("%d\n", dequeue(&q));
    printf("%d\n", dequeue(&q));
    printf("%d\n", dequeue(&q));
  
    return 0;
}

typedef struct __s {
    PQ q1;
    PQ q2;
}S, *PS;

void initS(PS s)
{
    if(s == NULL) return;

    s->q1 = (PQ)malloc(sizeof(Q));
    s->q2 = (PQ)malloc(sizeof(Q));

    initQ(s->q1);
    initQ(s->q2);

    return;
}

void push(PS s, int val)
{
    if(s == NULL) return;
  
    enqueue(s->q1, val);  
}

int pop(PS s)
{
    PQ tmp = NULL;
    int res = -1;

    if((s == NULL) || (s->q1 == NULL)) return res;
    while(s->q1->elemCount > 0) {
        enqueue(s->q2, dequeue(s->q1));
    }

    res = dequeue(s->q1);

    tmp = s->q1;
    s->q1 = s->q2;
    s->q2 = tmp;
    return res;
}

int main()
{
    S s;

    initS(&s);

    printf("Pushing\n");
    push(&s, 3);
    push(&s, 2);
    push(&s, 6);
    push(&s, 1);
    displayQ(s.q1);

    printf("Poping\n");
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    return 0;
}

</ankzcode>