creating a stack using two queues in c, dequeue is not working

Question

So I am creating a stack using two queues in C. And I am given enqueue, dequeue and printQueue. Unfortunately my dequeue for one of my queues is not working properly, below is what I have written thus far:

int isQueueEmpty(Queue *queue)
{
    if (queue == NULL) return 1;
    else if (queue->head == NULL) return 1;
    else return 0;
}

//// Do not modify this ////
void enqueue(Queue **queue, void *item)
{
    if (*queue == NULL)
        *queue = malloc(sizeof(Queue));
    if ((*queue)->head == NULL)
    {
        (*queue)->head = malloc(sizeof(Node));
        (*queue)->head->data = item;
        (*queue)->head->next = NULL;
        (*queue)->tail = (*queue)->head;
    }
    else
    {
        Node *temp = malloc(sizeof(Node));
        (*queue)->tail->next = temp;
        temp->data = item;
        temp->next = NULL;
        (*queue)->tail = temp;
    }
}

//// Do not modify this ////
void *dequeue(Queue *queue)
{
    if (queue == NULL || queue->head == NULL)
        return NULL;
    else
    {
        void *temp = queue->head->data;
        Node *tempNode = queue->head;
        queue->head = queue->head->next;
        free(tempNode);
        return temp;
    }
}

void printQueue(Queue *queue)
{
    if (queue != NULL)
    {
        printf("Queue content: {");
        Node *temp = queue->head;
        for (; temp != NULL; temp = temp->next)
        {
            printf("%d ", *(int* )(temp->data));
        }
        printf("}\n");
    }
    else
        printf("Uninitailized Queue\n");
}

Queue *q = NULL;
Queue *qu = NULL;

void push(void *item) {
    printf("reeter here\n");
    while (!isQueueEmpty(q)) {
        enqueue(&qu, q->head);
        printf("eleq: %d\n", *((int *)dequeue(q)));
    }
    enqueue(&q, item);
    while (!isQueueEmpty(qu)) {
        enqueue(&q, qu->head);
        dequeue(qu);
        //printf("elequ: %d\n", *((int *)dequeue(qu)));
    }
    printf("q:\n");
    printQueue(q);
    printf("qu:\n");
    printf("reached end\n");
    printQueue(qu);
}

Unfortunately my dequeue for my second queue is not removing the element properly cause the second loop in pop() to perform and infinite loop. Secondly the data stored in the queue after queuing it an dereferencing it came back as an address rather than what I input in:

reeter here
q:
Queue content: {1}
qu:
reached end
Uninitailized Queue
reeter here
eleq: 1
q:
Queue content: {21519347601}
qu:
reached end
Queue content: {}
reeter here
eleq: 2
eleq: -159836464
q:
Queue content: {3-1598364641519347601}
qu:
reached end
Queue content: {}
Queue content: {3-1598364641519347601}
3
-159836464
1519347601
reeter here

this is the result I have received from my shell. Hence how do I firstly fix the push() function so it actually pushes and stores the desired data and how do I dequeue the second queue properly without using modifying dequeue. Thank you

Answer 1

There is a problem in the dequeue function: it does not update the tail pointer when the last element is popped from the queue. This does not cause a problem because of the implementation of enqueue tests head first, but it is nevertheless risky to make tail a dangling pointer in this case.

I understand you ar not supposed to modify these functions, but here is a modified version for educational purposes:

void *dequeue(Queue *queue)
{
    if (queue == NULL || queue->head == NULL) {
        return NULL;
    } else {
        Node *tempNode = queue->head;
        queue->head = queue->head->next;
        if (!queue->head)
            queue->tail = NULL;
        void *temp = tempNode->data;
        free(tempNode);
        return temp;
    }
}

Note also these problems in enqueue:

• it is cumbersome and error prone to dereference the function argument multiple times.
• initialization code should be factorized
• allocation error should be tested and reported:

Here is a modified version for you to study:

int enqueue(Queue **queue_p, void *item)
{
    Queue *queue = *queue_p;

    if (*queue == NULL) {
        *queue_p = queue = malloc(sizeof(*queue));
        if (queue == NULL) {
            // allocation error, report failure
            return -1;
        }
    }
    Node *node = malloc(sizeof(*node));
    if (node == NULL) {
        // allocation error, report failure
        return -1;
    }
    node->data = item;
    node->next = NULL;
    if (queue->head == NULL) {
        queue->tail = queue->head = node;
    } else {
        queue->tail = queue->tail->next = node;
    }
    return 0;
}

Regarding your code, the function push() has several problems:

• you enqueue q->head instead of q->head->data. You should actually use the return value of dequeue() instead of breaking the encapsulation. The current code enqueues a pointer that will be freed by dequeue, causing undefined behavior.

Here is a modified version of push():

void push(void *item)
{
    printf("reenter here\n");
    while (!isQueueEmpty(q)) {
        int *data = dequeue(q);
        enqueue(&qu, data);
        //printf("eleq: %d\n", *data);
    }
    enqueue(&q, item);
    while (!isQueueEmpty(qu)) {
        int *data = dequeue(qu);
        enqueue(&q, data);
        //printf("elequ: %d\n", *data);
    }
    printf("q:\n");
    printQueue(q);
    printf("qu:\n");
    printQueue(qu);
    printf("reached end\n");
}