LIFO with linked list question

This is a discussion on LIFO with linked list question within the C Programming forums, part of the General Programming Boards category; Hello all, I have been working on this assignment for a few nights now, and I am having a wee ...

  1. #1
    Registered User
    Join Date
    May 2004
    Posts
    10

    LIFO with linked list question

    Hello all,

    I have been working on this assignment for a few nights now, and I am having a wee bit of a problem with it. It is probably something stupid and I will want to kick myself afterwards, but here goes;

    This is the first time that I am working with Linked List and it is, slowly, beginning to sink in (I think..... maybe...). Anyway I am not done yet, but basically what I need to do is add the following elements in the stack, for example 1,2,3,4,5 then when I view the stack it should display 5,4,3,2,1.

    My problem is that after entering 1-2-3-4-5 when I display the stack I always get 4-3-2-1-0 ! and I can't put my finger on what it is I am doing wrong. Could someone please point out where the error is?

    The code is below, please focus on the push() function, I believe this is where the error is.

    Code:
    /*
    Stack is a LIFO (last in first out) data structure. Push adds an element at the
    head and pop deletes an element from the head. Implement a Stack with 
    pop/push/display methods using the Linked Data Structure 
    
    */
    
    
    #include <stdio.h> 
    #include <stdlib.h> 
    
    struct Node{ 
        char data; 
        struct Node *next;  
    }; 
    
    struct Queue{ 
        struct Node *head; 
        struct Node *tail; 
    }; 
    
    main(){ 
    
        struct Queue myQueue;struct Node*temp; 
        int choice=1,data; 
        myQueue.head = (struct Node *)malloc(sizeof(struct Node)); 
        myQueue.tail = myQueue.head; 
        myQueue.head->next = NULL; 
    
        while(choice){ 
            puts("\n1. Display The Stack"); 
            puts("2. Push a value ."); 
            puts("3. Pop a value."); 
            puts("0. Exit \n"); 
            puts(" Enter your choice and Press ENTER."); 
            scanf("%d",&choice); 
            switch(choice){ 
                    case 1: temp =myQueue.head->next; 
                            if(!isEmpty(&myQueue)){ 
                               printf("\n\nStack now contains:\n\n"); 
                               while (temp !=NULL){ 
                                 printf(" %d ",temp->data); 
                                 temp=temp->next; 
                               } 
                            } 
                            else 
                                    printf("\n\nStack is empty\n\n"); 
                            break; 
                            
                    case 2: puts("\n\nEnter an integer"); 
                            scanf("%d",&data); 
                            push(&myQueue,data); 
                            break;
                             
                    case 3: if(!isEmpty(&myQueue)){ 
                                data= pop(&myQueue); 
                                printf(" Pop: %d \n",data); 
                            } 
                            else 
                                    printf("\nStack is empty\n"); 
                            break; 
                    default: break; 
            } 
        } 
    } 
    
    push(struct Queue *q,int data){ 
    
        struct Node *newNode; 
        if ((newNode=(struct Node *)malloc(sizeof(struct Node))) == NULL) 
            return 0; 
        newNode->next = NULL; 
        newNode->data = data; 
        if (q->head == NULL)
            q->head = newNode;
        else    
        newNode->next=q->head; 
        q->head = newNode; 
    } 
    int pop(struct Queue* q){ 
        int dqueuedElt; 
      
        struct Node *oldnode; 
        oldnode = q->head->next; 
        dqueuedElt = oldnode->data; 
    
        if (q->head->next->next == NULL){ 
            printf("\nlast node\n"); 
            q->tail = q->head; 
        } 
        else 
            q->head->next = q->head->next->next; 
        free(oldnode); 
    
        return dqueuedElt; 
    } 
    
    int isEmpty(struct Queue* q){ 
        if(q->head==q->tail) 
            return 1; 
        else 
            return 0; 
    }
    Thank you in advance

  2. #2
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    in function push
    Code:
        if (q->head == NULL)
            q->head = newNode;
    if the queue is empty make q->head the first element seems ok
    but when printing the queue
    Code:
     temp =myQueue.head->next; // set temp to the 2nd element ??
        if(!isEmpty(&myQueue)){ 
            printf("\n\nStack now contains:\n\n"); 
            while (temp !=NULL){ 
                printf(" %d ",temp->data); 
                temp=temp->next; 
          }
    Kurt

    edit: q->head should never become null because it is initialized to a dummy node in the beginning of main.
    So the real mistake must be in the push function.
    Last edited by ZuK; 09-15-2005 at 03:37 AM.

  3. #3
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Made a few modifications. Now it seems to work.
    Code:
    /*
    Stack is a LIFO (last in first out) data structure. Push adds an element at the
    head and pop deletes an element from the head. Implement a Stack with 
    pop/push/display methods using the Linked Data Structure 
    
    */
    
    
    #include <stdio.h> 
    #include <stdlib.h> 
    
    struct Node{ 
        char data; 
        struct Node *next;  
    }; 
    
    struct Queue{ 
        struct Node *head; 
        struct Node *tail; 
    }; 
    
    main(){ 
    
        struct Queue myQueue;struct Node*temp; 
        int choice=1,data; 
    //    myQueue.head = (struct Node *)malloc(sizeof(struct Node)); // removed dummy node
        myQueue.head = NULL; 
        myQueue.tail = myQueue.head;  // empty if both point to NULL
    //    myQueue.head->next = NULL; 
    
        while(choice){ 
            puts("\n1. Display The Stack"); 
            puts("2. Push a value ."); 
            puts("3. Pop a value."); 
            puts("0. Exit \n"); 
            puts(" Enter your choice and Press ENTER."); 
            scanf("%d",&choice); 
            switch(choice){ 
                    case 1: // temp =myQueue.head->next; 
                            if(!isEmpty(&myQueue)){ 
    			   temp =myQueue.head; 
                               printf("\n\nStack now contains %d element:\n\n", count( &myQueue )); 
    //                           while (temp !=NULL){ 
                               while (temp !=myQueue.tail){  
                                 printf(" %d ",temp->data); 
                                 temp=temp->next; 
                               } 
                            } 
                            else 
                                    printf("\n\nStack is empty\n\n"); 
                            break; 
                            
                    case 2: puts("\n\nEnter an integer"); 
                            scanf("%d",&data); 
                            push(&myQueue,data); 
                            break;
                             
                    case 3: if(!isEmpty(&myQueue)){ 
                                data= pop(&myQueue); 
                                printf(" Pop: %d \n",data); 
                            } 
                            else 
                                    printf("\nStack is empty\n"); 
                            break; 
                    default: break; 
            } 
        } 
    } 
    
    push(struct Queue *q,int data){ 
    
        struct Node *newNode; 
        if ((newNode=(struct Node *)malloc(sizeof(struct Node))) == NULL) 
            return 0; 
        newNode->next = NULL; 
        newNode->data = data; 
        if (q->head == NULL)
            q->head = newNode;
        else    
        newNode->next=q->head; 
        q->head = newNode; 
    } 
    
    int pop(struct Queue* q){ 
        int dqueuedElt; 
      
        struct Node *oldnode; 
        oldnode = q->head; 
        dqueuedElt = oldnode->data; 
    
        if (q->head->next== q->tail){ 
            printf("\nlast node\n"); 
            q->tail = q->head = NULL;  // now it's empty
        } 
        else 
            q->head = q->head->next; 
        free(oldnode); 
    
        return dqueuedElt; 
    } 
    
    int isEmpty(struct Queue* q){ 
        if(q->head==q->tail) 
            return 1; 
        else 
            return 0; 
    }
    // added count
    int count( struct Queue* q ) {
       int c = 0;
       struct Node *temp;
       temp =q->head; 
       while (temp !=q->tail){ 
          c++;
          temp=temp->next; 
       } 
       return c;
    }
    This Version works but it never updates q->tail.
    Kurt

  4. #4
    Registered User
    Join Date
    May 2004
    Posts
    10

    Smile Thank you Zuk

    Thanks a lot for the answer,

    Really appreciate the help!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 04:05 PM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  3. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM
  4. linked list question
    By yeahdixon in forum C++ Programming
    Replies: 2
    Last Post: 03-28-2002, 09:16 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

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