top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Queue implementation in C using LinkList

+1 vote
868 views

What is Queue
Queue is a abstract data type with two operation add_data(enque) and get_data(deque) and provides the data in the form of its arrival or simply it maintains the first in first out machenism (FIFO). Data is always added to its top and retrieved from its rear.

Queue ADT

Required Functions 

int queue_size()
struct node * create_node(int data)
void add_data(int data)
int get_data()
void traverse_queue()

Sample Code 

struct node
{
    int data;
    struct node *next;
};

struct node *top, *rear;
int length= 0;

int queue_size()
{
    printf("\n No. of elements in queue : %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void add_data(int data)
{
    struct node *new;
    new = create_node(data);

    if ((top == NULL) && (rear == NULL))
    {
        top = new;
        rear = new;
    }
    else
    {
        top->next = new;
        top = new;
    }
}

int get_data()
{
    struct node *temp_rear;
    int ret_val;

    temp_rear = rear;

    if (temp_rear == NULL)
    {
        printf("\n Error : Trying to pop from empty queue");
        return -1;  // Assuming -1 as error
    }
    else
    {
        temp_rear = temp_rear->next;
    }

    printf("\n Popped value : %d", rear->data);
    ret_val = rear->data;

    free(rear);
    rear = temp_rear;

    length--;
    return ret_val;
}

void traverse_queue()
{
    struct node *temp_rear;

    temp_rear = top;

    if (temp_rear == NULL)
    {
        printf("Queue is empty");
        return;
    }

    while (temp_rear != NULL)
    {
        printf("%d ", temp_rear->data);
        temp_rear = temp_rear->next;
    }
}
posted Sep 3, 2014 by Salil Agrawal

  Promote This Article
Facebook Share Button Twitter Share Button LinkedIn Share Button
C language has nothing called null.
commented Sep 5, 2014 by anonymous
In get_data function, data should be returned from *rear but in the code it is being returned from top which is wrong.

 printf("\n Popped value : %d", top->data);
 ret_val = top->data;
commented Sep 11, 2014 by Ranjith
My bad, good catch corrected the code :)
commented Sep 11, 2014 by Salil Agrawal


Related Articles

Circular Linklist Implementation in C (Singly)

What is Link List
W linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a link to the next node in the sequence.

enter image description here

Why Circular Link List
As you can see in the first image that the last->next is null but if last->next is pointing to the head node is called circular link list. The main advantage id that if you have access to any node then you can get access of any node.

Necessary Functions

struct node * create_node(int data)
void insert_at_begining(int info)
void insert_at_position(int info, int position)
void delete_at_begining()
void delete_at_position(int position)
void search(int key)
void update(int olddata, int newdata)
void traverse()
void rev_traverse(struct node *p)

Sample Code
C sample code someone can try C++ code...

struct node
{
    int data;
    struct node *next;
};

/* We can have additional structure which can have head and last node is node pointer and 
   additionally can have length variable which contains the length of the link list */
struct node *head = NULL, *last = NULL;
int length = 0;


struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void insert_at_begining(int info)
{
    struct node *new;
    new = create_node(info);

    if (head == NULL && last == null)
    {   
        head = last = new;
        head->next = last->next = NULL;
    }
    else
    {
        new->next = head;
        head = new;
        last->next = head;
    }
}

void insert_at_position(int info, int position)
{
    struct node *new, *ptr, *prevnode;
    int len = 0, i;

    new = create_node(info);

    if (head == NULL)
    {
        if (position == 1)
        {
            head = last = new;
            head->next = last->next = NULL; 
        }
        else
            printf("\n empty linked list you cant insert at that particular position");
    }
    else
    {
        if (length < position)
            printf("\n node cant be inserted as position is exceeding the linkedlist length");

        else
        {
            for (ptr = head, i = 1; i <= length; i++)
            {
                prevnode = ptr;
                ptr = ptr->next;
                if (i == position-1)
                {
                    prevnode->next = new;
                    new->next = ptr;
                    break;
                }
            }
        }
    }
}

void delete_at_begining()
{
    struct node *y;

    if (head == NULL) 
        printf("\n List is empty");
    else
    {
        x = last;
        y = head;
        head = y->next;
        last->next = head;
        length--;
        free(y);
    }
}

void delete_at_position(int position)
{
    int count = 0, i;
    struct node *ptr, *temp, *prevnode;

    if (head == last && head == NULL)
        printf("\n empty linked list you cant delete");
    else
    {
        if (length < position)
            printf("\n node cant be deleted at position as it is exceeding the linkedlist length");

        else
        {
            for (ptr = head,i = 1; i <= length; i++)
            {
                prevnode = ptr;
                ptr = ptr->next;
                if (position == 1)
                {   
                    length--;
                    head = ptr;
                    last->next = head;
                    free(prevnode);
                    break;
                }
                else if (i == position - 1)
                {   
                    length--;
                    prevnode->next = ptr->next;
                    free(ptr);
                    break;
                }
            }
        }
    }
}

void search(int key)
{
    int count = 0, i, f = 0;
    struct node *ptr;

    if (head == NULL)
        printf("\nlist is empty no elemnets in list to search");
    else
    {
        for (ptr = head,i = 0; i < length; i++,ptr = ptr->next)
        {
            count++;
            if (ptr->data == key)
            {
                printf("\n the value is found at position at %d", count);
                f = 1;
            }   
        }

        if (f == 0)
            printf("\n the value is not found in linkedlist");
    }
}


void update(int olddata, int newdata)
{   
    int i, f = 0;
    struct node *ptr;

    if (head == NULL)
        printf("\n list is empty no elemnts for updation");
    else
    {   
        for (ptr = head, i = 0; i < length; ptr = ptr->next,i++)
        {   
            if (ptr->data == olddata)
            {   
                ptr->data = newdata;
                printf("value is updated to %d", ptr->data);
                f = 1;
            }   
        }

        if (f == 0)
            printf("\n no such old value to be get updated");
    }
}

void traverse()
{
    if (head == NULL)
        printf("\n List is empty");
    else
    {
        x = head;
        while (x->next !=  head)
        { 
            printf("%d->", x->data);
            x = x->next;
        }
        printf("%d", x->data);
    }
}

void rev_traverse(struct node *p)
{
    int i = 0;

    if (head == NULL)
    {
        printf("empty linked list");
    }
    else
    {
        if (p->next !=  head)
        {
            i = p->data;
            rev_traverse(p->next);
            printf(" %d", i);
        }
        if (p->next == head)
        {
            printf(" %d", p->data);
        }
    }
}
READ MORE
Stack implementation using LinkList?

What is Stack
A stack is a ADT which has LIFO i.e. last in first out behavior. Which means the element which is enetered at the later would be accessed at first. A Stack has two basic operations which are called push and pop which are used to store and retrieve data from the stack.

Stack ADT

Required Functions
Though only push and pop are the necessary function but lets define the following function for the stack implementation in C using LinkList.

int stack_size()
struct node * create_node(int data)
void push(int data) 
void pop()
void traverse_stack()

Sample Code

struct node
{
    int data;
    struct node *next;
};

struct node *top;
int length= 0;

int stack_size()
{
    printf("\n No. of elements in stack : %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void push(int data)
{
    struct node *new;
    new = create_node(data);

    if (top == NULL)
    {
        top = new;
    }
    else
    {
        new->next = top;
        top = new;
    }
}

void pop()
{
    struct node *temp_top;

    temp_top = top;

    if (temp_top == NULL)
    {
        printf("\n Error : Trying to pop from empty stack");
        return;
    }
    else
        temp_top = temp_top->next;

    printf("\n Popped value : %d", top->data);
    free(top);
    top = temp_top;

    length--;
}

void traverse_stack()
{
    struct node *temp_top;

    temp_top = top;

    if (temp_top == NULL)
    {
        printf("Stack is empty");
        return;
    }

    while (temp_top != NULL)
    {
        printf("%d ", temp_top->data);
        temp_top = temp_top->next;
    }
}
READ MORE
...