Create FREE 'HowTo' Videos with MyGuide

Queue



Pass Quiz and Get a Badge of Learning



Content "filtered", Please subscribe for FULL access.


Chapter 4 : Queue


Queue arrow_upward


  • A Queue is a particular kind of collection in which the entities are kept in order.
  • Implements First In, First Out (FIFO) storage system.
  • The first element added to the queue will be the first one to be removed.
  • It does not have a specific capacity regardless of how many elements are already contained; a new element can always be added.
  • A bounded queue is a queue limited to a fixed number of items.

  • Queue Data Structure arrow_upward


    Insertion operation in queue:

    Deletion operation in a queue:


    Example of a Program to Implement Queue using Pointers arrow_upward

    PROGRAM:
    #define true 1
    #define false 0
    #include<stdio.h>
    #include<conio.h>
    #include<process.h>
    #include<stdlib.h>
    struct q_point
    {
    int ele;
    struct q_point* n;
    };
    struct q_point *f_ptr = NULL;
    int e_que(void);
    void add_ele(int);
    int rem_ele(void);
    void show_ele();
    /*main function*/
    main()
    {
    int ele,choice,j;
    while(1)
    {
    printf("\n\n****IMPLEMENTATION OF QUEUE USING POINTERS****\n");
    printf("==============================================");
    printf("\n\t\t MENU\n");
    printf("==============================================");
    printf("\n\t[1] To insert an element");
    printf("\n\t[2] To remove an element");
    printf("\n\t[3] To all the elements");
    printf("\n\t[4] Exit");
    printf("\n\n\tEnter your choice:");
    scanf("%d", &choice);
    switch(choice)
    {
    case 1:
    {
    printf("\n\tElement to be inserted:");
    scanf("%d",&ele);
    getchar();
    add_ele(ele);
    break;
    }
    case 2:
    {
    if(!e_que())
    {
    j=rem_ele();
    printf("\n\t%d is removed from the queue",j);
    }
    else
    {
    printf("\n\tQueue is Empty.");
    getch();
    }
    break;
    }
    case 3:
    show_ele();
    getch();
    break;
    case 4:
    exit(1);
    break;
    default:
    printf("\n\tInvalid choice.");
    getch();
    break;
    }
    }
    }
    /* Function to check if the queue is empty*/
    int e_que(void)
    {
    if(f_ptr==NULL)
    return true;
    return false;
    }
    /* Function to add an element to the queue*/
    void add_ele(int ele)
    {
    struct q_point *queue = (struct q_point*)malloc(sizeof(struct q_point));
    queue->ele = ele;
    queue->n = NULL;
    if(f_ptr==NULL)
    f_ptr = queue;
    else
    {
    struct q_point* ptr;
    ptr = f_ptr;
    for(ptr=f_ptr ;ptr->n!=NULL; ptr=ptr->n);
    ptr->n = queue;
    }
    }
    /* Function to remove an element from the queue*/
    int rem_ele()
    {
    struct q_point* queue=NULL;
    if(e_que()==false)
    {
    int j = f_ptr->ele;
    queue=f_ptr;
    f_ptr = f_ptr->n;
    free(queue);
    return j;
    }
    else
    {
    printf("\n\tQueue is empty.");
    return -9999;
    }
    }
    /* Function to display the queue*/
    void show_ele()
    {
    struct q_point *ptr=NULL;
    ptr=f_ptr;
    if(e_que())
    {
    printf("\n\tQUEUE is Empty.");
    return;
    }
    else
    {
    printf("\n\tElements in Queue are:\n\t");
    while(ptr!=NULL)
    {
    printf("%d\t",ptr->ele);
    ptr=ptr->n;
    }
    }
    }
    
    
    OUTPUT:
    ****IMPLEMENTATION OF QUEUE USING POINTERS****
    ==============================================
                     MENU
    ==============================================
            [1] To insert an element
            [2] To remove an element
            [3] To all the elements
            [4] Exit
    
            Enter your choice:1
    
            Element to be inserted:45
    
    
    ****IMPLEMENTATION OF QUEUE USING POINTERS****
    ==============================================
                     MENU
    ==============================================
            [1] To insert an element
            [2] To remove an element
            [3] To all the elements
            [4] Exit
    
            Enter your choice:1
    
            Element to be inserted:32
    
    
    ****IMPLEMENTATION OF QUEUE USING POINTERS****
    ==============================================
                     MENU
    ==============================================
            [1] To insert an element
            [2] To remove an element
            [3] To all the elements
            [4] Exit
    
            Enter your choice:3
    
            Elements in Queue are:
            45      32
    
    ****IMPLEMENTATION OF QUEUE USING POINTERS****
    ==============================================
                     MENU
    ==============================================
            [1] To insert an element
            [2] To remove an element
            [3] To all the elements
            [4] Exit
    
            Enter your choice:5
    
            Invalid choice.
    
    25
    

    DESCRIPTION:

  • In the above program, pointer *q and integer rear are declared.
  • The variable rear is initialized with zero.
  • By using scanf (), statement elements are entered.
  • In the while loop pointer q and rear are increased.
  • If the rear reaches to seven, the break statement terminates the loop.
  • After the execution of while loop, the pointer q points to last memory location of the queue.
  • The starting address of the queue is again set by the statement q = q-rear.
  • Finally, using second while loop and continuous increment operation with rear, successive memory locations are accessed and elements are displayed.

  • Circular Queue arrow_upward


  • Let us consider an array A with n elements in which A[1] comes after A[N].
    • When this technique is applied to construct a queue then the queue is called a circular queue.
  • In a circular queue A, if A[N] is occupied and we have to insert an element then instead of moving all the elements forward, we insert this element at position A[1].
  • This operation takes less time than that of moving all the elements forward.

  • Priority Queues arrow_upward


  • A priority queue is defined as a queue in which each element has a priority associated with it.
  • This priority determines the order in which they exit the queue.
    • An element of higher priority is processed before any element of lower priority.
    • Two elements with the same priority are processed according to the order in which they were added to the queue.

    Deques arrow_upward


  • A Deque is defined as a linear list in which insertions and deletions are possible at either end but not in the middle.
  • Input Restricted Deque:
  • An input restricted deque is a deque which allows insertion at one end of the list but allows deletions at both ends of the list.
  • Output Restricted Deque:
  • An Output Restricted Deque is a deque which allows deletions only at one end of the list but allows insertions at both end of the list.

  • Thank You from Kimavi arrow_upward


  • Please email us at Admin@Kimavi.com and help us improve this tutorial.


  • Mark as Complete => Receive a Certificate in Data-Structure


    Kimavi Logo

    Terms and conditions, privacy and cookie policy | Facebook | YouTube | TheCodex.Me | Email Kimavi


    Kimavi - A Video Learning Library { Learning is Earning }

    Get Ad Free Learning with Progress Report, Tutor Help, and Certificate of Learning for only $10 a month



    All videos on this site created using MyGuide.

    Create FREE HowTo videos with MyGuide.