Queue Implementation Using Linked List

Source Code:

#include <iostream>
#include <stdlib.h> // included to use malloc function
using namespace std;

// node/element structure
struct node {
    int data; // store value
    node *next; // store address of next element
}; // struct ends with semicolon

node *head = NULL; // intial node of queue

// function for insertion operation
void enqueue (int val) {
    // creating new node
    node *temp = (node*)malloc(sizeof(node));
    // assigning value to its data part
    temp->data = val; 
    // storing NULL to its pointer part
    temp->next = NULL;
    if(head == NULL) {
            head = temp; // For first insertion
    } else {
        node *ptr = head; // ptr is used for traversal
            // while loop is used to approach last element
            while(ptr->next != NULL) {
                ptr = ptr->next;
            }
            // assiging address of new node to last node
            ptr->next = temp;
    }
    cout<<val<<" is inserted in Queue successfully!...."<<endl;
}

// function for deletion operation
void dequeue() {
    // checking either queue is empty
    if(head == NULL) {
        cout<<"Queue is empty!....."<<endl;
        return;
    }
        // Displaying data from head node
        cout<<head->data<<" Removed From Queue!......"<<endl;
        node *temp = head;
        // assigning head to its next pointer
        head = head->next;
        // deleting retrived node
        delete temp;
        return;
}

// Optional method to dispaly queue elements
void display() {
if(head == NULL) {
        cout<<"Queue is Empty!...."<<endl;
        return;
    }
    node *temp; // temp node to traverse list
    temp = head; // assigning head to temp node
    while(temp != NULL) {
        cout<<temp->data<<"  ->  ";
        temp = temp->next;
    }
    cout<<"NULL"<<endl;
}

int main(int argc, char** argv) {
    
    enqueue(30);
    enqueue(23);
    enqueue(56);
    dequeue();
    display();
    enqueue(400);
    display();
    dequeue();
    return 0;
}

Output:

Working:

Queue FIFO data structure is used where we want to process data that is inserted or store earlier. This data structure is most commonly used in process scheduling. In process scheduling this technique is known as FCFS (First Come First Serve).

In this program example we use linked list for queue implementation. We use here Dev-C++ IDE (Integrated Development Environment) for compile and executed source code. In this program example following three methods are created for complete representation of queue.

Operations of Queue:

In all methods implemented in queue we are required a temp node to process the queue nodes. Because queue is implemented using linked list. For linked list traversal operation we have to set address of the head node to any temp node. In enqueue operation we access the last node of the queue and insert new data item at he end of queue. Aleternatively .for dequeue operation we just retrive value from the head node and delete this head node.

In this way we achieve the order that is called FIFO (First In First Out). For process of nodes in queue we have to use iterative structure. We have used while loop for traversal of nodes.