Thread: 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

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

Thanks a lot for the answer,

Really appreciate the help!