Queue Data Structure (Introduction)

Queues Introduction

A Queue is another type of Data Structure, generally done via arrays. Generally, Queues are FIFO i.e. First in First out. A good example would be people standing at a billing counter in a queue, the person who comes first, will be served first
queue

More about Queues

  • Unlike arrays, where insertion and deletion can happen at any end.
  • In Queues, insertion (Enqueue) and deletion (Dequeue) can happen at only one end each.
  • Insertion happens at the rear end and deletion happens at the front
  • Queues follow FIFO First in First out structure, i.e. the element added first (Enqueued) will go out of the queue first(Dequeued)
  • Unlike stack, which follows, LIFO, last in first out, and stack where both insertion and deletion happens as one end. For queue insertion(Enqueue) and deletion(Dequeue) happens at opposite ends. 

Queue Operations

  • Enqueue: Adding a new item to the Queue Data Structure, in other words, enqueuing new item to Stack DS.

If the Queue is full, then it is said to be in an overflow condition

  • Dequeue: Removing an item from the Queue, i.e. dequeuing an item out.

If a Queue is empty then it is said to be in an underflow condition

  • IsEmpty: This returns True If the Queue is empty else returns False
  • IsFull: This returns True if the Queue is full else returns false.

Some other notations are Front and Rear, that return the front end read items of the queue.

Queue Data Structures

Representation of Queue

Queue as a data structure can be represented in two ways.

  • Stack as an Array (Most popular)
  • Stack as a struct (Popular)
  • Stack as a Linked List.

1. Enqueue()

  • When we require to add an element to the Queue we perform Enqueue() operation.
  • Push() operation is synonymous of insertion/addition in a data structure.
Queue Data Structure 2

2. Dequeue()

  • When we require to delete/remove an element to the Queue we perform Dequeue() operation.
  • Dequeue() operation is synonymous of deletion/removal in a data structure.

Applications and uses for Queues

  • Heavily used in almost all applications of the operating system, to schedule processes, moving them in or out of process scheduler.
  • FCFS, SJF etc
  • Asynchronously i.e. when data resource may be the same but not received at the same rate.
  • Anything that has to do with process and schedule, in the system or code.
#include<stdio.h>
#define SIZE 5

//setting up initial values
int queue[SIZE], front = -1, rear = -1;

void exitprogram(){
    return;
}

void enQueue(int data){
    if(rear == SIZE-1)
        printf("\nQueue was full can't do insertion");
    else{
        //When adding initial element
        if(front == -1)
            front = 0;

        rear++;
        queue[rear] = data;
        printf("\n Enqeueing Complete!!!");
   }
}
void deQueue(){
    if(front == -1)
        printf("\n Queue was Empty!!! Couldn't delete");
    else{
        printf("\n Dequeued : %d", queue[front]);
        front++;

        //condition if last remaining element was dequeued 
        if(front > rear)
	        front = rear = -1;
   }
}
void display(){
    if(rear == -1)
        printf("\nQueue was Empty!!!");
    else{
        int i;
        printf("\nQueue :\n");

        for(i=front; i<=rear; i++)
	        printf("%d ",queue[i]);
   }
}

int main()
{
   int value, preference = 1;

    while(preference){
        printf("\n\nWhat do you want to do?\n");
        printf("1. Enqueue\n2. Dequeue\n3. Print Queue\n4. Exit");

        printf("\nEnter your preference: ");
        scanf("%d",&preference);

        switch(preference){
	        case 1: 
                printf("Enter value for current Queue ");
	        scanf("%d",&value);
                enQueue(value);
		break;

	        case 2:
                deQueue();
		break;

                case 3:
                display();
	        break;

	        case 4:
                preference = 0;
	        break;

	        default: printf("\nPlease enter other value");
      }
   }
   return 0;
}

Output

What do you want to do?
1. Enqueue  2. Dequeue  3. Print Queue  4. Exit

Enter your preference: 1
Enter value for current Queue: 1
Enqeueing Complete!!!

What do you want to do?
1. Enqueue 2. Dequeue 3. Print Queue 4. Exit

Enter your preference: 1
Enter value for current Queue: 2
Enqeueing Complete!!!

What do you want to do?
1. Enqueue 2. Dequeue 3. Print Queue 4. Exit

Enter your preference: 1
Enter value for current Queue: 3
Enqeueing Complete!!!

What do you want to do?
1. Enqueue 2. Dequeue 3. Print Queue 4. Exit

Enter your preference: 2
Dequeued : 1

What do you want to do?
1. Enqueue 2. Dequeue 3. Print Queue 4. Exit

Enter your preference: 3
Queue :
2 3 4
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

// Basic struct for queue
struct Queue
{
int front, rear;
unsigned size;
//pointer named as array to point towards actual
//array memory created later in createQueue function
int* array;
};

// Here we initialize queue and init. size of queue to 0 & front, rear to -1
struct Queue* createQueue(unsigned size)
{
struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
queue->size = size;
queue->front = -1;
queue->rear = -1;

//creating required memory for array
queue->array = (int*) malloc(queue->size * sizeof(int));
return queue;
}

// Will return true if queue size has reached capacity
int isFull(struct Queue* queue)
{
if(queue->rear == queue->size -1)
printf("\nQueue was full can't do insertion");

return (queue->rear == queue->size -1);
}

// Will return true if queue size is 0
int isEmpty(struct Queue* queue)
{
if(queue->front == -1)
printf("\n Queue was Empty!!! Couldn't delete");

return (queue->front == -1);
}

// Here we add new item to queue and change rear/front and size
void enqueue(struct Queue* queue, int item)
{
if (isFull(queue))
return;

if(queue->front == -1)
queue->front = 0;

queue->rear++;
queue->array[queue->rear] = item;
printf("%d added to the queue at array pos:%d\n", item,queue->rear);
}

// Here we remove or dequeue from queue and also change the front value and size of queue
void dequeue(struct Queue* queue)
{
if (isEmpty(queue))
return;

int item = queue->array[queue->front];
queue->front++;
printf("\n%d dequeued from queue, new front is at pos:%d\n", item,queue->front);
}

void display(struct Queue* queue)
{
if(queue->rear == -1)
printf("\nQueue was Empty!!!");
else{
int i;
printf("\nQueue :\n");

for(i=queue->front; i<=queue->rear; i++)
printf("%d ",queue->array[i]);
}
}

// Main function to run queue program
int main()
{
struct Queue* queue = createQueue(5);

enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);

dequeue(queue);
dequeue(queue);

display(queue);

return 0;
}

Output

10 added to the queue at array pos:0
20 added to the queue at array pos:1
30 added to the queue at array pos:2
40 added to the queue at array pos:3

10 dequeued from queue, new front is at pos:1
20 dequeued from queue, new front is at pos:2

Queue :
30 40

3 comments on “Queue Data Structure (Introduction)”