C: Queue and Memory Limit Excedeed

Question

I'm a C beginner and decided to participate in a small online contest in order to practice.

In the current problem I'm asked to write a queue with a struct that responds to the commands PushBack and PopFront.

The input consists of

• A number n (n <= 1000000) indicating the number of commands inputs.
• n lines. Each line consists of two integer numbers a and b:
  • a is 2 for executing PopFront, in which case b is the expected popped value.
  • a is 3 for PushBack, in which case b is the value to be enqueued.

If we try to pop from an empty queue then the value returned is -1.

The task is to print YES or NO after executing the last command if the value returned by any PushBack during the program execution coincide or not with the expected value.

I implemented a version of this, but after submitting my answer the online judge gives Maximum-Limit-Excedeed (in the last test out of 27).

I was reading about it and this issue may be related to some of these:

1. Using an array or data structure too big.
2. There is an infinite (or too big) recursion in the program.
3. An incorrect usage of pointers (diagnosed as MLE).

I'm not sure what is the problem. It seems to me that in some of the tests the number of addition of nodes is way greater than that of deletions (which means that 1. takes place in my code) which, in turn, causes the while loop in EmptyQueue to be too big (2. also takes place). I'm not able to spot whether there is an incorrect usage of pointers.

My questions are:

• What am I'm doing wrong here?
• What should I do to fix this?

Code:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

//===================
//Definitions:

typedef int Item;

typedef struct node
{
    Item item;
    struct node * next;
} Node;

typedef struct queue
{
    Node * front;
    Node * rear;
    long counter;
} Queue;

//===================
//Function Prototypes:

void InitializeQueue(Queue * pq);
bool PushBack(Queue * pq, Item item);
int PopFront(Queue * pq);
void EmptyQueue(Queue * pq);


int main(void)
{
    Queue line;
    long n, i;
    int command, expected, received;
    bool check = true;

    scanf("%ld", &n);

    InitializeQueue(&line);

    i = 0;
    while (i < n)
    {
        scanf("%d %d", &command, &expected);

        switch (command)
        {
            case 2:
                received = PopFront(&line);
                if (received != expected)
                    check = false;
                break;
            case 3:
                PushBack(&line, expected);
                break;

        }
        i++;
    }

    if (check == true)
        printf("YES\n");
    else
        printf("NO\n");

    // free memory used by all nodes
    EmptyQueue(&line);

    return 0;

}




void InitializeQueue(Queue * pq)
{
    pq->front = NULL;
    pq->rear = NULL;
    pq->counter = 0;
}

bool PushBack(Queue * pq, Item item)
{
    Node * pnode;

    //Create node
    pnode = (Node *)malloc(sizeof(Node));

    if (pnode == NULL)
    {
        fputs("Impossible to allocate memory", stderr);
        return false;
    }
    else
    {
        pnode->item = item;
        pnode->next = NULL;
    }

    //Connect to Queue
    if (pq->front == NULL)
    {
        pq->front = pnode;
        pq->rear = pnode;
    }
    else
    {
        pq->rear->next = pnode;
        pq->rear = pnode;
    }

    pq->counter++;

    return true;
}


int PopFront(Queue * pq)
{
    int popped;
    Node * temp;

    temp = pq->front;

    if (pq->counter == 0)
        return -1;
    else
    {
        popped = pq->front->item;
        pq->front = pq->front->next;
        free(temp);
        pq->counter--;
        return popped;
    }
}




void EmptyQueue(Queue * pq)
{
    int dummy;

    while (pq->counter != 0)
        dummy = PopFront(pq);
}

Thanks.

Answer 1

I don't think there's actually anything wrong with that code functionally, though it could do with some formatting improvements :-)

I will mention one thing:

The task is to check whether the returned value after executing PopFront coincides with the expected one. If so, then print YES. Print NO, otherwise.

I would read this as a requirement on each PopFront. You appear to be storing the fault condition and only printing YES or NO once at the end.

I'd suggest fixing that as a start and see what the online judge comes back with.

---

This all ignores the fact that it's actually rather difficult to debug code unless you can reproduce the problem. If you can't get the data set from the online contest, it may be worth generating your own (large) one to see if you can get you code to fail.

Once you have a repeatable failure, debugging becomes massively easier.

---

Although it's unlikely, you may (as mch points out in a comment) be running afoul of limited memory. I consider this unlikely as your own comments indicate only 5meg of space is being used at the end, which is not onerous. However, if that is the case, it's probably due to the fact that every single integer has the overhead of a pointer carried along with it.

If you wanted to investigate that avenue, you could slightly adjust the structures as follows (getting rid of the unnecessary counter as well):

#define ITEMS_PER_NODE 1000

typedef struct node {
    Item item[ITEMS_PER_NODE];  // array of items.
    int startIndex;             // start index (one to pop from).
    int nextIndex;              // next index (one to push at).
    struct node *next;          // next node.
} Node;

typedef struct queue {
    Node *front;                // first multi-item node.
    Node *rear;                 // last multi-item node.
} Queue;

The idea is to store many items per node so that the overhead of the next pointer is greatly reduced (one pointer per thousand items rather than one per item).

The code for queue manipulation would then become slightly more complex but still understandable. First off, a helper function for creating a new node, ready for adding data to:

// Helper to allocate a new node and prep it for appending.
// Returns node or NULL (and prints error) if out of memory.

Node *GetNewNode(void) {
    Node *pnode = malloc (sizeof(Node));
    if (pnode == NULL)
        fputs ("Impossible to allocate memory", stderr);
    else
        pnode->startIndex = pnode->nextIndex = 0;
    return pnode;
}

Next, the mostly unchanged queue initialisation:

void InitializeQueue (Queue *pq) {
    pq->front = pq->rear = NULL;
}

The pushback is slightly more complex in that it first adds a new multi-item node if the queue is empty or current last node has reached the end. Whether that happens or not, an item is added to the final node:

bool PushBack (Queue *pq, Item item) {
    // Default to adding to rear node (assuming space for now).

    Node *pnode = pq->rear;

    // Make sure queue has space at end for new item.

    if (pq->front == NULL) {
        // Handle empty queue first, add single node.

        if ((pnode = GetNewNode()) == NULL)
            return false;
        pq->front = pq->rear = pnode;

    } else if (pq->rear->nextItem == ITEMS_PER_NODE) {
        // Handle new node needed in non-empty queue, add to rear of queue.

        if ((pnode = GetNewNode()) == NULL)
            return false;
        pq->rear->next = pnode;
        pq->rear = pnode;
    }

    // Guaranteed space in (possibly new) rear node now, just add item.

    pq->rear->item[pq->rear->nextIndex++] = item;
}

Popping is also a bit more complex - it gets the value to return then deletes the first node if it's now exhausted. That may also entail clearing the queue if the node it deletes was the only one:

int PopFront (Queue * pq) {
    // Capture empty queue.

    if (pq->first == NULL)
        return -1;

    // Get value to pop.

    Node *currFront = pq->front;
    int valuePopped = currFront->item[currFront->startIndex++];

    // Detect current node now empty, delete it.

    if (currFront->startItem == currFront->endIndex) {
        // Detect last node in queue, just free and empty entire queue.

        if (currFront == pq->rear) {
            free (currFront);
            pq->front = pq->rear = NULL;
        } else {
            // Otherwise remove front node, leaving others.

            pq->front = currFront->next;
            free (currFront);
        }
    }

    // Regardless of queue manipulation, return popped value.

    return valuePopped;
}

Emptying the queue is largely unchanged other than the fact we clear nodes rather than items:

void EmptyQueue (Queue * pq) {
    // Can empty node at a time rather than item at a time.

    while (pq->front != NULL) {
        Node *currentFront = pq->front;
        pq->front = pq->front->next;
        free (currentFront);
    }
}

Answer 2

I think is better to use a more simple approach like that in the code I post here.

The code in the following lines doesn't match the input/output required by the contest, but contains a functional and simple approach to solve the problem: A simple stack manager! (if I correctly understood).

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

int * stack;
int * base;
int cnt;

/* To emulate input file */
struct stFile {
    int n;
    struct stCmd {
        int a;
        int b;
    } cmd[200]; // 200 is an arbitrary value.
} fdata = {
    20,
    {
        {2,0},
        {2,0},
        {2,0},
        {3,35},
        {2,0},
        {3,4},
        {2,0},
        {2,0},
        {2,0},
        {3,12},
        {3,15},
        {3,8},{3,18},
        {2,0},
        {2,0},
        {3,111},
        {2,0},
        {2,0},
        {2,0},
        {2,0},
        {3,8},{3,18},{3,8},{3,18},{3,8},{3,18},{3,8},{3,18},{3,8},{3,18},
        {3,11},{3,13},{3,11},{3,11},{3,11},{3,11},{3,11},{3,11},
        {3,11},{3,13},{3,11},{3,11},{3,11},{3,11},{3,11},{3,11},
        {2,0},
        {2,0},
        {2,0},
        {2,0},
        {2,0},
        {2,0},
        {2,0},
        {2,0},
        {0,0}
    }
};

int push(int item)
{
    if (cnt) {
        *stack = item;
        stack++;
        cnt--;
        return 0;
    } else {
        return 1;
    }
}

int pop(int *empty)
{
    if (stack!=base) {
        stack--;
        cnt++;
        if (empty)
            *empty = 0;
    } else {
        if (empty)
            *empty = 1;
    }

    return *stack;
}

int main(void)
{
    int i=0,e=0;

    cnt = fdata.n;
    base = stack = malloc(cnt*sizeof(int));

    if (!base) {
        puts("Not enough memory!");
        return 1;
    }

    while(fdata.cmd[i].a!=0) {
        switch(fdata.cmd[i].a) {
        case 2:
            printf("popping ...: %d ",pop(&e));
            printf("empty: %d\n",e);
            break;

        case 3:
            e = push(fdata.cmd[i].b);
            printf("pushing ...: %d %s\n",fdata.cmd[i].b,(e)?"not pushed":"pushed");
            break;

        default:
            break;

        };

        i++;
    }

    if (base)
        free(base);

    return 0;
}