change stack to a queue

This is a discussion on change stack to a queue within the C Programming forums, part of the General Programming Boards category; Taking my original file stack.c with all the stack functions in it, I need to change so this is a ...

  1. #1
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157

    change stack to a queue

    Taking my original file stack.c with all the stack functions in it, I need to change so this is a queue file.

    What I believe is the only difference is the POP function because in a queue the last item in is the last item out. I know this involves two pointers, but I couldn't follow the example in class. Could someone explain the organization of the POP function?



    here's the stack code

    Code:
    /*****************/
    /*  stack.c      */
    /****************/
    
    #include <stdlib.h>
    #include "stack.h"
    
    struct node {
    
       int data;
       struct node * next;
    };
    
    struct node *first;
    int count;
    
    void make_empty()
    {
       first = NULL;
       count = 0;
    }
    
    int is_empty(void)
    {
       return count == 0;
    }
    
    int is_full(void)
    {
       return 0;
    }
    
    void push(int insert_value)
    {
       struct node *new_node;
    
       new_node=malloc(sizeof(struct node));
       if (new_node == NULL)  {
          printf("Error in push:  stack is full.\n");
          exit (EXIT_FAILURE);
       }
       new_node->data = insert_value;
       new_node->next = first;
       first = new_node;
       count++;
    }
    
    int pop(void)
    {
      struct node * top_node;
      int i;
    
      if (is_empty())  {
         printf("Error in pop: stack is empty.\n");
         exit (EXIT_FAILURE);
      }
    
      printf("%d deleted successfully.\n",first->data);
      top_node=first;
      i = first->data;
      first = first->next;
      free(top_node);
      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;
      }
    }
    Sue B.

    dazed and confused


  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    In the stack, you pushed values to the beginning of the list, and you removed them from the beginning of the list.

    For the queue, you will push items to the end of the list, and remove them from the beginning of the list.

    You can either do this by traversing the list to the end every time you push an element, or maintaining a pointer to the end of the list. I suggest maintaining a pointer to the end of the list.

    Incidentally, this means that the POP function won't have to change... just the PUSH function.
    Callou collei we'll code the way
    Of prime numbers and pings!

  3. #3
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    Darnit my instructor asked in class what needs to change in a stack to make it a successful queue and I raised my hand and said you need to change the POP function and he said "Yes".

    Then he proceeded to write some diagram on the board and I got totally lost. And usually its because he gets confused and mucks the thing up himself and then fixes something and then I am left confused. (Please God give me the understanding to get this stuff).

    My text book does not explain queues. So I have no idea where to start to change my function POP nor why you say to change PUSH.

    Please explain...

    There are two pointers needed. One to point to the first node and one to point to the last node. One moves one direction and the other moves in the other direction. What evaluation are you making to make sure you are at the beginning when moving backwards from the end to beginning??
    Sue B.

    dazed and confused


  4. #4
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    you originally had a stack as a one ended structure. You pushed onto the top and popped from the top.To change a stack to a queue you open the bottom of the stack up so that the push still goes to the top of the stack but the pop will come from the bottom of the stack rather than the top. Very simple really.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  5. #5
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    probably I mangled this queue file all to he** but I have to start somewhere to go forward and get it right.

    I tried to make notes throughout program to show you my questions and hopefully highlight the areas that I need advice for, give me direction if I am going about this in the wrong way. Please....and be NICE.


    Code:
    /*****************/
    /*  queue.c      */
    /*****************/
    
    #include <stdlib.h>
    #include "stack.h"
    
    struct node {
    
       int data;
       struct node * next;
    };
                            /*  declaring the pointers to the first and last nodes of queue   */
    struct node *first;
    struct node *last;
    int count;
    
    void make_empty()      /*  do I initialize  last  here as well? */
    {
       first = NULL;
       count = 0;
    }
    
    int is_empty(void)  /*   i think this is left unchanged   */
    {
       return count == 0;
    }
    
    int is_full(void)       /*  ain't sure what goes here   */
    {
       return 0;
    }
    
    void push(int insert_value)
    {
       struct node *new_node;
       /*  do I need a second pointer to alloc memory to :   like last_node  or something  ???   */   
    
       new_node=malloc(sizeof(struct node));
       if (new_node == NULL)  {
          printf("Error in push:  stack is full.\n");
          exit (EXIT_FAILURE);
       }
       new_node->data = insert_value;
       new_node->next = first;
       first = new_node;
       count++;
    }
    
    int pop(void)
    {    /*  okay here's where I am sure I have mucked things up   PLEASE HELP   */
      struct node * head;
      struct node * tail;  
      int i,j;
    
      if (is_empty())  {
         printf("Error in pop: stack is empty.\n");
         exit (EXIT_FAILURE);
      }
         /*  I am sure I don't need this statement  *
      printf("%d deleted successfully.\n",first->data);
    
       /*  is any of this close to right, two pointers, one pointing to the first node, one pointing to the last node  */
      head=first;
      tail=last;
      i = first->data;
      j = last->data;
      first = first->next;
      last = NULL;
      free(head);
      count--;
      return i;   /*  and do i return i only */  
    }
    
    void print_list()    /* anything here need to change  */
    {
      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;
      }
    }
    Sue B.

    dazed and confused


  6. #6
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Hmm... this gets a bit complicated in a way... Let me attempt an example...
    Code:
    1. Wake Up <- first
    2. Eat Breakfast
    3. Feed the Pets
    4. Exercise <- last
    Okay, there's my queue. Let me point out that this is a linked list, going from first, to last (to NULL). Now, let's say I have completed the first queue task, and want to remove it from the queue...
    Code:
    1. Wake Up <- free() me
    2. Eat Breakfast <- first
    3. Feed the Pets
    4. Exercise <- last
    All we really did here was made first point to the next node of the list... and that's it. The first item in the queue is gone. This works the same way your stack pop() function worked... it just moves first to the next element in the queue.

    Pushing is a little different. Obviously we don't want to push at the beginning of the queue...
    Code:
    2. Eat Breakfast <- first
    3. Feed the Pets
    4. Exercise
    5. Program <- last
    Okay, so we just pushed something to the queue. And the procedure for doing it? Just add it to the end of the list. Maintaining a pointer to the end of the list makes this very simple, although it also means we have to remember to update last after each time we add a new node.


    Now there's the special cases...
    What if the list is empty?
    First off, if the queue is empty, then first = NULL
    Obviously, pop() just shouldn't work, that's easy to implement.
    push () expects us to allocate a node and make last -> next = newnode. We can't do that though, since there isn't any queue to put this new node on. There are some elegant ways to do this, but really, it's easiest just to detect whether the list is empty when you push, and if it is, then you still allocate a new node, but then you just let first = last = newnode.

    You may want to change your pop function to make things easier, but you really don't have to. In the stack, you popped from the beginning of the list, in the queue you pop from the beginning of the list, and that's all there is to it.

    Just change your push to add to the end of the list, using the pointer last.
    Callou collei we'll code the way
    Of prime numbers and pings!

  7. #7
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    I am not following your line of thought.
    I was told only to change the POP function.
    Do I have to change both the POP and PUSH??
    Sue B.

    dazed and confused


  8. #8
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Queues:
    1. To push, you add an element to the end of the list.
    2. To pop, you remove the first element in the list.
    3. Remember to update the appropriate pointers when you push and pop.
    4. You'll probably have to make a special case for adding to an empty list, or removing from a 1-element list to keep your pointers consistent, although it is possible that your implementation will not require either or both of these special cases.


    Points 1 and 2 are really what you have to worry about. You will absolutely, positively, have to change your push function. Your pop function, you should only make minor changes to from the stack implementation, because it already removes the first element in the list.

    Your PUSH function, I suggest you just delete the entire body of the function, and rewrite it from scratch.

    The other functions, you are going to code them according to how PUSH and POP are coded.

    I am not really sure why your professor told you the complete opposite what I am telling you. Perhaps your professor was thinking of an array implementation of a stack and queue, in which case, his advice would be correct.
    Callou collei we'll code the way
    Of prime numbers and pings!

  9. #9
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    here's a sample of a queue that a friend sent me.
    I guess it works, however, I cannot theoretically use this as we were instructed to use the same interface as our stack.c file.

    So I want to know how to incorporate what is here into my existing stack.c file.

    The biggest confusing factor to this for me is that the functions for the queue are not the same names (and therefore not same functions in essence) as my stack.c file...

    The other two confusing things are
    1) I am not familiar with things such as (int Q **tail, Q **head, int item) which are the parameters of the insert1 function. I never used a variable pointer to a pointer. Is there a simpler method to do what this function is doing??

    2) I am assuming I don't really have to change much in my stack.c functions, including changing the parameters of the most if any of the functions, but this code is passing variables in the rem (assuming POP) function and my stack did not. In trying to stay with the same interface, do I have to pass anything to the POP in my queue???

    What I have preferred to do at all in learning the C language was find code that is simplest to follow to do the desired things/functions. I never straight copy anyone's code, for I find that I don't learn a darned thing, unless they put ample remarks in their code showing the purpose of the functions or code statements/expressions. So I am really intending on submitting code that makes sense to me, not just copy someone else's work for a grade.


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define QSIZE 6
    
    int count;
    /*count is global because it needs to be changed by insert and remove fxs*/
    
    typedef struct tag{
         int n;
         struct tag * next;
    }Q;
          
    /* in my stack there is a make_empty, pop and push and not a
        rem, insert, or insert1 functions; the only three that are here
       and in my stack are the 1st three.
    */
    
    void initialize();         
    int empty();
    int full();
    int rem(Q *, Q *);
    void insert(Q *, Q *, int);
    void insert1(Q **, Q **, int);
    
    main()
    {
       Q *tail, *head, *ptr;
       int code, code1, i, n;
       int i1, i2;
    
       tail = malloc (sizeof(Q));
       if (tail == NULL) {
          printf("malloc failed to allocate storage - exit \n");
          exit;
       }
    
       head = malloc (sizeof(Q));
       if (head == NULL) {
          printf("malloc failed to allocate storage - exit \n");
          exit;
       }
    
       tail->next = head;
       head->next = NULL;
    
       initialize();
       printf("Initially the queue is is empty?1=Yes 0=No\n %d\n", empty());
       printf("Intially the queue is full?1=Yes 0=No\n %d\n", full());
    
       printf("Enter 1 to continue, 0 to stop: ");
       scanf("%d", &code);
       while(code!=0)
       {  printf("Enter 2 to insert an item, 3 to remove an item: ");
          scanf("%d", &code1);
          switch(code1)
          {   case 2: printf("Enter an integer to be inserted: ");
                      scanf("%d", &i1);    
                      if (count == 0 || count == 1)
                      {insert(tail, head, i1); break;}
                      if (count > 1)
                      insert1(&tail, &head, i1);
                      break;
              case 3: i2=rem(tail, head);
                      if(i2==0)
                        printf("Nothing is removed\n");
                      else
                        printf("%d is removed\n", i2);
                      break;
              default: printf("Wrong code\n");
          }
          printf("Currently in the queue:\n");
          if(count==0)
             printf("Nothing\n");
          else 
          { 
           if (count == 1)
            printf("%d    ", head->n);
           else
           {
            for (ptr=tail; ptr != NULL; ptr=ptr->next)
             printf("%d    ", ptr->n);
           }
           printf("\n");
          } 
    
       printf("Enter 1 to continue, 0 to stop: ");
       scanf("%d", &code);
       }
       return 0;
    }
    
    void initialize()
    {
        count=0;
    }
    
    int empty()
    {
       if (count == 0)
       { printf("QUEUE IS EMPTY\n");
         return 1;
       }
       else return 0;
    }
    
    int full()
    {
       if (count == QSIZE) 
       {  printf("QUEUE IS FULL\n");
          return 1; 
       }
       else return 0;
    }
     /*  What is this function doing?  Is it the POP function?
      rem = remove ???   
    */
    int rem(Q *tail, Q *head)
    {
       int temp;
       Q *prev, *cur;
       prev = tail;
       cur = tail->next;
    
       if (empty()) 
       {printf("Error\n");
        return 0;
       }
    
       while (cur->next != NULL)
       { prev = cur;
         cur = cur->next;
       }
    
       temp = cur->n;
       free(cur);
       prev->next = NULL;
       head = prev;
       count--;
       
       return temp;
    }
     /*  I am guessing this is a POP function but there are 
    two insert functions here, what is the second one for??? 
    */
    void insert(Q *tail, Q *head, int item)
    {
       if (full()) 
       {printf("Queue is full. Overflow!\n");
        return; }
    
       if (count == 0)
       { head->n = item;
         count++; 
         return; }
       
       if (count == 1)
       { tail->n = item;
         count++;
         return; }
    
    }
     
    void insert1(Q **tail, Q **head, int item)
    {
      Q *new;
    
      if (full()) 
       {printf("Queue is full. Overflow!\n");
        return; }
    
      new = malloc(sizeof(Q)); 
      if (new == NULL) {
       printf("malloc failed to allocate storage - exit \n");
       exit;  }
      new->n = item;
      new->next = *tail;
      *tail = new;
      count++;
      return; 
    }
    Sue B.

    dazed and confused


  10. #10
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Egh... okay, that code you posted is trying to pop from the end of the list and push to the beginning... but it's really straining to do it. Trust me, this can be done much simpler.

    The Q ** stuff is because... well, that just means that he needs that function to change the value of a Q *, so he passes it by address. Using global variables, this isn't really a problem.
    Code:
    Q * head, tail;
    
    // These are just linked list functions...
    void add2Head (int addMe);
    int remHead (void);
    void add2Tail (int addMe);
    int remTail (void);
    
    // Adds node to beginning of list.
    // No problems with head == NULL.
    void add2Head (int addMe)
    {
     Q * temp;
     temp = malloc (sizeof (Q));
     temp -> next = head;
     temp -> info = addMe;
     head = temp;
     return;
    }
    
    // Removes first node in the list.
    // Problems if head == NULL.
    int remHead (void)
    {
     Q * temp;
     int i;
     i = head -> info;
     temp = head;
     head = head -> next;
     free (temp);
     return i;
    }
    
    // Adds node to end of list.
    // Problems with tail == NULL.
    void add2Tail (int addMe)
    {
     Q * temp;
     temp = malloc (sizeof (Q));
     temp -> next = NULL;
     temp -> info = addMe;
     tail -> next = temp;
     tail = temp;
     return;
    }
    
    // Removes last node in the list.
    // Problems with head == NULL.
    // Problems with tail == NULL.
    int remTail (void)
    {
     Q * temp;
     int i;
     i = tail -> info;
    
     // This for loop is why we pop from the beginning, not the end.
     for (temp = head; temp -> next != tail; temp = temp -> next);
     
     free (tail);
     tail = temp;
     return i;
    }
    This code should work I think.. as long as they have access to tail and head. Looking at these functions, we only have 1 cardinal rule... DON'T USE remTail! Every time we call it, it will have to traverse the entire list. Now, using these functions, lemme implement a stack. All we really have to do for this is make sure we add and remove from the same end. Since we aren't gonna use remTail, we'l have to remove and add from the head.
    Code:
    void initialize (void)
    {
     head = NULL;
     return;
    }
    
    int is_empty (void)
    {
     return (head == NULL);
    }
    
    int is_full (void)
    {
     return 0;
    }
    
    void push (int i)
    {
     if (!is_full())
     {
      add2Head (i);
     }
    }
    
    int pop (void)
    {
     int i;
     if (!is_empty ())
     {
      i = remHead ();
     }
     return i;
    }
    It doesn't give intelligent responces to an empty or full stack really, but it should work. Now let's implement a queue using the linked list. What's important for a queue is that we add on one side, and take away from the other. Since we won't use remTail, we'll use remHead and add2Tail.
    Code:
    void initialize (void)
    {
     // It's possible to do this by only assigning one of these variables
     //  to NULL, but I assign both here for completeness.
     head = NULL;
     tail = NULL;
     return;
    }
    
    int is_empty (void)
    {
     // Same as initialize ()... just doin' it for completeness.
     return (head == NULL || tail == NULL);
    }
    
    int is_full (void)
    {
     return 0;
    }
    
    void push (int i)
    {
     if (!is_full())
     {
       if (is_empty ())
       // There are problems with adding to an empty queue.  First off, 
       //  we can't add2Tail with tail = NULL, so we'll use add2Head.
       //  Second off, we have to make sure that both tail and head
       //  point to the single variable of the queue when we empty it.
       {
        add2Head (i);
        tail = head;
       }
       else add2Tail (i); // Normally, we just add2Tail.
     }
    }
    
    int pop (void)
    {
     int i;
     if (!is_empty)
     {
      i = remHead ();
     }
     // remHead only modifies the value of head, not tail.  But, if we
     //  manage to remove the last element in the queue with remHead
     //  then the queue is empty and tail doesn't have anything to point
     //  to, so we assign it to NULL.
     if (is_empty ()) tail = NULL;
     return i;
    }
    Notice how similar the stack pop() and the queue pop() is. It wouldn't be all that tough to implement a queue that adds to the head of the list and removes from the tail using these functions, but no matter how you look at it, removing the tail of the list is going to involve a list traversal, which is more complicated than it is worth.

    As usuall, I haven't actually compiled the code, so it'll prolly not compile, but it should be readable anyhow.
    Last edited by QuestionC; 12-02-2001 at 08:54 PM.
    Callou collei we'll code the way
    Of prime numbers and pings!

  11. #11
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    only question I have right now is when my instructor says the queue functions have the same interface as the stack functions, does that mean that there is only one push and one pop function?? I ask because all queue function samples I have seen have a push for the head and a push for the tail and one pop. HE didn't say anything about that.

    Let's see if I get this :

    (1) make_empty the queue first (just like in stack)
    (2) push a value from main (checking if queue is_full first)
    (3) continue pushing values until queue is_full
    (4) try to push one too many values, and get overflow message
    (5) then pop off 3 values

    Now why would there be a push to both ends, tail and head?
    Why would you remove values from both ends??
    I thought you pushed to the tail and popped from the head

    line of people at ticket booth
    guy 1st in line is the head
    guy last in line is the tail
    1st guy gets ticket, and leaves (popping)
    another guy comes to get into line at tail (pushing)

    So again I ask, why are there two insert (push) functions in the following program??? There is only one remove (pop) function.

    Maybe someone could just explain what the insert function is doing and what the insert1 function is doing...


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define QSIZE 6
    
    int count;
    /*count is global because it needs to be changed by insert and remove fxs*/
    typedef struct tag{
         int n;
         struct tag * next;
    }Q;
          
    void initialize();
    int empty();
    int full();
    int rem(Q *, Q *);
    void insert(Q *, Q *, int);
    void insert1(Q **, Q **, int);
    
    main()
    {
       Q *tail, *head, *ptr;
       int code, code1, i, n;
       int i1, i2;
    
       tail = malloc (sizeof(Q));
       if (tail == NULL) {
          printf("malloc failed to allocate storage - exit \n");
          exit;
       }
    
       head = malloc (sizeof(Q));
       if (head == NULL) {
          printf("malloc failed to allocate storage - exit \n");
          exit;
       }
    
       tail->next = head;
       head->next = NULL;
    
       initialize();
       printf("Initially the queue is is empty?1=Yes 0=No\n %d\n", empty());
       printf("Intially the queue is full?1=Yes 0=No\n %d\n", full());
    
       printf("Enter 1 to continue, 0 to stop: ");
       scanf("%d", &code);
       while(code!=0)
       {  printf("Enter 2 to insert an item, 3 to remove an item: ");
          scanf("%d", &code1);
          switch(code1)
          {   case 2: printf("Enter an integer to be inserted: ");
                      scanf("%d", &i1);    
                      if (count == 0 || count == 1)
                      {insert(tail, head, i1); break;}
                      if (count > 1)
                      insert1(&tail, &head, i1);
                      break;
              case 3: i2=rem(tail, head);
                      if(i2==0)
                        printf("Nothing is removed\n");
                      else
                        printf("%d is removed\n", i2);
                      break;
              default: printf("Wrong code\n");
          }
          printf("Currently in the queue:\n");
          if(count==0)
             printf("Nothing\n");
          else 
          { 
           if (count == 1)
            printf("%d    ", head->n);
           else
           {
            for (ptr=tail; ptr != NULL; ptr=ptr->next)
             printf("%d    ", ptr->n);
           }
           printf("\n");
          } 
    
       printf("Enter 1 to continue, 0 to stop: ");
       scanf("%d", &code);
       }
       return 0;
    }
    
    void initialize()
    {
        count=0;
    }
    
    int empty()
    {
       if (count == 0)
       { printf("QUEUE IS EMPTY\n");
         return 1;
       }
       else return 0;
    }
    
    int full()
    {
       if (count == QSIZE) 
       {  printf("QUEUE IS FULL\n");
          return 1; 
       }
       else return 0;
    }
    
    int rem(Q *tail, Q *head)
    {
       int temp;
       Q *prev, *cur;
       prev = tail;
       cur = tail->next;
    
       if (empty()) 
       {printf("Error\n");
        return 0;
       }
    
       while (cur->next != NULL)
       { prev = cur;
         cur = cur->next;
       }
    
       temp = cur->n;
       free(cur);
       prev->next = NULL;
       head = prev;
       count--;
       
       return temp;
    }
    
    void insert(Q *tail, Q *head, int item)
    {
       if (full()) 
       {printf("Queue is full. Overflow!\n");
        return; }
    
       if (count == 0)
       { head->n = item;
         count++; 
         return; }
       
       if (count == 1)
       { tail->n = item;
         count++;
         return; }
    
    }
     
    void insert1(Q **tail, Q **head, int item)
    {
      Q *new;
    
      if (full()) 
       {printf("Queue is full. Overflow!\n");
        return; }
    
      new = malloc(sizeof(Q)); 
      if (new == NULL) {
       printf("malloc failed to allocate storage - exit \n");
       exit;  }
      new->n = item;
      new->next = *tail;
      *tail = new;
      count++;
      return; 
    }
    Sue B.

    dazed and confused


  12. #12
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    I have been foolin with this all day and still not sure what is going on.

    I need a source file that has just the queue functions in it and all things pertaining to a queue

    I need a source file that has the main() function in it that runs the queue program.

    I need a variable called count that keeps track of # of items in queue.

    I need to limit the size of the queue to 6 items (ie. #define MAX_SIZE 6)

    I need to use the functions I have listed ; named as they are. Only minor changes to function definitions are allowed.

    Here's the queue.c file with all queue functions (I need help with push and pop still--maybe others)
    Code:
    #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;
    
      if (is_empty())  {
         printf("Error in pop: stack is empty.\n");
         exit (EXIT_FAILURE);
      }
    
      i=first->data;
      free(first);
      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;
      }
    }
    And here is the source file with the main() function
    It has multitudes of problems, I am sure. I tried converting instructors code with implementation of queue through arrays, but fail to follow the logic of some of it.

    Code:
    #include <stdio.h>
    #define MAX_SIZE 6
    
    
    main()
    {
    
        int run, choice, num, i, n;
    
        make_empty();
    
        printf("Is queue empty at start?\n %d\n",is_empty());
        printf("Is queue full at start?\n %d\n",is_full());
    
        printf("Enter 1 to continue or 0 to stop :");
        scanf("%d", &run);
    
        while (run != 0)   {
    
          printf (" Enter 2 to insert an item into queue\n"
                  " Enter 3 to remove an item from queue\n");
          scanf("%d",&choice);
    
          switch (choice)   {
    
            case 2 :  printf("Enter any number to be inserted:");
                      scanf("%d", &num);
                      push(num);
                      break;
    
            case 3 :  num = pop();
                      if (num == 0)
                         printf("Nothing was removed\n");
                      else
                         printf("%d was removed\n",num);
                      break;
    
            default : printf("You entered invalid choice\n");
          }
    
          printf("Currently in your queue :\n");
    
          if (is_empty)
             printf("There's nothing in the queue.\n");
    
          else    {
             i = first;
             n = 0;
    
          do {
             printf ("%d ", i);
             n++
             if (i>=MAX_SIZE-1)
                i = 0;
             else
                i++;
          } while (n<count);
    
          printf("\n");
       printf("Enter 1 to continue or 0 to stop :");
       scanf("%d",run);
       }
    return 0;
    }
    Sue B.

    dazed and confused


  13. #13
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    That other source file you posted, the one with 2 insert functions... to tell you the truth, I'm not too sure how that one is supposed to work. There isn't any reason for it to have that.

    The problem with yourpush and pop functions is that when you push, you have to malloc a new node, and put it on the end of the list (last -> next). Then you have to update last to point at this new node.

    For push, you are remembering to free the first node, but you are forgetting to update first so that it points at the new first node.

    Really, the code that I posted works... it just needs some includes and a typedef for Q.
    (There is one bug... in function pop(), there is a call to is_empty that needs marks of parenthesis added.)

    First, I suggest writing code that can succesfully remove the first element from the list and update first to point at the new beginning...
    then write a bit of code that can succesfully add an element to the end of the list and update last to point to the new last node.
    Your pop function will revolve around removing from the head, and your push will revolve around adding to the tail. After you get those down, it's just about handling the special cases.
    Callou collei we'll code the way
    Of prime numbers and pings!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pushing a Queue onto a Stack?
    By MiroMage in forum C Programming
    Replies: 5
    Last Post: 10-14-2008, 10:23 PM
  2. Stack and Queue
    By audinue in forum C Programming
    Replies: 7
    Last Post: 07-04-2008, 01:28 PM
  3. stack implementation problem-help needed
    By sanju in forum C Programming
    Replies: 1
    Last Post: 12-10-2002, 07:29 AM
  4. HEap and stack, I'm confused
    By indigo0086 in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 10-31-2002, 10:59 AM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 12:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21