Short Notes On Queue

A Queue is a linear data structure. It is a list in which all insertions to the queue are performed at one end and all the deletions are performed at the other end. The element in the queue are processed in the same order in which they were received. Hence it is called a First In First Out(FIFO) list.

Applications of Queue

Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.
Handling of interrupts in real-time systems.

Basic operation

enqueue() − add (store) an item to the queue.
dequeue() − remove (access) an item from the queue.

Enqueue Operation

Queues maintain two data pointers, front and rear.

The steps should for enqueue (insert) data into a queue −

Step 1 − Check if the queue is full.

Step 2 − If the queue is full, produce overflow error and exit.

Step 3 − If the queue is not full, increment rear pointer to point the next empty space.

Step 4 − Add data element to the queue location, where the rear is pointing.

Step 5 − return success.

Dequeue Operation

Accessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access.

Step 1 − Check if the queue is empty.

Step 2 − If the queue is empty, produce underflow error and exit.

Step 3 − If the queue is not empty, access the data where front is pointing.

Step 4 − Increment front pointer to point to the next available data element.

Step 5 − Return success.

Array Implementation Of Queue

#include <stdio.h>

#define MAX 50

int queue_array[MAX];

int rear = - 1;

int front = - 1;

main()

{

    int choice;

    while (1)

    {

        printf("1.Insert element to queue \n");

        printf("2.Delete element from queue \n");

        printf("3.Display all elements of queue \n");

        printf("4.Quit \n");

        printf("Enter your choice : ");

        scanf("%d", &choice);

        switch (choice)

        {

            case 1: insert();

            break;

            case 2: delete();

            break;

            case 3: display();

            break;

            case 4: exit(1);

            default: printf("Wrong choice \n");

        }   /*End of switch*/

    }   /*End of while*/

}   /*End of main()*/

insert()

{

    int add_item;

    if (rear == MAX - 1)

       {

    printf("Queue Overflow \n");

       }

    else

    {

        if (front == - 1)

           {

        /*If queue is initially empty */

        front = 0;

        printf("Inset the element in queue : ");

        scanf("%d", &add_item);

        rear = rear + 1;

        queue_array[rear] = add_item;

           }

    }

} /*End of insert()*/

delete()

{

    if (front == - 1 || front > rear)

    {

        printf("Queue Underflow \n");

        return ;

    }

    else

    {

  printf("Element deleted from queue is : %d\n", queue_array[front]);

  front = front + 1;

    }

} /*End of delete() */

display()

{

    int i;

    if (front == - 1)

       {

        printf("Queue is empty \n");

       }

    else

    {

        printf("Queue is : \n");

        for (i = front; i <= rear; i++)

            {

            printf("%d ", queue_array[i]);

            printf("\n");

            }

    }

}

Analysis of Queue

Enqueue : O(1)
Dequeue : O(1)
Size : O(1)

Please go through video:

Queue implementation in C using LinkList

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.

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;
    }
}

Short notes on Quick Sort

Quick Sort

Quick sort is a very popular sorting method. This sort name comes from the fact that quick sort can sort a list of data elements significantly faster than any of the common sorting algorithms. This sorting uses a strategy called divide and conquer. It is based on the principle that is faster and easier to sort two small arrays than one larger one.

The sequence of steps required to perform a quick sort operation on a set of elements of the array are as follows.

A pivot item near the middle of the array is chosen. Let it be x.
Now scan the array from left to right until some element e.g., a_i>x is encountered.
Now scan the array from right to left until some element e.g.,a_j<x is encountered.
Now exchange the items ai and aj.
Again repeat steps 2 to 4 until the scan operation meets somewhere in the middle of the array.

Quick sort is also called partition exchange sort and it was invented by C.A.R. Hoare. The average execution time of quick sort is O(n(log₂n)²) and this sort is good for large sorting jobs.

Pictorial Representation

Quick Sort Algorithm

1. If n < = 1, then return.

2. Pick any element V in a[]. This is called the pivot.

3. Rearrange elements of the array by moving all elements xi > V right of V and all elements xi < = V left of V. If the place of the V after re-arrangement is j, all elements with value less than V, appear in a[0], a[1] . . . . a[j – 1] and all those with value greater than V appear in a[j + 1] . . . . a[n – 1].

4. Apply quick sort recursively to a[0] . . . . a[j – 1] and to a[j + 1] . . . . a[n – 1].

Program for Quick Sort

#include <stdio.h>
void quick_sort(int[], int, int);
int partition(int[], int, int);
int main()
{
   int a[50], n, i;
   printf("How many elements?");
   scanf("%d", & n);
   printf("\nEnter array elements:");
   for (i = 0; i < n; i++)
   {
       scanf("%d", & a[i]);
   }
   quick_sort(a, 0, n - 1);
   printf("\nArray after sorting:");
   for (i = 0; i < n; i++)
   {
       printf("%d ", a[i]);
   }

   return 0;
}

void quick_sort(int a[], int l, int u)
{
   int j;
   if (l < u)
   {
       j = partition(a, l, u);
       quick_sort(a, l, j - 1);
       quick_sort(a, j + 1, u);
   }
}

int partition(int a[], int l, int u)
{
   int v, i, j, temp;
   v = a[l];
   i = l;
   j = u + 1;
   do
   {
       do
{
           i++;
}
       while (a[i] < v && i <= u);
       do
{
           j--;
}
       while (v < a[j]);
       if (i < j)
       {
           temp = a[i];
           a[i] = a[j];
           a[j] = temp;
       }
   }
   while (i < j);
   a[l] = a[j];
   a[j] = v;
   return (j);
}

The complexity of the quick sort algorithm is given in the following table.

Algorithm	Worst case	Average case	Best case
Quick sort	O(n)²	log₂n	log₂n

Short Notes On Queue

Enqueue Operation

Your comment on this post:

Related Articles