Thursday, October 29, 2015

Data Structures - Linked Lists Part 2 (and Queues)


This is a second part to my first post about Arrays and Linked lists. Here I have (finally) implemented and tested two separate queues. Notice that you probably wouldn't need a queue structure if you are utilizing only one queue. The queue structure is so that I can use several different queues. Lots and lots of comments to guide you through:

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

typedef struct mynode{ //this is the node structure, which includes a data int
  int data;            //and a pointer to the next node
 struct mynode* next;
}node;

typedef struct{ //this is the queue structure, which includes a head and tail pointer.
  node* head;   //a head and a tail pointer points to the first and last nodes of a queue
  node* tail;
}queue;

void enqueue(queue* que, int new_data); //here a list of the function prototypes
void dequeue(queue* que);
int take_queue_data(queue* que);
void print(queue* que);

int main()  //main function to test out
{
    //test cases hereeee
    queue* testq1 = (queue*)malloc(sizeof(queue));
    queue* testq2 = (queue*)malloc(sizeof(queue));
    enqueue(testq1, 1); print(testq1);
    enqueue(testq2, 2); print(testq2);
    enqueue(testq1, 3); print(testq1);
    enqueue(testq2, 4); print(testq2);
    enqueue(testq1, 5); print(testq1);
    enqueue(testq2, 6); print(testq2);
    dequeue(testq1); print(testq1);
    dequeue(testq2); print(testq2);
    dequeue(testq1); print(testq1);
    dequeue(testq2); print(testq2);
    dequeue(testq1); print(testq1);
    dequeue(testq2); print(testq2);
}

void enqueue(queue* que, int new_data){
  node* tmp = (node*)malloc(sizeof(node)); //make a temporary node
  tmp->data = new_data; //set the node->data to what we want to insert   
  tmp->next = NULL; //the next of that node would just be the nothing.

  if (que->head == NULL && que->tail == NULL){// if queue is empty
    que->head = tmp;// here we set the head and tail to this one node
    que->tail = tmp;// because this is the first node ever
  }
  else{ //if queue isnt empty, then just set it as the new tail.
    (que->tail)->next = tmp; 
    que->tail = tmp;// and then remember to link this node to the last one's "next" pointer
  }
  return;
}//end of enqueue

void dequeue(queue* que){
    node* tmp = que->head; //temporary for head of queue
  if (que->head == NULL){ //in case queue is empty
  printf("Queue is empty! \n");
    return;
  }
  else if(que->head == que->tail){
    que->head = NULL; //delete that last element
    que->tail = NULL; //and everything back to NULL
  }
  else{//there is more than one element in queue
      que->head = (que->head)->next;
  }
  free(tmp); //we cant hold on to this mem space forever, or cannnnn we. :(
}// end of dequeue

int take_queue_data(queue* que){//this will give us the first data in queue
    if(que->head == NULL){
     printf("Queue is empty, nothing to look at.");
     return 0;
    }
    else{
     return (que->head)->data;   
    }
}

void print(queue* que){//this is to look at whole queue
    node* tmp = que->head; //set tmp to the front of the queue to walk
    while(tmp != NULL){
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }    
    printf("\n");
}

I hope this helps you understand a linked list better(or how to implement it). Remember there is a doubly linked list too, and it's simple to implement with a alittle tweaking of this code. :D
If you see any problems, have any suggestions, or have any questions feel free to ask in the comments below!

0 comments:

Post a Comment