title: C: Queue and Memory Limit Excedeed
body: <p>I'm a <code>C</code> beginner and decided to participate in a small online contest in order to practice.</p>
  
  <p>In the current problem I'm asked to write a queue with a <code>struct</code> that responds to the commands <code>PushBack</code> and <code>PopFront</code>.</p>
  
  <p>The input consists of</p>
  
  <ul>
  <li>A number <code>n</code> (<code>n &lt;= 1000000</code>) indicating the number of commands inputs.</li>
  <li><code>n</code> lines. Each line consists of two integer numbers <code>a</code> and <code>b</code>:
  
  <ul>
  <li><code>a</code> is <code>2</code> for executing <code>PopFront</code>, in which case <code>b</code> is the expected popped value.</li>
  <li><code>a</code> is <code>3</code> for <code>PushBack</code>, in which case <code>b</code> is the value to be enqueued.</li>
  </ul></li>
  </ul>
  
  <p>If we try to pop from an empty queue then the value returned is <code>-1</code>.</p>
  
  <p>The task is to print <code>YES</code> or <code>NO</code> after executing the last command if the value returned by any <code>PushBack</code> during the program execution coincide or not with the expected value.</p>
  
  <p>I implemented a version of this, but after submitting my answer the online judge gives <code>Maximum-Limit-Excedeed</code> (in the last test out of <code>27</code>).</p>
  
  <p>I was reading about it and this issue may be related to some of these:</p>
  
  <ol>
  <li>Using an array or data structure too big.</li>
  <li>There is an infinite (or too big) recursion in the program.</li>
  <li>An incorrect usage of pointers (diagnosed as MLE).</li>
  </ol>
  
  <p>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 <code>1.</code> takes place in my code) which, in turn, causes the <code>while</code> loop in <code>EmptyQueue</code> to be too big (<code>2.</code> also takes place). I'm not able to spot whether there is an incorrect usage of pointers.</p>
  
  <p>My questions are:</p>
  
  <ul>
  <li>What am I'm doing wrong here?</li>
  <li>What should I do to fix this?</li>
  </ul>
  
  <p>Code:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdbool.h&gt;
  #include &lt;stdlib.h&gt;
  
  //===================
  //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", &amp;n);
  
      InitializeQueue(&amp;line);
  
      i = 0;
      while (i &lt; n)
      {
          scanf("%d %d", &amp;command, &amp;expected);
  
          switch (command)
          {
              case 2:
                  received = PopFront(&amp;line);
                  if (received != expected)
                      check = false;
                  break;
              case 3:
                  PushBack(&amp;line, expected);
                  break;
  
          }
          i++;
      }
  
      if (check == true)
          printf("YES\n");
      else
          printf("NO\n");
  
      // free memory used by all nodes
      EmptyQueue(&amp;line);
  
      return 0;
  
  }
  
  
  
  
  void InitializeQueue(Queue * pq)
  {
      pq-&gt;front = NULL;
      pq-&gt;rear = NULL;
      pq-&gt;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-&gt;item = item;
          pnode-&gt;next = NULL;
      }
  
      //Connect to Queue
      if (pq-&gt;front == NULL)
      {
          pq-&gt;front = pnode;
          pq-&gt;rear = pnode;
      }
      else
      {
          pq-&gt;rear-&gt;next = pnode;
          pq-&gt;rear = pnode;
      }
  
      pq-&gt;counter++;
  
      return true;
  }
  
  
  int PopFront(Queue * pq)
  {
      int popped;
      Node * temp;
  
      temp = pq-&gt;front;
  
      if (pq-&gt;counter == 0)
          return -1;
      else
      {
          popped = pq-&gt;front-&gt;item;
          pq-&gt;front = pq-&gt;front-&gt;next;
          free(temp);
          pq-&gt;counter--;
          return popped;
      }
  }
  
  
  
  
  void EmptyQueue(Queue * pq)
  {
      int dummy;
  
      while (pq-&gt;counter != 0)
          dummy = PopFront(pq);
  }
  </code></pre>
  
  <p>Thanks.</p>