queue implementation not working

**sballew** · 12-04-2001

need to get this source file to interact with my file with queue functions. Please Help !!

Code:

/********************/
/*  queue_main.c      */
/********************/

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

int count;

main()
{
  int number, choice;

  make_empty();

  for( ; ; )    {

    printf("\nChoose one of the following.\n\n"
           "0   To end program\n"
           "1   To add a value to list (Push)\n"
           "2   To remove top value from list (Pop)\n"
           "3   To print list \n"
           "4   To list # of nodes\n\n");

    printf("Enter your choice: ");
    scanf("%d", &choice);
    printf("\n");

    switch(choice)
    {
      case 0:
        printf("You have ended the program.\n"
               "Good-bye !! \n\n");
        exit(0);

      case 1:
        printf("Enter a number to push: ");
        scanf("%d", &number);
        push(number);
        break;

      case 2:
        number = pop();
        printf("You just removed %d\n", number);
        break;

      case 3:
        print_list();
        break;

      case 4:
        printf("You have %d nodes in your list\n",count);
        break;

      default:
        printf("Illegal choice.\n");
    }
  }
  return 0;
}

Here's the source file with queue functions

Code:

/*************************/
/* queue.c                                */
/*************************/



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

#define MAX_SIZE 6

struct node {
   int data;
   struct node * next;
};

struct node *first;
struct node *last;

int count;

void make_empty()
{
   first = NULL;
   last = NULL;
   count = 0;
}

int is_empty(void)
{
   return count == 0;
}

int is_full(void)
{
   return count == MAX_SIZE;
}

void push(int insert_value)
{
   last->data = insert_value;
   last->next = first;
   count++;
}

int pop(void)
{
  int i;
  struct node *last, *ptr;
  last = malloc (sizeof(struct node));
  ptr = malloc (sizeof (struct node));

  if (last == NULL || ptr == NULL) {
     printf("\nThere was error in allocating memory.\n");
     exit(EXIT_FAILURE);
  }

  if (is_empty())  {
     printf("Error in pop: stack is empty.\n");
     exit (EXIT_FAILURE);
  }

  for (last = first ; last != NULL; last = last->next)
  {
      if (last->next != NULL)  {
          ptr = last;
      }

      i = last->data;
  }
  ptr->next = NULL;
  free(last);
  count--;
  return i;

}

void print_list()
{
  struct node *ptr;
  if (first == NULL) {
    printf("List is empty.\n\n");
  }

  else  {
       printf("\n\nHere is your list:  \n");
       for (ptr=first;ptr;ptr=ptr->next)
           printf("%d\n",ptr->data);
       return;
  }
}

Sayeh · 12-05-2001

Okay, part of your problem with this is that you are confusing the concept of pointers and allocation of structs.

Let's look at your 'pop' function---

***

int pop(void)
{
int i;
struct node *last, *ptr;
last = malloc (sizeof(struct node));
ptr = malloc (sizeof (struct node));

if (last == NULL || ptr == NULL) {
printf("\nThere was error in allocating memory.\n");
exit(EXIT_FAILURE);
}

if (is_empty()) {
printf("Error in pop: stack is empty.\n");
exit (EXIT_FAILURE);
}

for (last = first ; last != NULL; last = last->next)
{
if (last->next != NULL) {
ptr = last;
}

i = last->data;
}
ptr->next = NULL;
free(last);
count--;
return i;

}

***

Why are you allocating 'last' and 'ptr'? These should have already been allocated onto the list when push() was called. pop merely gets rid of things so you should be setting 'last' and 'ptr' to the address of structs already allocated. You then dispose of them and clear 'last' and/or 'ptr' to null.

And let's correctly typedef 'node'. If you don't do it this way, you are creating an incomplete type (see C99).

typedef struct nodeTag
{
int data;
struct nodeTag *next;
}node;

Think of it another way-- If I have your house address and my house address, I have two pointers. One points to your house, the other points to my house. That's all a pointer does.

If you malloc() against either of these pointers, what your saying is, that you want the pointer to point to an entirely new house-- one you've just allocated. Let's say we've just malloc() 'last'.

Like so, last = (node*)malloc(sizeof(node));

Now, after you've malloc() against, let's say 'last', you then turn around and say 'last = first;' what happens?

Well, you just told last to no longer point at the memory you just allocated (so it is block you just lost-- it's allocated but you can no longer get to it), and the pointer 'last' now points to the structure 'first'.

A pointer is just a long. 4-bytes in length (on 32-bit processors). It can hold a value of up to 4GB. Which means it can 'point at' any memory address from -2GB to +2GB.

In your example, you have to find the last node each time. In reality however, both first & last should be valid all the time.

/* first should already be pointing somewhere. if NULL, nothing is on the stack, just return. In keeping with your example, I will find the last node */

int pop(void);

int pop(void)
{
node *current;
int i;

i = NODATA; /* init enumerated flag */

last = first; /* put last to head of list */
if(!last) /* last & first both NULL, bail */
return(i); /* have to return something */

while(last->next) /* is there a node below this one? */
{
current = last; /* remember where we are */
last = last->next;
};

i = last->data; /* get the value */
free(last); /* eliminate the 'last' node */
current->next = NULL; /* cleanup the pointer */
last = current; /* make last valid */

return(i);
}

---------

Enjoy. You can make mods as necessary to make it return errors the way you want.

**sballew** · 12-05-2001

Got it to work. Thanks.

Thread: queue implementation not working

Thread Tools

Search Thread

Display

queue implementation not working

Similar Threads

Priority Queue Help

Binary Search Trees Part III

Request for comments

queue help

queue linked implementation