I created a push and pop function in C but do not know how to print them in order

user_14540418 0
Viewed 353

I've recently studied about linked-list and tried to create a push and pop function.

I've successfully created one which look like this.

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

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

struct node* buffer = NULL;

void push(int elem){
  struct node *new_element = (struct node*)malloc(sizeof(struct node));
  new_element->next = buffer;
  new_element->data = elem;
  buffer = new_element;
}

int pop(void){
  int elem = buffer->data;
  struct node *eliminate = buffer;
  buffer = eliminate->next;
  free(eliminate);
  return elem;
}

Afterwards I tried to print them this way:

int main(void) {
  push(5);
  push(7);
  push(8);
  pop();
  printf("%d %d", buffer->data, buffer->next->data);
}

However, the result was 7 5 instead of 5 7. Is there anything wrong with my push function?

stack linked-list c
5 Answers

After you do:

push(5);
push(7);
push(8);

You have the following linked list:

5 <- 7 <- 8 <- buffer

After the pop you have: 5 <- 7 <- buffer

That is why buffer->data is 7 and buffer->next->data is 5.

In order to print the list in the correct order you will need an pointer pointing to the first node. In your case the 5. Also with your approach you should make it a double linked list.

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

struct node* start = NULL;
struct node* buffer = NULL;

void push(int elem){
  struct node *new_element = (struct node*)malloc(sizeof(struct node));
  new_element->next = buffer;
  new_element->data = elem;
  if (buffer == NULL) start = new_element; // this is the magic
  buffer = new_element;
}
user_117792280

Due to the LIFO nature of push 5 - push 7 -push 8 - pop, when 8 is popped (removed from list) only 5 & 7 remain, and these two will appear in reverse of the order in which they were entered.

Furthermore, If you prefer a sorted list of nodes, read on.

"However, the result was "7 5" instead of "5 7". Is there anything wrong with my push function? "

Because the steps do not necessarily have content enter in desired order, you should consider using a sort function in conjunction with printing. Step to a merge sort follow:

MergeSort(headRef)

  1. If the head is NULL or there is only one element in the Linked List

    then return.

  2. Else divide the linked list into two halves.
    FrontBackSplit(head, &a, &b); /* a and b are two halves */

  3. Sort the two halves a and b. MergeSort(a); MergeSort(b);

  4. Merge the sorted a and b (using SortedMerge() discussed here) and update the head pointer using headRef. *headRef = SortedMerge(a, b);

Excerpt code showing sample implementation from here (see link for full example)

/* Driver program to test above functions*/
int main() 
{ 
    /* Start with the empty list */
    struct Node* res = NULL; 
    struct Node* a = NULL; 
  
    /* Let us create a unsorted linked lists to test the functions 
Created lists shall be a: 2->3->20->5->10->15 */
    push(&a, 15); 
    push(&a, 10); 
    push(&a, 5); 
    push(&a, 20); 
    push(&a, 3); 
    push(&a, 2); 
  
    /* Sort the above created Linked List */
    MergeSort(&a); 
  
    printf("Sorted Linked List is: \n"); 
    printList(a); 
  
    getchar(); 
    return 0; 
}

... several other supporting functions

// C code for linked list merged sort 
#include <stdio.h> 
#include <stdlib.h> 
  
/* Link list node */
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
/* function prototypes */
struct Node* SortedMerge(struct Node* a, struct Node* b); 
void FrontBackSplit(struct Node* source, 
                    struct Node** frontRef, struct Node** backRef); 
  
/* sorts the linked list by changing next pointers (not data) */
void MergeSort(struct Node** headRef) 
{ 
    struct Node* head = *headRef; 
    struct Node* a; 
    struct Node* b; 
  
    /* Base case -- length 0 or 1 */
    if ((head == NULL) || (head->next == NULL)) { 
        return; 
    } 
  
    /* Split head into 'a' and 'b' sublists */
    FrontBackSplit(head, &a, &b); 
  
    /* Recursively sort the sublists */
    MergeSort(&a); 
    MergeSort(&b); 
  
    /* answer = merge the two sorted lists together */
    *headRef = SortedMerge(a, b); 
}
user_6451280

What you experience is the correct behavior. In fact your push() / pop() couple implements a LIFO behavior: Last In, First Out (push() and pop() are actually the common interface name of the functions interacting with the stack abstract data type). The order you expect, instead, would have been shown in case of a FIFO implementation (First In, First Out).

Here is the content of your stack step by step:

  1. push(5);: only an element is present

     -----
 | 5 |
 -----
 ^
 |
 buffer

  2. push(7);:

     ---------
 | 7 | 5 |
 ---------
 ^
 |
 buffer

  3. push(8);:

     -------------
 | 8 | 7 | 5 |
 -------------
 ^
 |
 buffer

  4. pop();: the last inserted element (8, last in) is removed (first out)

     ---------
 | 7 | 5 |
 ---------
 ^
 |
 buffer

And this is actually what is printed.

user_113367620

Actually, the code is running correctly, this is what your code is doing:

buff=NULL

after push(5): buff=5->NULL

after push(7): buff=7->5->NULL

after push(8): buff=8->7->5->NULL

after pop(): buff=7->5->NULL

thus buffer->data is 7 and buffer->next->data is 5

user_78405280

You should expect 7, 5 as the output. You implemented a Last In First Out stack. This means that the node with data = 8 is the last node pushed onto the stack and the first one out. When you pop that node you are left with 7 and 5 and 7 is on top of the stack.

Here's a link to a good tutorial about stacks

user_123664890
Related