Programming - C Queues using Linked Lists

in #programming5 years ago (edited)

    Hello, its me again. I was away for the weekend and didn't manage to find time to upload any post. But, for that reason I will upload 2 posts today. We will talk about Queue Implementation using Linked Lists (next post will be Stacks). I will show you the exact same functions (add, remove, print) that we used with Array Implementation. So, without further do, let's get started.


Queue Linked List Implementation:

    As we already know, a Queue is a Data Structure that implements the FIFO way of getting information. We define the most Data Structures with structs in C. But, because this time we use Lists we will also need a Node for the List. This Node will contain Data and a pointer to the next Node. So our Node looks like this:

typedef struct Node{ 
	int val;
	struct Node *next;
}Node;

    Using this Node definition we can now have our Queue front and rear be Node pointers! So, our Queue struct will contain those 2 pointers and maybe even other information like capacity of Queue and so on...
The Code looks like this:

typedef struct Queue{
	Node *front;
	Node *rear;
}Queue;

Those 2 pointer will be initialized as NULL, that means the Queue is empty!


    The functions will again use a struct variable of type Queue, that will be a pointer (we pass the address) when we add or remove (change the Queue in any way) and be passed as a normal variable when printing (so that we don't lose any information). 


Adding (Enqueue): 

    For adding an Item we can check if Queue is full, when having a capacity variable. 

Afterwards, we create a new Node using the Code we used in Linked Lists like this:

Node *nn;
// create new node
nn = (Node*)malloc(sizeof(Node));
nn->val = val;
nn->next = NULL;

    A special Case is when the Queue is empty, where we set front and rear equal to our new Node. The basic Case simpy adds the new Item at the end using a Current Node Pointer and setting the rear to the new Node.

So, our Code looks like this:

void enqueue(Queue *Q, int val){
	Node *cur, *nn;
	// create new node
	nn = (Node*)malloc(sizeof(Node));
	nn->val = val;
	nn->next = NULL;
	// check if empty
	if(Q->front == NULL){
		Q->front = Q->rear = nn;
	}
	// basic case
	else{
		// set cur to front
		cur = Q->front;
		// find last Node
		while(cur->next != NULL){
			cur = cur->next;
		}
		// insert nn to end
		cur->next = nn;
		Q->rear = nn;	
	}
}


 Removing (Dequeue):  

     When removing an Item we have to check if the Queue is empty that means we return -1. Afterwards, we get the value at the front and then we have 2 cases: When this Item was the only one we set both pointers to NULL, else we simply set the front to the front next pointer. Last, we return our value. 

So, our Code looks like this:

int dequeue(Queue *Q){
	int val;
	// check if empty
	if(Q->front == NULL){
		return -1;
	}
	// get value in front
	val = Q->front->va>l;
	// check if one item inside
	if(Q->front == Q->rear){
		Q->front = Q->rear = NULL;
	}
	// basic case
	else{
		// make front point to next
		Q->front = Q->front->>next;
	}
	//return the value 
	return val;	
}


Printing: 

    For printing I will call the dequeue function as long as there are Items. We could also use a while loop the way we did it in Linked Lists. But, I think it makes more sense using the dequeue function on a struct variable, so that we don't lose information.

So, this is our Code:

void print(Queue Q){
	int val;
	// check if empty
	if(Q.front == NULL){
		printf("Queue is Empty!\n");
		return;
	}
	// call dequeue as long as there are items
	while((val= dequeue(&Q)) != -1){
		printf("%d ", val);
	}	
	printf("\n");
}


Code:  

    Lastly, here a Code that uses those functions so that you know how to set them up. It's almost the same exact Code I used with Arrays.

int main(){
	// initialize Queue
	Queue Q;
	Q.front = Q.rear = NULL;
	print(Q);
	// add 5 to queue
	enqueue(&Q, 5);
	print(Q);
	// add 10 to queue
	enqueue(&Q, 10);
	print(Q);
	// remove from queue
	int val;
	val = dequeue(&Q);
	if(val == -1){
		printf("Queue is Empty!\n");
	}
	else{
		printf("%d\n", val);
	}
	print(Q);		
}


    Thanks for reading. Hope you enjoyed it! :)

Coin Marketplace

STEEM 0.22
TRX 0.06
JST 0.025
BTC 19816.83
ETH 1338.23
USDT 1.00
SBD 2.47