Queue Implementation Using Linked List

    1. Home
    2. Tutorials
    3. Data Structure And Algorithms
    4. Data Structure And Algorithms Programs
    5. Queue
    6. Program

    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:

    C++ program to implement queue using Dev-C++ IDE

    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:

    Sr. Method/Function Description Optional/Mandatory
    1 enqueue This method is used for insertion operation in queue. Mandatory
    2 dequeue This method is used for retrival/removal of data items from the queue. Mandatory
    3 display Display method is used to display all items from the queue. This method is used to present current state of the queue. Optional

    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.

    Comments
    Login to TRACK of Comments.