Queue using linked list


Logic



Enqueue
if front=NULL
    Allocate memory and data for front node.
    Make front->next = NULL.
    Assign front to rear.

else
    Allocate memory and data for current node.
    Make curr->next = NULL. 
    Let rear->next point to curr.
    Make curr as rear.
Enqueue 1    
                            front                     
                            _____
                              1 |                               
                            ____|


                          front,rear 
                              |
                             \|/
                           _______
                           | 1 | -|--->NULL
                           |___|__|

Enqueue 2

                          front                     
                          ___________
                           1   | 2   |                            
                          _____|_____|


                         front          rear
                           |             |
                          \|/           \|/
                          _______       ______
                         | 1 | --|---->| 2 | -|-->NULL                                                                                                   
                         |___|___|     |___|__|


Enqueue 3
                        front
                        _________________ 
                            1 |  2  |  3 |                       
                        ______|_____|____|


                         front                         rear
                           |                            |
                          \|/                          \|/
                          _________      _______       _______
                         |  1 | --|---->| 2 | --|---->| 3 | --|-->NULL
                         |____|___|     |___|___|     |___|___|

void enqueue(int element)
{
    node* curr;

    if(isEmpty())
    {
        front = (node*)malloc(sizeof(node));
        front->next = NULL;
        front->data = element;
        rear = front;
    }
    else
    {
        curr = (node*)malloc(sizeof(node));
        curr->data = element;
        curr->next = NULL;
        rear->next = curr;
        rear = curr;
    }
}


Dequeue
if front->next == NULL (last element present)
    Deallocate memory for node pointed by front.
    Make front and rear as NULL.
else
    Let current node point to next of front.
    Deallocate memory for node pointed by front.
    Make current node as front.
    front
                    _________________ 
                          |  2  |  3 |                       
                    ______|_____|____|


                     front           curr         rear
                       |              |            |
                      \|/            \|/          \|/
                    _________      _______       _______
                    |  1 | --|---->| 2 | --|---->| 3 | -|-->NULL
                    |____|___|     |___|___|     |___|__|


                                     front         rear
                                       |            |
                                      \|/          \|/
                                    _________     ________
                                    | 2 | --|---->| 3 | --|-->NULL
                                    |___|___|     |___|___|
void dequeue()
{
    node* curr;

    if(front==NULL)
        printf("Can't dequeue.No element in queue");
    else
    {
        if(front->next==NULL)       //last element present
        {
            free(front);
            init();
        }

        else
        {
            curr = front->next;
            free(front);
            front = curr;
        }
    }
}


No comments:

Post a Comment