Queue

• A queue is an ordered list in which insertions are done at one end (rear) and
deletions are done at other end (front).
• The first element to be inserted is the first one to be deleted.
• Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list.
Queue
Struct queue
{
int front;
int rear;
int a[MAX];
}
typedef Struct queue Que
Queue
void create_empty_queue (Que *q)
{
rear =-1;
front =-1;
}
int is_full (Que *q) int is_empty (Que *q)
{
{
if(front == rear ==-1)
if(rear ==MAX-1) return 1;
return 1; else
else return 0;
}
return 0;
}
void insert_queue (Que *q, int item)
{
if (is_full(q))
{
printf(“Overflow”);
exit();
}
if (is_empty(q))
{
rear ++;
front ++;
}
else
rear++;
a[rear] = item;
}
Time complexity = O(1)
int delete_queue (Que *q)
{
if (is_empty(q))
{
printf(“Underflow”);
exit();
}
temp = a[front];
if (front == rear)
{
front =-1;
rear =-1;
}
else
front ++;
return temp;
Time complexity = O(1)
}
Write an algorithm to implement queue using two
stacks
void insert (int item)
{
push(S, item);
}
int delete()
{
int i, temp;
while (S1  top !=0)
{ i=pop(S1);
push(S2,i);
}
temp = pop(S1);
while(!is_empty(S2))
{ i = pop(S2);
push (S1,i);
}
return temp;
}
Linked List Representation of queue
 Insertion in queue
void insert(struct node *ptr, int item)    if (front == NULL)  
        {  
{      
            front = ptr; 
    ptr = (struct node *) malloc (sizeof(struc             rear = ptr;   
t node));               front -> next = NULL;  
    if(ptr == NULL)               rear -> next = NULL;  
    {           }  
        printf("\nOVERFLOW\n");       else   
        {  
        return;               rear -> next = ptr;  
    }               rear = ptr;  
    else               rear->next = NULL;  
    {            }  
    }  
        ptr -> data = item;   }   
To do
Deletion in queue using linked list
Drawback of linear queue
In a normal Queue, we can insert elements until queue becomes full.
But once queue becomes full, we can not insert the next element even if
there is a space in front of queue.
Circular Queue
• A queue, in which the last node is connected back to the first node to
form a cycle, is called as circular queue.
• Circular queue are the queues implemented in circular form rather than
in a straight line.
Circular Queue
int isFull() {
if ((front == rear + 1) || (front ==0 && rear == SIZE -1))
return 1;
else
return 0;
}

int isEmpty() {
if ( front == -1 )
return 1;
else
return 0;
}
void enQueue(int element)
{
if ( isFull() )
printf("\n Queue is full!! \n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
int deQueue() {
int element;
if (isEmpty()) {
printf("\n Queue is empty !! \n");
exit();
}
else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Q has only one element, so we reset the queue after dequeuing it.
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return (element);
}
}
Priority Queue
• Priority Queue is similar to a queue, and every element has some priority value
associated with it.
• The priority of the elements in a priority queue determines the order in which
elements are served (i.e., the order in which they are removed).
• If in any case the elements have same priority, they are served as per their
ordering in the queue.
• A priority queue is a container of elements, each having an associated key.
• Insert (key, data): Inserts data with key to the priority queue. Elements are ordered
based on key.
• DeleteMin/DeleteMax: Remove and return the element with the smallest/largest
key.
• GetMinimum/GetMaximum: Return the element with the smallest/largest key
without deleting it.
Applications of Queues
• There are several algorithms that use queues to solve problems. For
example, BFS, traversing of a binary tree, etc.
• Round robin scheduling for process scheduling is implemented using
queues.
• Jobs sent to a printer are places on a queue.
• Every real-life line is a queue. For example, lines at ticket counters.
List, Set, Tuple and Dictionary
• Lists: are just like dynamic sized arrays, declared in other languages (vector in C++
and ArrayList in Java). Lists need not be homogeneous always which makes it the
most powerful tool in Python.
• Tuple: A Tuple is a collection of Python objects separated by commas. In some ways,
a tuple is similar to a list in terms of indexing, nested objects, and repetition but a
tuple is immutable, unlike lists that are mutable.
• Set: A Set is an unordered collection data type that is mutable, and has no duplicate
elements. Python’s set class represents the mathematical notion of a set.
• Dictionary: Dictionaries in Python is an ordered collection of data values, used to
store data values like a map, which, unlike other Data Types that hold only a single
value as an element, Dictionary holds key:value pair. Key-value is provided in the
dictionary to make it more optimized.
Collection VS
Features Mutable Ordered Indexing Duplicate Data

List ✔ ✔ ✔ ✔

Tuple X ✔ ✔ ✔

Set ✔ X X X

Dictionary ✔ ✔ ✔ X